SORTING
⭐ 1. Bubble Sort
Concept: Repeatedly swaps adjacent elements if out of order.
Best: O(n) → Array already sorted
Worst: O(n²) → Array in reverse order
Preferably used when: Data size is very small and simplicity is needed.
⭐ 2. Selection Sort
Concept: Selects the minimum element and places it at the correct position each pass.
Best: O(n²) → Even if sorted, full scan required
Worst: O(n²) → Reverse or random order
Preferably used when: Swaps must be minimized (it does only n swaps).
⭐ 3. Insertion Sort
Concept: Inserts each element into its correct position like arranging cards.
Best: O(n) → Array already/nearly sorted
Worst: O(n²) → Array in reverse order
Preferably used when: Data is small or almost sorted.
⭐ 4. Radix Sort
Concept: Sorts numbers digit-by-digit using counting sort.
Best: O(d·(n + k)) → Small digits / uniform distribution
Worst: O(d·(n + k)) → Large number of digits
Preferably used when: Sorting large lists of integers/strings with fixed-length keys.
⭐ 5. Shell Sort
Concept: Performs gap-based comparisons, ending with insertion sort.
Best: O(n log n) → Nearly sorted with good gap sequence
Worst: O(n²) → Bad gap sequence
Preferably used when: Arrays are medium-sized and faster than simple sorts is needed.
⭐ 6. Quick Sort
Concept: Picks pivot, partitions elements into left (smaller) and right (larger), recursively sorts.
Best: O(n log n) → Balanced partitions
Worst: O(n²) → Pivot always smallest/largest (sorted or reverse order)
Preferably used when: General-purpose sorting; fastest in practice for large arrays.
⭐ 7. Merge Sort
Concept: Recursively splits array into halves and merges them in sorted order.
Best: O(n log n) → Always
Worst: O(n log n) → Always
Preferably used when: Stable sort is required, or for linked lists and external sorting (large data on disk).
1. BUBBLE SORT
#include <stdio.h>
int main() {
int n, i, j, temp;
// Taking array size
printf("Enter number of elements: ");
scanf("%d", &n);
int a[n];
// Input elements
printf("Enter %d elements:\n", n);
for(i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
// Bubble Sort
for(i = 0; i < n - 1; i++) {
for(j = 0; j < n - i - 1; j++) {
// Swap if out of order
if(a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
// Output sorted array
printf("Sorted array: ");
for(i = 0; i < n; i++) {
printf("%d ", a[i]);
}
return 0;
}
2. SELECTION SORT
#include <stdio.h>
int main() {
int n, i, j, minIndex, temp;
// Input size
printf("Enter number of elements: ");
scanf("%d", &n);
int a[n];
// Input elements
printf("Enter %d elements:\n", n);
for(i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
// Selection Sort
for(i = 0; i < n - 1; i++) {
// Assume current index is the minimum
minIndex = i;
// Find the actual minimum in the remaining array
for(j = i + 1; j < n; j++) {
if(a[j] < a[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum with element at i
temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
// Output sorted array
printf("Sorted array: ");
for(i = 0; i < n; i++) {
printf("%d ", a[i]);
}
return 0;
}
[Link] sort:
#include <stdio.h>
int main() {
int n, i, j, key;
printf("Enter number of elements: ");
scanf("%d", &n);
int a[n];
printf("Enter %d elements:\n", n);
for(i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
// Insertion Sort
for(i = 1; i < n; i++) {
key = a[i]; // Current element
j = i - 1;
// Shift bigger elements to the right
while(j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
// Place key in correct position
a[j + 1] = key;
}
printf("Sorted array: ");
for(i = 0; i < n; i++) {
printf("%d ", a[i]);
}
return 0;
}
[Link] sort
#include <stdio.h>
int getMax(int a[], int n) {
int max = a[0];
for(int i = 1; i < n; i++)
if(a[i] > max)
max = a[i];
return max;
}
void countingSort(int a[], int n, int exp) {
int output[n];
int count[10] = {0};
// Count digits
for(int i = 0; i < n; i++)
count[(a[i] / exp) % 10]++;
// Cumulative count
for(int i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build output array
for(int i = n - 1; i >= 0; i--) {
int digit = (a[i] / exp) % 10;
output[count[digit] - 1] = a[i];
count[digit]--;
}
// Copy back
for(int i = 0; i < n; i++)
a[i] = output[i];
}
void radixSort(int a[], int n) {
int max = getMax(a, n);
// sort for 1s, 10s, 100s place
for(int exp = 1; max/exp > 0; exp *= 10)
countingSort(a, n, exp);
}
int main() {
int a[] = {839, 415, 73, 92};
int n = 4;
radixSort(a, n);
for(int i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}
5. Shell sort
#include <stdio.h>
void shellSort(int a[], int n) {
int gap, i, j, temp;
// Start with large gap then reduce it
for(gap = n/2; gap > 0; gap /= 2) {
// Do gapped insertion sort for this gap
for(i = gap; i < n; i++) {
temp = a[i];
j = i;
// Move elements that are gap apart
while(j >= gap && a[j - gap] > temp) {
a[j] = a[j - gap];
j = j - gap;
}
a[j] = temp;
}
}
}
int main() {
int a[] = {40, 10, 80, 20, 60, 30};
int n = 6;
shellSort(a, n);
printf("Sorted array: ");
for(int i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}
[Link] sort
#include <stdio.h>
// Function to swap two numbers
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Partition function
int partition(int a[], int low, int high) {
int pivot = a[high]; // choose last element as pivot
int i = low - 1; // index of smaller element
for(int j = low; j < high; j++) {
// if current element <= pivot, swap it to left side
if(a[j] <= pivot) {
i++;
swap(&a[i], &a[j]);
}
}
// place pivot in correct position
swap(&a[i + 1], &a[high]);
return i + 1; // pivot index
}
// QuickSort function
void quickSort(int a[], int low, int high) {
if(low < high) {
int p = partition(a, low, high);
quickSort(a, low, p - 1); // sort left side
quickSort(a, p + 1, high); // sort right side
}
}
int main() {
int a[] = {50, 20, 10, 40, 30};
int n = 5;
quickSort(a, 0, n - 1);
printf("Sorted array: ");
for(int i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}
7. Merge sort
#include <stdio.h>
void merge(int a[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int left[n1], right[n2];
// Copy data to temp arrays
for(i = 0; i < n1; i++)
left[i] = a[l + i];
for(j = 0; j < n2; j++)
right[j] = a[m + 1 + j];
i = 0; // index of left array
j = 0; // index of right array
k = l; // index of merged array
// Merge the two arrays
while(i < n1 && j < n2) {
if(left[i] <= right[j]) {
a[k] = left[i];
i++;
} else {
a[k] = right[j];
j++;
}
k++;
}
// Copy remaining elements of left[]
while(i < n1) {
a[k] = left[i];
i++;
k++;
}
// Copy remaining elements of right[]
while(j < n2) {
a[k] = right[j];
j++;
k++;
}
}
void mergeSort(int a[], int l, int r) {
if(l < r) {
int m = (l + r) / 2;
mergeSort(a, l, m); // left half
mergeSort(a, m + 1, r); // right half
merge(a, l, m, r); // merge halves
}
}
int main() {
int a[] = {50, 20, 10, 40, 30};
int n = 5;
mergeSort(a, 0, n - 1);
printf("Sorted array: ");
for(int i = 0; i < n; i++)
printf("%d ", a[i]);
return 0;
}
Explanation for Insertion sort:
Okay, no problem — I will explain SUPER SLOW, SUPER SIMPLE, like you are learning it for the
first time, and you will DEFINITELY understand it now.
I’ll avoid technical words and explain what is happening inside the code in plain English.
⭐ Let’s take a small array:
[12, 5, 7]
We will trace the code for this array.
⭐ First, understand the goal
Insertion sort works like this:
We keep the left side sorted.
We pick one number from the right
and insert it into the correct place on the left.
Like arranging cards in your hand.
⭐ NOW LET’S GO LINE BY LINE (VERY
SIMPLE)
❗ Code part:
for(i = 1; i < n; i++) {
👉 What this means:
We start from index 1 (the SECOND element), because the FIRST element alone is already “sorted”.
So first we pick:
🔹 i = 1 → key = a[1] = 5
We want to insert 5 into the left side [12].
⭐ Next line:
key = a[i];
👉 Meaning:
Pick the element you want to insert.
So:
key = 5
⭐ Next line:
j = i - 1;
👉 Meaning:
Start looking to the left side from the element before key.
So:
i = 1
j = 0
j points to 12
Now we compare 12 with 5.
⭐ Now the important while loop:
while(j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
This part is what confuses everyone — so I will break it SLOWLY.
🔥 WHAT DOES WHILE LOOP DO?
It checks:
“Is the left element bigger than the key?”
If yes:
➡ shift that left element to the right
➡ move j one step left
➡ check again
Let’s do it for our example.
⭐ PASS: i = 1, key = 5
Left side is [12]
Check while condition:
j = 0 (points to 12)
a[j] = 12
key = 5
Is 12 > 5? → YES
So inside the loop:
Step 1:
a[j + 1] = a[j]
Which means:
a[1] = 12
Array becomes:
[12, 12, 7]
We have “shifted” 12 to the right to make space for 5.
Step 2:
j--;
Now:
j = -1
Loop stops because j < 0.
⭐ After loop ends:
a[j + 1] = key;
➡ We insert key (5) into the empty space.
Since j = -1:
j + 1 = 0
So:
a[0] = 5
Final array after first pass:
[5, 12, 7]
⭐ SECOND PASS (i = 2)
key = 7
Left side is [5,12]
Compare 12 > 7 → shift
Array becomes:
[5, 12, 12]
Compare 5 > 7? NO → stop
Insert 7:
[5, 7, 12]
🎉 Final Sorted Array
[5, 7, 12]
⭐⭐ THE MOST IMPORTANT IDEA
✔ The while loop SHIFTS bigger elements to the right
✔ After shifting is done, we place key in the empty place
✔ That’s why it's called Insertion sort
❤️If you STILL WANT MORE SIMPLE
explanation
I can explain using:
🔹 a drawing
🔹 animation-style steps
🔹 real-life card analogy
🔹 full table with i and j values
Just tell me which style you prefer, and I’ll make it even simpler.