Sorting Algorithms
Sorting Algorithm
A Sorting Algorithm is used to rearrange a given array or list of
elements in an order.
For example, a given array [10, 20, 5, 2] becomes [2, 5, 10, 20] after
sorting in increasing order and becomes [20, 10, 5, 2] after sorting in
decreasing order.
Bubble Sort
Bubble Sort is a comparison based simple sorting algorithm that
works by comparing the adjacent elements and swapping them if the
elements are not in the correct order.
It is an in-place and stable sorting algorithm that can sort items in
data structures such as arrays and linked lists.
Working of Bubble Sort Algorithm
5, 3, 1, 4, 2
Bubble Sort
Bubble Sort is simple and easy to implement.
It repeatedly swaps adjacent elements until the array is sorted.
Works well for small datasets but slow for large ones.
// Step 2: Bubble Sort
for (i = 0; i < n - 1; i++) {
#include <stdio.h> for (j = 0; j < n - i - 1; j++) {
void main() { if (arr[j] > arr[j + 1]) {
int arr[100], n, i, j, temp; // swap arr[j] and arr[j + 1]
// Step 1: Take input temp = arr[j];
printf("Enter number of elements: "); arr[j] = arr[j + 1];
scanf("%d", &n); arr[j + 1] = temp;
printf("Enter %d elements: ", n); }
for (i = 0; i < n; i++) }
scanf("%d", &arr[i]); }
// Step 3: Display result
printf("Sorted array in ascending order:\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
}
Selection Sort
Selection Sort works by:
Repeatedly finding the smallest element (for ascending order) from
the unsorted part of the array.
Swapping it with the first unsorted element.
After each pass, one element is placed in its correct sorted position.
Working of Selection Sort
5, 3, 1, 4, 2
Selection Sort
Simple to understand.
Works by selecting the smallest element in each pass.
Fewer swaps than Bubble Sort.
Still inefficient for large datasets (O(n²)).
#include <stdio.h> // Step 2: Selection Sort
for (i = 0; i < n - 1; i++) {
int main() { minIndex = i;
int arr[100], n, i, j, minIndex, temp; for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) { // Step 3: Display result
minIndex = j; printf("Sorted array in ascending order:\n");
// Step 1: Input for (i = 0; i < n; i++)
printf("Enter number of elements: "); }
} printf("%d ", arr[i]);
scanf("%d", &n);
// Swap if new minimum return 0;
printf("Enter %d elements: ", n); }
for (i = 0; i < n; i++) found
scanf("%d", &arr[i]); if (minIndex != i) {
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
Insertion Sort
Insertion Sort builds the sorted list one element at a time.
It works the same way as you sort playing cards in your hand —
pick a card and insert it into the correct position among the already
sorted cards.
Insertion Sort
For each element in the array:
Treat the first element as already sorted.
Take the next element (key).
Compare it with elements on the left (sorted part).
Shift larger elements one position to the right.
Insert the key in its correct position.
Working of Insertion Sort
10, 4, 9, 1, 3, 5, 6, 8, 2
// Step 2: Insertion Sort
#include <stdio.h> for (i = 1; i < n; i++) {
key = arr[i];
int main() { j = i - 1;
int arr[100], n, i, j, key;
// Move elements greater than key one position ahead
// Step 1: Input while (j >= 0 && arr[j] > key) {
printf("Enter number of elements: "); arr[j + 1] = arr[j];
scanf("%d", &n); j--;
}
printf("Enter %d elements: ", n); arr[j + 1] = key;
for (i = 0; i < n; i++) }
scanf("%d", &arr[i]);
// Step 3: Output
printf("Sorted array in ascending order:\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;