C DSA Sorting

What is Sorting?

Sorting means putting values in order, for example from smallest to largest.

Sorted data is easier to read, and much faster to search. Remember: binary search only works on sorted data!

Bubble Sort

Bubble sort is one of the simplest sorting algorithms:

1. Compare the first two values. If the first one is bigger, swap them.
2. Move one step to the right, and compare the next two values. Keep going to the end of the array.
3. Now the biggest value has "bubbled up" to the end. It is in the right place.
4. Repeat for the rest of the array.

One trip through the array is called a pass. Here is the first pass, step by step:

After one pass, the biggest value (8) is at the end. The next pass does the same for the rest of the array, and so on.

Run the simulation below to see how bubble sort puts the same array in order, all the way to the end. The index goes along the bottom, and the value goes up: the bigger the value, the taller the column:

The two yellow columns are being compared. If the left one is bigger, they swap. After each pass, one more column turns green: it is in its final place.

The program below prints the array after every pass, so you can watch it get sorted:

#include <stdio.h>

void printArray(int arr[], int length) {
  for (int i = 0; i < length; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

int main() {
  int numbers[] = {5, 3, 8, 1, 4};
  int length = sizeof(numbers) / sizeof(numbers[0]);

  printf("Start:  ");
  printArray(numbers, length);

  for (int i = 0; i < length - 1; i++) {
    // Compare each pair of neighbors
    for (int j = 0; j < length - 1 - i; j++) {
      if (numbers[j] > numbers[j + 1]) {
        // Swap them
        int temp = numbers[j];
        numbers[j] = numbers[j + 1];
        numbers[j + 1] = temp;
      }
    }
    printf("Pass %d: ", i + 1);
    printArray(numbers, length);
  }

  return 0;
}

Start:  5 3 8 1 4
Pass 1: 3 5 1 4 8
Pass 2: 3 1 4 5 8
Pass 3: 1 3 4 5 8
Pass 4: 1 3 4 5 8 

Example Explained

• The outer loop (i) runs one pass at a time.
• The inner loop (j) compares each pair of neighbors, and swaps them if they are in the wrong order.
• To swap two values, we need a third variable, temp, to hold one value for a moment.
• After each pass, one more value is in its final place at the end. That is why the inner loop stops at length - 1 - i.

Make It Faster: Stop Early

Look at the result above again. The array was already sorted after Pass 3, but Pass 4 still ran.

Here is a smart trick: if a whole pass makes no swaps, the array is sorted, and we can stop. A variable called swapped remembers if a swap happened:

#include <stdio.h>

void printArray(int arr[], int length) {
  for (int i = 0; i < length; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

int main() {
  int numbers[] = {1, 2, 4, 3, 5};
  int length = sizeof(numbers) / sizeof(numbers[0]);

  for (int i = 0; i < length - 1; i++) {
    int swapped = 0; // No swaps yet in this pass

    for (int j = 0; j < length - 1 - i; j++) {
      if (numbers[j] > numbers[j + 1]) {
        int temp = numbers[j];
        numbers[j] = numbers[j + 1];
        numbers[j + 1] = temp;
        swapped = 1;
      }
    }

    printf("Pass %d: ", i + 1);
    printArray(numbers, length);

    if (swapped == 0) {
      printf("No swaps, so the array is sorted. Stop!\n");
      break;
    }
  }

  return 0;
}

Pass 1: 1 2 3 4 5
Pass 2: 1 2 3 4 5
No swaps, so the array is sorted. Stop!

This array was almost sorted, so we stopped after 2 passes instead of 4.

Sort the Easy Way: qsort()

Bubble sort is great for learning, but it is slow for large arrays. In real programs, use the qsort() function from <stdlib.h>. It is fast, and it is already written for you!

You only need to give qsort() a small callback function that compares two values:

#include <stdio.h>
#include <stdlib.h>

// Tells qsort() how to compare two numbers
int compare(const void *a, const void *b) {
  return (*(int*)a - *(int*)b);
}

int main() {
  int numbers[] = {64, 25, 12, 22, 11};
  int length = sizeof(numbers) / sizeof(numbers[0]);

  qsort(numbers, length, sizeof(int), compare);

  for (int i = 0; i < length; i++) {
    printf("%d ", numbers[i]);
  }
  printf("\n");

  return 0;
}

11 12 22 25 64 

Example Explained

• qsort() needs four things: the array, the number of items, the size of one item, and the compare function.
• *(int*)a turns the general pointer a into an int pointer, and reads the number it points to.
• The compare function returns a negative number if a should come first, a positive number if b should come first, and 0 if they are equal.

qsort() usually uses a fast algorithm called Quick Sort. You can learn how it works in our DSA Quick Sort chapter.

Summary

• Sorting puts values in order. Sorted data is easier to read and faster to search.
• Bubble sort compares neighbors and swaps them if they are in the wrong order.
• If a pass makes no swaps, the array is sorted, and bubble sort can stop early.
• In real programs, use qsort(). It is fast and ready to use.

So far, you have searched and sorted arrays. Now it is time to build your own data structures, starting with the stack. That is the next chapter!