Sorting Algorithms
Sorting means arranging data in a specific order — either ascending or descending. Sorting
helps in searching, data analysis, and efficient organization of data. The most common and
simple sorting algorithms are: Bubble Sort, Selection Sort, and Insertion Sort.
1. Bubble Sort
Definition:
Bubble Sort is a simple sorting algorithm that repeatedly compares adjacent elements and
swaps them if they are in the wrong order. This process continues until the entire list is
sorted.
Algorithm Steps:
1. Compare the first and second elements.
2. Swap if needed.
3. Repeat for all elements.
4. Continue until no swaps occur.
Example:
Unsorted array: [5, 2, 8, 4, 1]
Pass 1: [2, 5, 4, 1, 8]
Pass 2: [2, 4, 1, 5, 8]
Pass 3: [2, 1, 4, 5, 8]
Pass 4: [1, 2, 4, 5, 8]
Final Sorted Array: [1, 2, 4, 5, 8]
Program in C:
#include <stdio.h>
int main() {
int a[5] = {5, 2, 8, 4, 1};
int i, j, temp;
for(i = 0; i < 5-1; i++) {
for(j = 0; j < 5-i-1; j++) {
if(a[j] > a[j+1]) {
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
printf("Sorted array: ");
for(i = 0; i < 5; i++)
printf("%d ", a[i]);
return 0;
}
Time Complexity:
Best: O(n)
Worst: O(n²)
Average: O(n²)
2. Selection Sort
Definition:
Selection Sort finds the smallest element from the unsorted part of the array and places it at
the beginning of the sorted part.
Algorithm Steps:
1. Find the smallest element.
2. Swap it with the first element.
3. Repeat for all positions.
Example:
Unsorted array: [5, 2, 8, 4, 1]
Pass 1: [1, 2, 8, 4, 5]
Pass 2: [1, 2, 8, 4, 5]
Pass 3: [1, 2, 4, 8, 5]
Pass 4: [1, 2, 4, 5, 8]
Final Sorted Array: [1, 2, 4, 5, 8]
Program in C:
#include <stdio.h>
int main() {
int a[5] = {5, 2, 8, 4, 1};
int i, j, min, temp;
for(i = 0; i < 5-1; i++) {
min = i;
for(j = i+1; j < 5; j++) {
if(a[j] < a[min])
min = j;
}
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
printf("Sorted array: ");
for(i = 0; i < 5; i++)
printf("%d ", a[i]);
return 0;
}
Time Complexity:
Best: O(n²)
Worst: O(n²)
Average: O(n²)
3. Insertion Sort
Definition:
Insertion Sort works by taking one element at a time and inserting it into its correct
position in the sorted part of the array.
Algorithm Steps:
1. Start from the second element.
2. Compare with previous elements.
3. Insert into the correct position.
4. Repeat.
Example:
Unsorted array: [5, 2, 8, 4, 1]
Pass 1: [2, 5, 8, 4, 1]
Pass 2: [2, 5, 8, 4, 1]
Pass 3: [2, 4, 5, 8, 1]
Pass 4: [1, 2, 4, 5, 8]
Final Sorted Array: [1, 2, 4, 5, 8]
Program in C:
#include <stdio.h>
int main() {
int a[5] = {5, 2, 8, 4, 1};
int i, j, key;
for(i = 1; i < 5; i++) {
key = a[i];
j = i - 1;
while(j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
printf("Sorted array: ");
for(i = 0; i < 5; i++)
printf("%d ", a[i]);
return 0;
}
Time Complexity:
Best: O(n)
Worst: O(n²)
Average: O(n²)
Comparison Table
Bubble Sort - Best: O(n), Worst: O(n²), Stable: Yes
Selection Sort - Best: O(n²), Worst: O(n²), Stable: No
Insertion Sort - Best: O(n), Worst: O(n²), Stable: Yes
Conclusion
Bubble Sort is simple but slow for large data.
Selection Sort reduces swaps but still O(n²).
Insertion Sort is efficient for small or nearly sorted data.
All three are basic sorting algorithms and form the foundation for advanced sorting
methods.