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

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

Rearranging array elements into ascending or descending order is called sorting. It's a fundamental building block 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 start with bubble β†’ selection β†’ insertion. All three use nested loops β€” great practice for reinforcing for-loop fundamentals.

Bubble Sort β€” Compare and Swap Adjacent Elements

Compare adjacent elements and swap them if they're in the wrong order. Repeating this makes larger values "bubble" toward 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 quickly as n grows
Advantage
The simplest sort to implement β€” great for learning.

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

From the unsorted section, find the minimum and swap it into the first unsorted slot. Repeat until everything is in place.
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 with fewer swaps
Advantage
Minimal element moves; conceptually very clear.

Insertion Sort β€” Sorting Cards in Your Hand

Treat the left portion as already sorted. For each remaining element, insert it into the right spot. Think of 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 case, O(n) on nearly-sorted data (very fast)
Advantage
Great for small or nearly-sorted inputs. Also stable.

Sort Visualizer

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

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 31: Data Structures
Next lesson →
Lesson 33: Compile Errors

Frequently Asked Questions

Q. Which sorting algorithm is the fastest overall?

A. In practice, Quicksort is the fastest for most workloads. Its average time complexity is O(n log n), and implementations are highly efficient. Depending on the data, merge sort or heap sort can pull ahead. Production 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 (it's what the standard library's qsort() uses), and merge sort is great for linked lists and external sorting. The usual learning path 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, tied students 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 as input size n grows. With O(nΒ²), doubling n quadruples the time; O(n log n) grows far more slowly. O(n) is linear, O(n log n) is fast in practice, and O(nΒ²) or worse is usually only acceptable for small inputs.

Review 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, yielding 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 around a pivot, giving O(n log n) on average. In the worst case, it 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 preserves the relative order of elements with equal keys. Merge sort is stable; quicksort is not.

Share this article
Share on X Share on Facebook