Sorting an Array in C
Sorting means arranging values in order: ascending (small to big) or descending (big to small). A merit list, a price list from low to high, and contacts from A to Z are all sorted lists.
In this lesson you will write the two sorting programs that every C exam asks: bubble sort and selection sort. You will trace them pass by pass, so you can also solve dry-run questions.
What You Will Learn
- What sorting is.
- How bubble sort works, with a program and a dry run.
- How to stop bubble sort early when the array is already sorted.
- How selection sort works, with a program and a dry run.
- Time complexity and the difference between the two.
Bubble Sort and Selection Sort Explained
Exam definition: Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order; after each pass the largest remaining element reaches the end. Selection sort repeatedly selects the smallest element from the unsorted part and swaps it with the first unsorted position.
Memory trick: Bubble sort = air bubbles in water: the biggest bubble rises to the top (end) first. Selection sort = a team captain selecting the shortest player first for the line, then the next shortest, and so on.
Algorithms
BUBBLE SORT (n elements)
for pass = 0 to n-2:
for j = 0 to n-2-pass:
if a[j] > a[j+1]: swap a[j], a[j+1]
SELECTION SORT (n elements)
for i = 0 to n-2:
min = i
for j = i+1 to n-1:
if a[j] < a[min]: min = j
swap a[i], a[min]
Example 1: Bubble Sort Program in C
#include <stdio.h>
void bubble_sort(int a[], int n)
{
int pass, j, temp, swapped;
for (pass = 0; pass < n - 1; pass++)
{
swapped = 0;
for (j = 0; j < n - 1 - pass; j++)
{
if (a[j] > a[j + 1]) /* wrong order: swap */
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
swapped = 1;
}
}
if (swapped == 0) /* no swap: already sorted */
break;
}
}
int main(void)
{
int a[] = {64, 25, 12, 22, 11};
int n = sizeof(a) / sizeof(a[0]);
int i;
bubble_sort(a, n);
printf("Sorted (ascending):");
for (i = 0; i < n; i++)
printf(" %d", a[i]);
printf("\n");
return 0;
}
Output
Sorted (ascending): 11 12 22 25 64
Code Explanation
- The outer loop counts passes. For n elements we need at most n − 1 passes.
- The inner loop compares neighbours
a[j]anda[j + 1]. It stops atn - 1 - passbecause the lastpasselements are already in their final place. - If the left one is bigger, the three-line swap (using
temp) exchanges them. swappedremembers whether any swap happened. A pass with no swap means the array is sorted, so webreakearly. This is the optimized bubble sort.- The function changes the original array, because arrays are passed by address.
How Bubble Sort Works (Pass-by-Pass Dry Run)
Start : 64 25 12 22 11
Pass 1 : 25 12 22 11 | 64 (64 bubbled to the end)
Pass 2 : 12 22 11 | 25 64
Pass 3 : 12 11 | 22 25 64
Pass 4 : 11 | 12 22 25 64 (sorted)
Inside pass 1, step by step: (64,25) swap → (64,12) swap → (64,22) swap → (64,11) swap. Four comparisons, and 64 reaches the end.
Example 2: Selection Sort Program in C
This version also sorts in descending order by changing one comparison.
#include <stdio.h>
void selection_sort(int a[], int n, int ascending)
{
int i, j, pick, temp;
for (i = 0; i < n - 1; i++)
{
pick = i; /* position of smallest (or largest) */
for (j = i + 1; j < n; j++)
{
if (ascending ? a[j] < a[pick] : a[j] > a[pick])
pick = j;
}
if (pick != i) /* one swap per pass at most */
{
temp = a[i];
a[i] = a[pick];
a[pick] = temp;
}
}
}
void print(const int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf(" %d", a[i]);
printf("\n");
}
int main(void)
{
int marks[] = {72, 45, 88, 30, 61, 95};
int n = sizeof(marks) / sizeof(marks[0]);
selection_sort(marks, n, 1);
printf("Ascending :");
print(marks, n);
selection_sort(marks, n, 0);
printf("Descending:");
print(marks, n);
return 0;
}
Output
Ascending : 30 45 61 72 88 95 Descending: 95 88 72 61 45 30
Selection sort dry run (ascending)
Start : 72 45 88 30 61 95
i = 0 : smallest 30 -> swap with 72 : 30 | 45 88 72 61 95
i = 1 : smallest 45 -> no swap : 30 45 | 88 72 61 95
i = 2 : smallest 61 -> swap with 88 : 30 45 61 | 72 88 95
i = 3 : smallest 72 -> no swap : 30 45 61 72 | 88 95
i = 4 : smallest 88 -> no swap : 30 45 61 72 88 | 95
Selection sort does at most one swap per pass. That makes it useful when swapping is costly. See also: C program to sort the array in descending order.
Time Complexity of Bubble Sort and Selection Sort
| Case | Bubble sort (optimized) | Selection sort |
|---|---|---|
| Best (already sorted) | O(n): one pass, no swaps | O(n²): still scans everything |
| Average | O(n²) | O(n²) |
| Worst (reverse sorted) | O(n²) | O(n²) |
| Comparisons (worst) | n(n−1)/2 | n(n−1)/2 always |
| Swaps (worst) | n(n−1)/2 | n − 1 at most |
| Extra memory | O(1) | O(1) |
Difference Between Bubble Sort and Selection Sort
| Point | Bubble sort | Selection sort |
|---|---|---|
| Idea | Swap adjacent pairs | Select the minimum, swap once |
| After pass k | Largest k elements at the end | Smallest k elements at the start |
| Swaps | Many | Few (≤ n − 1) |
| Stops early if sorted? | Yes (with a flag) | No |
| Stable (keeps equal items in order)? | Yes | No (usual version) |
For large data, faster sorts like quick sort and merge sort (O(n log n)) are used. C's library gives qsort() in stdlib.h. You will meet these in Module 16.
Important Points to Remember
- Bubble sort swaps adjacent elements; the biggest goes to the end each pass.
- Selection sort finds the minimum and puts it at the front each pass.
- Both need at most n − 1 passes.
- Both are O(n²); optimized bubble sort is O(n) on sorted input.
- For descending order, just flip the comparison (
>↔<). - Both sort in place (no extra array).
Common Mistakes Beginners Make
| Mistake | What happens | Fix |
|---|---|---|
Inner loop j < n in bubble sort | Compares a[n-1] with a[n]: out of bounds | j < n - 1 - pass |
Swap without temp: a[j] = a[j+1]; a[j+1] = a[j]; | Both get the same value | Use a temp variable |
| Swapping inside the inner loop of selection sort | Becomes a slower, messy sort | Only remember min; swap after the inner loop |
Starting selection inner loop at j = 0 | Disturbs the sorted part | Start at j = i + 1 |
Resetting swapped outside the pass loop | Early exit never happens | Set swapped = 0 at the start of each pass |
Sorting an Array Practice Questions
- Show the array after the first pass of bubble sort on
{5, 1, 4, 2, 8}. - Show the array after the first pass of selection sort on
{5, 1, 4, 2, 8}. - What is the best-case time complexity of optimized bubble sort?
- Which sort makes fewer swaps? Why?
- How many comparisons does bubble sort make on 5 elements in the worst case?
Show answers
{1, 4, 2, 5, 8}.{1, 5, 4, 2, 8}(1 is the smallest, swapped with 5).- O(n), when the array is already sorted.
- Selection sort: at most one swap per pass, so at most n − 1 swaps.
- 5 × 4 / 2 = 10.
Coding Exercise
Sort the marks {67, 89, 45, 89, 72} in descending order with bubble sort and print the top 3 marks.
Show solution
#include <stdio.h>
int main(void)
{
int a[] = {67, 89, 45, 89, 72};
int n = 5, i, j, temp;
for (i = 0; i < n - 1; i++)
{
for (j = 0; j < n - 1 - i; j++)
{
if (a[j] < a[j + 1]) /* < gives descending order */
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
printf("Top 3:");
for (i = 0; i < 3; i++)
printf(" %d", a[i]);
printf("\n");
return 0;
}
Top 3: 89 89 72
Quick Quiz: Bubble Sort and Selection Sort (MCQ)
-
Bubble sort compares:
A) First and last B) Adjacent elements C) Middle elements D) Random pairs
-
After the first pass of bubble sort (ascending), which element is in place?
A) Smallest at the start B) Largest at the end C) Middle D) None
-
Worst-case time complexity of selection sort:
A) O(n) B) O(log n) C) O(n²) D) O(n log n)
-
Maximum number of swaps in selection sort of n elements:
A) n² B) n − 1 C) n(n−1)/2 D) 1
-
Which sort can stop early on an already sorted array?
A) Selection B) Optimized bubble C) Both D) Neither
Show answers
- B: adjacent elements.
- B: largest at the end.
- C: O(n²).
- B: n − 1.
- B: optimized bubble sort.
Quick Revision for Exams and Interviews
Read this before your exam. The highlighted words are the answer.
Must-remember facts
| Bubble sort | Swap adjacent; largest goes to the end |
|---|---|
| Selection sort | Pick the minimum; put it at the front |
| Passes | n − 1 |
| Time (both) | O(n²) |
| Bubble best case | O(n) with swapped flag |
| Fewest swaps | Selection (≤ n − 1) |
| Stable | Bubble yes, selection no |
Frequently asked questions
- What is the difference between bubble sort and selection sort?
- Bubble swaps neighbours many times; selection finds the minimum and swaps once per pass.
- How do you optimize bubble sort?
- Use a swapped flag; if a pass makes no swap, stop.
- How do you sort in descending order?
- Reverse the comparison: use
<instead of>in bubble sort.
Remember
- Bubble = big bubble rises to the end.
- Selection = select the smallest, put it first.
Next Topic
Next lesson: Matrix Operations in C. You will use 2D arrays for matrix addition, multiplication and transpose.