Skip to content
StudyFame

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

  1. The outer loop counts passes. For n elements we need at most n − 1 passes.
  2. The inner loop compares neighbours a[j] and a[j + 1]. It stops at n - 1 - pass because the last pass elements are already in their final place.
  3. If the left one is bigger, the three-line swap (using temp) exchanges them.
  4. swapped remembers whether any swap happened. A pass with no swap means the array is sorted, so we break early. This is the optimized bubble sort.
  5. 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

CaseBubble sort (optimized)Selection sort
Best (already sorted)O(n): one pass, no swapsO(n²): still scans everything
AverageO(n²)O(n²)
Worst (reverse sorted)O(n²)O(n²)
Comparisons (worst)n(n−1)/2n(n−1)/2 always
Swaps (worst)n(n−1)/2n − 1 at most
Extra memoryO(1)O(1)

Difference Between Bubble Sort and Selection Sort

PointBubble sortSelection sort
IdeaSwap adjacent pairsSelect the minimum, swap once
After pass kLargest k elements at the endSmallest k elements at the start
SwapsManyFew (≤ n − 1)
Stops early if sorted?Yes (with a flag)No
Stable (keeps equal items in order)?YesNo (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

MistakeWhat happensFix
Inner loop j < n in bubble sortCompares a[n-1] with a[n]: out of boundsj < n - 1 - pass
Swap without temp: a[j] = a[j+1]; a[j+1] = a[j];Both get the same valueUse a temp variable
Swapping inside the inner loop of selection sortBecomes a slower, messy sortOnly remember min; swap after the inner loop
Starting selection inner loop at j = 0Disturbs the sorted partStart at j = i + 1
Resetting swapped outside the pass loopEarly exit never happensSet swapped = 0 at the start of each pass

Sorting an Array Practice Questions

  1. Show the array after the first pass of bubble sort on {5, 1, 4, 2, 8}.
  2. Show the array after the first pass of selection sort on {5, 1, 4, 2, 8}.
  3. What is the best-case time complexity of optimized bubble sort?
  4. Which sort makes fewer swaps? Why?
  5. How many comparisons does bubble sort make on 5 elements in the worst case?
Show answers
  1. {1, 4, 2, 5, 8}.
  2. {1, 5, 4, 2, 8} (1 is the smallest, swapped with 5).
  3. O(n), when the array is already sorted.
  4. Selection sort: at most one swap per pass, so at most n − 1 swaps.
  5. 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)

  1. Bubble sort compares:

    A) First and last   B) Adjacent elements   C) Middle elements   D) Random pairs

  2. 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

  3. Worst-case time complexity of selection sort:

    A) O(n)   B) O(log n)   C) O(n²)   D) O(n log n)

  4. Maximum number of swaps in selection sort of n elements:

    A) n²   B) n − 1   C) n(n−1)/2   D) 1

  5. Which sort can stop early on an already sorted array?

    A) Selection   B) Optimized bubble   C) Both   D) Neither

Show answers
  1. B: adjacent elements.
  2. B: largest at the end.
  3. C: O(n²).
  4. B: n − 1.
  5. 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 sortSwap adjacent; largest goes to the end
Selection sortPick the minimum; put it at the front
Passesn − 1
Time (both)O(n²)
Bubble best caseO(n) with swapped flag
Fewest swapsSelection (≤ n − 1)
StableBubble 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.