What is Sorting in C?
Sorting is the process of arranging elements of an array or list in a specific order, usually:
Ascending order (smallest → largest)
Descending order (largest → smallest)
In C, sorting can be done using different algorithms like Bubble Sort, Insertion Sort, Selection Sort.
1. Bubble Sort
Definition:
Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.
The largest element "bubbles" to the end in each pass.
Algorithm:
1. Repeat n-1 times:
o For each pair of adjacent elements:
If arr[j] > arr[j+1], swap them.
2. After each pass, the largest element is fixed at the end.
Repeatedly compare adjacent elements and swap if out of order. After pass k, the last k elements are in
final position.
Algorithm:
1. Compare the first element with the second.
2. If the first is greater than the second (for ascending), swap them.
3. Move to the next pair and continue.
4. After each pass, the largest element moves to the end.
5. Repeat until the array is sorted.
Start: [5, 3, 4, 1, 2]
Pass 1 (compare up to index 3):
(0,1): 5 > 3 → swap → [3, 5, 4, 1, 2]
(1,2): 5 > 4 → swap → [3, 4, 5, 1, 2]
(2,3): 5 > 1 → swap → [3, 4, 1, 5, 2]
(3,4): 5 > 2 → swap → [3, 4, 1, 2, 5] (5 is fixed at end)
Pass 2 (compare up to index 2):
, (0,1): 3 > 4? no → [3, 4, 1, 2, 5]
(1,2): 4 > 1 → swap → [3, 1, 4, 2, 5]
(2,3): 4 > 2 → swap → [3, 1, 2, 4, 5] (4 is now fixed at index 3)
Pass 3 (compare up to index 1):
(0,1): 3 > 1 → swap → [1, 3, 2, 4, 5]
(1,2): 3 > 2 → swap → [1, 2, 3, 4, 5] (3 fixed at index 2)
Pass 4 (compare up to index 0):
(0,1): 1 > 2? no → [1, 2, 3, 4, 5] (already sorted)
Result: [1, 2, 3, 4, 5]
Invariants: after each pass, the largest remaining element “bubbles” to its final spot at the end.
2. Insertion Sort —
Insertion sort builds the sorted array one element at a time. It takes one element from the
unsorted part and inserts it into its correct position in the sorted part.
Algorithm:
Assume the first element is already sorted.
Pick the next element.
Compare it with elements in the sorted part and shift the elements to the right until the
correct position is found.
Insert the element at the correct position.
Repeat for all elements.
Idea: Build a sorted left portion by inserting each new element (key) into its correct place among the
already-sorted left side.
Example: [29, 10, 14, 37, 13]
Step-by-Step Dry Run:
Pass 1 (second element = 10):
Consider first element 29 → already sorted.
Now pick 10.
Compare 10 with 29. Since 10 < 29, shift 29 to the right.
Insert 10 before 29.
Array becomes: [10, 29, 14, 37, 13]
Pass 2 (third element = 14):
Sorting is the process of arranging elements of an array or list in a specific order, usually:
Ascending order (smallest → largest)
Descending order (largest → smallest)
In C, sorting can be done using different algorithms like Bubble Sort, Insertion Sort, Selection Sort.
1. Bubble Sort
Definition:
Bubble Sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.
The largest element "bubbles" to the end in each pass.
Algorithm:
1. Repeat n-1 times:
o For each pair of adjacent elements:
If arr[j] > arr[j+1], swap them.
2. After each pass, the largest element is fixed at the end.
Repeatedly compare adjacent elements and swap if out of order. After pass k, the last k elements are in
final position.
Algorithm:
1. Compare the first element with the second.
2. If the first is greater than the second (for ascending), swap them.
3. Move to the next pair and continue.
4. After each pass, the largest element moves to the end.
5. Repeat until the array is sorted.
Start: [5, 3, 4, 1, 2]
Pass 1 (compare up to index 3):
(0,1): 5 > 3 → swap → [3, 5, 4, 1, 2]
(1,2): 5 > 4 → swap → [3, 4, 5, 1, 2]
(2,3): 5 > 1 → swap → [3, 4, 1, 5, 2]
(3,4): 5 > 2 → swap → [3, 4, 1, 2, 5] (5 is fixed at end)
Pass 2 (compare up to index 2):
, (0,1): 3 > 4? no → [3, 4, 1, 2, 5]
(1,2): 4 > 1 → swap → [3, 1, 4, 2, 5]
(2,3): 4 > 2 → swap → [3, 1, 2, 4, 5] (4 is now fixed at index 3)
Pass 3 (compare up to index 1):
(0,1): 3 > 1 → swap → [1, 3, 2, 4, 5]
(1,2): 3 > 2 → swap → [1, 2, 3, 4, 5] (3 fixed at index 2)
Pass 4 (compare up to index 0):
(0,1): 1 > 2? no → [1, 2, 3, 4, 5] (already sorted)
Result: [1, 2, 3, 4, 5]
Invariants: after each pass, the largest remaining element “bubbles” to its final spot at the end.
2. Insertion Sort —
Insertion sort builds the sorted array one element at a time. It takes one element from the
unsorted part and inserts it into its correct position in the sorted part.
Algorithm:
Assume the first element is already sorted.
Pick the next element.
Compare it with elements in the sorted part and shift the elements to the right until the
correct position is found.
Insert the element at the correct position.
Repeat for all elements.
Idea: Build a sorted left portion by inserting each new element (key) into its correct place among the
already-sorted left side.
Example: [29, 10, 14, 37, 13]
Step-by-Step Dry Run:
Pass 1 (second element = 10):
Consider first element 29 → already sorted.
Now pick 10.
Compare 10 with 29. Since 10 < 29, shift 29 to the right.
Insert 10 before 29.
Array becomes: [10, 29, 14, 37, 13]
Pass 2 (third element = 14):
