Scribd
Upload
1 views9 pages

Sorting Algorithms Complete

The document provides an overview of four sorting algorithms: Bubble Sort, Insertion Sort, Selection Sort, and Quick Sort, including their concepts, step-by-step examples, and C programs for implementation. Each algorithm is explained with an example input and the final sorted output, along with their time complexities. Bubble, Insertion, and Selection Sort have a time complexity of O(n^2), while Quick Sort is more efficient with a time complexity of O(n log n).

Uploaded by

Prashant Chaudhary
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
1 views9 pages

Sorting Algorithms Complete

The document provides an overview of four sorting algorithms: Bubble Sort, Insertion Sort, Selection Sort, and Quick Sort, including their concepts, step-by-step examples, and C programs for implementation. Each algorithm is explained with an example input and the final sorted output, along with their time complexities. Bubble, Insertion, and Selection Sort have a time complexity of O(n^2), while Quick Sort is more efficient with a time complexity of O(n log n).

Uploaded by

Prashant Chaudhary
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Sorting Algorithms: Bubble, Insertion, Selection and Quick Sort

Includes:

- Concept

- Elaborated step-by-step example

- C program

- Comments

- Output

1. BUBBLE SORT

Concept:

Bubble Sort compares adjacent elements and swaps them if they are in
wrong order.

After every pass the largest element reaches its correct position.

Example:

Input:

52813

Pass 1:
Compare 5 and 2

5 > 2 -> Swap

25813

Compare 5 and 8

5 < 8 -> No Swap

25813

Compare 8 and 1

8 > 1 -> Swap

25183

Compare 8 and 3

8 > 3 -> Swap

25138

Final Sorted Array:

12358

C Program:

#include<stdio.h>
int main()

int a[5]={5,2,8,1,3}; // Declare and initialize array

int i,j,temp; // Declare variables

for(i=0;i<4;i++) // Number of passes

for(j=0;j<4-i;j++) // Compare adjacent elements

if(a[j]>a[j+1]) // Check condition

temp=a[j]; // Swap elements

a[j]=a[j+1];

a[j+1]=temp;

for(i=0;i<5;i++)

printf("%d ",a[i]);

return 0;
}

2. INSERTION SORT

Concept:

Insertion Sort inserts each element into its correct position.

Example:

52813

Insert 2:

25813

Insert 1:

12583

Insert 3:

12358

C Program:
#include<stdio.h>

int main()

int a[5]={5,2,8,1,3};

int i,j,key;

for(i=1;i<5;i++)

key=a[i]; // Select element

j=i-1;

while(j>=0 && a[j]>key)

a[j+1]=a[j]; // Shift element

j--;

a[j+1]=key; // Insert element

return 0;
}

3. SELECTION SORT

Concept:

Selection Sort selects the smallest element and places it in correct position.

Example:

52813

Smallest = 1

12853

Smallest = 3

12358

C Program:
#include<stdio.h>

int main()

int a[5]={5,2,8,1,3};

int i,j,min,temp;

for(i=0;i<4;i++)

min=i; // Assume minimum

for(j=i+1;j<5;j++)

if(a[j]<a[min])

min=j;

temp=a[i]; // Swap

a[i]=a[min];

a[min]=temp;

return 0;
}

4. QUICK SORT

Concept:

Quick Sort uses Divide and Conquer method.

Steps:

1. Select pivot

2. Smaller elements move left

3. Larger elements move right

Example:

Input:

52813

Pivot = 3

Left: 1 2
Pivot: 3

Right: 5 8

Output:

12358

Time Complexity:

Bubble Sort O(n^2)

Insertion Sort O(n^2)

Selection Sort O(n^2)

Quick Sort O(n log n)

You might also like