πŸ‡―πŸ‡΅ ζ—₯本θͺž | πŸ‡ΊπŸ‡Έ English
Advertisement

Sorting Algorithms

Bubble, selection, and insertion sort in C, visualized step by step.

πŸ“– What to learn on this page
βœ… Must-know essentials
  • Bubble sort: swap adjacent pairs
  • Selection sort: pull the min to the front
  • Standard-library qsort
⭐ Read if you have time
  • Quicksort, mergesort
  • Complexity: O(nΒ²) vs O(n log n)
  • Stable vs unstable sorts

What is Sorting? β€” Rearranging Data in Order

Reordering array elements into ascending or descending order is called sorting. It's a fundamental technique for fast searching and organizing data.

Common sorting algorithms

AlgorithmAverage complexityCharacteristic
Bubble sortO(nΒ²)Simplest; compare and swap adjacent items
Selection sortO(nΒ²)Find the minimum and place it at the front
Insertion sortO(nΒ²)Like sorting cards in hand; fast on nearly-sorted data
QuicksortO(n log n)Fastest in practice; C's qsort() is based on it
Beginners should understand bubble β†’ selection β†’ insertion first. All three are written with nested loops β€” a great review of for loops.

Bubble Sort β€” Compare and Swap Adjacent Elements

Compare adjacent elements and swap them if they are in the wrong order. Repeating this makes larger values "bubble" to the end.
void bubbleSort(int a[], int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - 1 - i; j++) {
      if (a[j] > a[j+1]) {
        // swap
        int tmp = a[j];
        a[j] = a[j+1];
        a[j+1] = tmp;
      }
    }
  }
}

How it proceeds

[5 3 8 1 4] β†’ 5>3? swap β†’ [3 5 8 1 4]
[3 5 8 1 4] β†’ 5>8? no β†’ [3 5 8 1 4]
[3 5 8 1 4] β†’ 8>1? swap β†’ [3 5 1 8 4]
[3 5 1 8 4] β†’ 8>4? swap β†’ [3 5 1 4 8] ← 8 is in place!
... repeat for the remaining elements
Complexity
O(nΒ²) β€” slows down rapidly as the size grows
Advantage
Simplest to implement β€” great for learning.

Selection Sort β€” Find the Min, Put It at the Front

From the unsorted portion, find the minimum and swap it into the first unsorted slot. Repeat.
void selectionSort(int a[], int n) {
  for (int i = 0; i < n - 1; i++) {
    int minIdx = i;
    for (int j = i + 1; j < n; j++) {
      if (a[j] < a[minIdx])
        minIdx = j;      // track the minimum index
    }
    // swap position i with the minimum
    int tmp = a[i];
    a[i] = a[minIdx];
    a[minIdx] = tmp;
  }
}

How it proceeds

[5 3 8 1 4] β†’ min=1 β†’ swap(5,1) β†’ [1 3 8 5 4]
[1 3 8 5 4] β†’ min=3 β†’ unchanged β†’ [1 3 8 5 4]
[1 3 8 5 4] β†’ min=4 β†’ swap(8,4) β†’ [1 3 4 5 8]
[1 3 4 5 8] β†’ min=5 β†’ unchanged β†’ [1 3 4 5 8] Done!
Complexity
O(nΒ²) β€” same as bubble, but fewer swaps
Advantage
Minimal number of element moves; conceptually very clear.

Insertion Sort β€” Sorting Cards in Your Hand

Treat the left part as already sorted. For each remaining element, insert it into its correct position. It's like arranging cards as you pick them up.
void insertionSort(int a[], int n) {
  for (int i = 1; i < n; i++) {
    int key = a[i];      // value to insert
    int j = i - 1;
    while (j >= 0 && a[j] > key) {
      a[j+1] = a[j];    // shift right
      j--;
    }
    a[j+1] = key;        // place at the correct spot
  }
}

How it proceeds

[5| 3 8 1 4] β†’ insert 3 β†’ [3 5| 8 1 4]
[3 5| 8 1 4] β†’ 8 stays β†’ [3 5 8| 1 4]
[3 5 8| 1 4] β†’ 1 goes to the front β†’ [1 3 5 8| 4]
[1 3 5 8| 4] β†’ 4 between 3 and 5 β†’ [1 3 4 5 8] Done!
Everything left of | is already sorted.
Complexity
O(nΒ²) worst, O(n) when nearly sorted (very fast)
Advantage
Great for small or nearly-sorted inputs. Also a stable sort.

Sort Visualizer

Pick an algorithm and click Start to watch the array being sorted, step by step.
Click Start to begin the animation.
Comparisons: 0 Swaps: 0
Advertisement

Related lessons

Loops, Arrays, Strings
Arrays
Declaring, initializing, and accessing C arrays.
Algorithms
Data Structures
Linked list, stack, and queue.
Loops, Arrays, Strings
for / while Loops
Working with for and while loops.
← Previous lesson
Lesson 29: Data Structures
Next lesson →
Lesson 31: Compile Errors

Frequently Asked Questions

Q. Which sorting algorithm is the fastest overall?

A. In general, Quicksort is the fastest. Average time complexity is O(n log n) and implementations are efficient. Depending on the data, merge sort or heap sort can be faster. Professional code picks whichever fits the situation best.

Q. When should I use which sort?

A. Bubble sort is for teaching; insertion sort excels on nearly sorted data; quicksort covers most general use (qsort() in the standard library); merge sort is great for linked lists and external sorting. The usual learning order is bubble β†’ insertion β†’ quicksort.

Q. What is a stable sort?

A. A stable sort preserves the relative order of elements that compare equal. For example, when sorting students by score, ties keep their original order. Stable: bubble, insertion, merge. Unstable: selection, quicksort, heap.

Q. What does O(n log n) mean?

A. Time complexity describes how runtime grows with input size n. With O(nΒ²), doubling n quadruples the time; O(n log n) grows much more slowly. O(n) is linear, O(n log n) is practically fast, and anything O(nΒ²) or worse is usually only acceptable for small inputs.

Quick Quiz

Check your understanding of this lesson.

Q1. What is the worst-case complexity of bubble sort?

O(n)
O(n log n)
O(nΒ²)

Bubble sort repeatedly compares and swaps adjacent elements, giving O(nΒ²) in the worst case.

Q2. What is the average-case complexity of quicksort?

O(n)
O(n log n)
O(nΒ²)

Quicksort uses divide-and-conquer with a pivot, giving O(n log n) on average. The worst case can degrade to O(nΒ²).

Q3. What is a stable sort?

A sort that does not crash
A sort that preserves the order of equal elements
A sort that is always the fastest

A stable sort keeps the relative order of elements with equal keys. Merge sort is stable; quicksort is not.

Share this article
Share on X Share on Facebook