Bubble Sort and Quick Sort

What sorting is

Sorting arranges data in a particular order — ascending or descending — and makes searching and data manipulation more efficient.

[64, 34, 25, 12, 22, 11, 90]  →  [11, 12, 22, 25, 34, 64, 90]

Six characteristics

No single sorting algorithm is best for all situations!

Another version · counting sort

When every value is a small number — here from 1 to 10 — count how many times each value occurs, then print each value that many times. There are no comparisons, and the work is O(n + k) for k possible values.

#include <iostream>

using namespace std;
int a[11];

int main() {
    int n, x;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        a[x]++;
    }
    for (int i = 1; i <= 10; i++)
        cout << i << " " << a[i] << endl;
    for (int i = 1; i <= 10; i++) {
        for (int j = 0; j < a[i]; j++)
            cout << i << " ";
    }
    return 0;
}

10
4 6 4 2 1 2 1 3 4 1

1 3
2 2
3 1
4 3
5 0
6 1
7 0
8 0
9 0
10 0
1 1 1 2 2 3 4 4 4 6

The first ten lines are the counts, the last line is the sorted array. The array a[11] only fits values 1…10 — a value outside that range writes past the end.

How bubble sort works

1. Compare adjacent elements
2. Swap if they are in the wrong order
3. Repeat until no swaps are needed

Bubble sort implementation

#include <iostream>
#include <vector>
using namespace std;

void bubbleSort(vector<int>& arr) {
    int n = arr.size();

    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;

        // Last i elements are already in place
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }

        // If no swapping happened, array is sorted
        if (!swapped)
            break;
    }
}

void printArray(vector<int>& arr) {
    for (int num : arr)
        cout << num << " ";
    cout << endl;
}

int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};

    cout << "Original array: ";
    printArray(arr);

    bubbleSort(arr);

    cout << "Sorted array:   ";
    printArray(arr);

    return 0;
}

Original array: 64 34 25 12 22 11 90
Sorted array:   11 12 22 25 34 64 90

Step by step

Input: [64, 34, 25, 12, 22, 11, 90]

Pass 1:
[64, 34, 25, 12, 22, 11, 90]
[34, 64, 25, 12, 22, 11, 90]  - swap 64, 34
[34, 25, 64, 12, 22, 11, 90]  - swap 64, 25
[34, 25, 12, 64, 22, 11, 90]  - swap 64, 12
[34, 25, 12, 22, 64, 11, 90]  - swap 64, 22
[34, 25, 12, 22, 11, 64, 90]  - swap 64, 11
[34, 25, 12, 22, 11, 64, 90]  - 64 < 90, no swap

Pass 2:
[25, 34, 12, 22, 11, 64, 90]  - swap 34, 25
[25, 12, 34, 22, 11, 64, 90]  - swap 34, 12
[25, 12, 22, 34, 11, 64, 90]  - swap 34, 22
[25, 12, 22, 11, 34, 64, 90]  - swap 34, 11
[25, 12, 22, 11, 34, 64, 90]  - 34 < 64, no swap

Pass 3: [12, 22, 11, 25, 34, 64, 90]
Pass 4: [12, 11, 22, 25, 34, 64, 90]
Pass 5: [11, 12, 22, 25, 34, 64, 90]
Pass 6: [11, 12, 22, 25, 34, 64, 90]  - no swaps, stop

Final: [11, 12, 22, 25, 34, 64, 90]

Pass 6 makes no swaps. Here it is also the last pass the outer loop allows (n − 1 = 6), so the swapped flag saves nothing — but on an already sorted array it stops after 1 pass: that is the O(n) best case.

Bubble sort complexity

Problems with bubble sort

1. Inefficient for large datasets — O(n²) is too slow
2. Too many comparisons — compares adjacent elements again and again
3. Too many swaps — moves elements one position at a time
4. Not suitable for real-world applications with large data

Example: sorting 1,000,000 elements

• Bubble Sort: ~1,000,000,000,000 operations
• Quick Sort: ~20,000,000 operations
• about 50,000 times slower!

Another version · print the array after every pass

The same bubble sort, with one extra loop that prints the array after each pass — the passes above, straight from the program.

#include <iostream>

using namespace std;
int a[1000];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n - 1; i++) { 
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++)
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                swapped = true;
            }
        for (int i = 0; i < n; i++)
            cout << a[i] << " ";
        cout << endl;
        if (swapped == false)
            break;
    }
    return 0;
}

7
64 34 25 12 22 11 90

34 25 12 22 11 64 90
25 12 22 11 34 64 90
12 22 11 25 34 64 90
12 11 22 25 34 64 90
11 12 22 25 34 64 90
11 12 22 25 34 64 90

Another version · compare every pair

Even simpler: compare a[i] with every a[j] after it and swap if they are out of order. After step i the smallest remaining value sits at position i. Also O(n²), but no early stop.

#include <iostream>

using namespace std;
int a[1000];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++) 
        for (int j = i + 1; j < n; j++)
            if (a[i] > a[j])
                swap(a[i], a[j]);
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    return 0;
}

10
56 12 7 87 34 90 1 390 67 95

1 7 12 34 56 67 87 90 95 390

Advantages of the advanced algorithms

1. Much faster: O(n log n) vs O(n²)
2. Scalable: handle millions of elements efficiently
3. Practical: used in real-world systems
4. Divide and conquer: break the problem into smaller subproblems

Performance comparison

Bubble sort ≈ n², quick and merge sort ≈ n · log₂ n.

Quick sort algorithm

1. Choose a pivot element from the array
2. Partition: rearrange the array so elements < pivot are on the left and elements > pivot on the right
3. Recursively apply the same steps to the left and right partitions

Quick sort implementation · the function

int a[1000];

void quick_sort(int l, int r) {
    // Choose middle element as pivot
    int p = a[(l + r) / 2];
    int i = l;
    int j = r;

    // Partition the array
    while (i < j) {
        // Find element on left that should be on right
        while (a[i] < p) i++;
        // Find element on right that should be on left
        while (a[j] > p) j--;

        // Swap elements if needed
        if (i <= j) {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }

    // Recursively sort left partition
    if (l < j)
        quick_sort(l, j);
    // Recursively sort right partition
    if (i < r)
        quick_sort(i, r);
}

Quick sort implementation · main

int main() {
    int n;
    cout << "Enter number of elements: ";
    cin >> n;

    cout << "Enter elements: ";
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    cout << "Original array: ";
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;

    quick_sort(0, n - 1);

    cout << "Sorted array:   ";
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}

6
10 7 8 9 1 5

Enter number of elements: Enter elements: Original array: 10 7 8 9 1 5
Sorted array:   1 5 7 8 9 10

The prompts are printed before the input is read, so in the output they run together on one line.

Step by step

Input: [10, 7, 8, 9, 1, 5]. Pivot is the middle element, a[(l + r) / 2], as in the code.

quick_sort(0, 5): [10, 7, 8, 9, 1, 5], pivot = a[2] = 8
  swap a[0]=10 and a[5]=5 → [5, 7, 8, 9, 1, 10]
  swap a[2]=8 and a[4]=1 → [5, 7, 1, 9, 8, 10]
  recurse on left [0..3] and right [3..5]
  quick_sort(0, 3): [5, 7, 1, 9], pivot = a[1] = 7
    swap a[1]=7 and a[2]=1 → [5, 1, 7, 9, 8, 10]
    recurse on left [0..1] and right [2..3]
    quick_sort(0, 1): [5, 1], pivot = a[0] = 5
      swap a[0]=5 and a[1]=1 → [1, 5, 7, 9, 8, 10]
      nothing left to sort here
    quick_sort(2, 3): [7, 9], pivot = a[2] = 7
      swap a[2]=7 and a[2]=7 (the same cell) → [1, 5, 7, 9, 8, 10]
      nothing left to sort here
  quick_sort(3, 5): [9, 8, 10], pivot = a[4] = 8
    swap a[3]=9 and a[4]=8 → [1, 5, 7, 8, 9, 10]
    recurse on right [4..5]
    quick_sort(4, 5): [9, 10], pivot = a[4] = 9
      swap a[4]=9 and a[4]=9 (the same cell) → [1, 5, 7, 8, 9, 10]
      nothing left to sort here

Final: [1, 5, 7, 8, 9, 10]

Look at the first call: the pointers stop on the same cell, so the left part is [0..3] and the right part is [3..5] — they share index 3. With while (i < j) that can happen; the result is still sorted, only one cell is looked at twice. The common form while (i <= j) always separates the two parts.

Quick sort complexity

Quick sort characteristics

Advantages

• Fastest in practice for the average case
• In-place sorting: uses O(log n) stack space
• Cache-friendly: good locality of reference
• Simple to implement

Disadvantages

• Worst case O(n²): when the pivot is always the smallest or largest
• Not stable: may change the relative order of equal elements
• Recursive: uses stack space

Pivot selection strategies

1. Last element: simple, but can be slow on sorted arrays
2. First element: the same problem as the last element
3. Random element: better average case
4. Median of three: the median of the first, middle and last
5. Median of medians: guaranteed O(n log n), but complex

The code above takes the middle element — on an already sorted array that is the median, the best possible split.

Another version · read, sort, print

The same quick_sort, with a main that only reads n numbers and prints them sorted.

#include <iostream>

using namespace std;
int a[1000];

void quick_sort(int l, int r) {
    int p = a[(l + r) / 2];
    int i = l;
    int j = r;
    while (i < j) {
        while (a[i] < p) i++;
        while (a[j] > p) j--;
        if (i <= j) {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }
    if (l < j) 
        quick_sort(l, j);
    if (i < r)
        quick_sort(i, r);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    quick_sort(0, n - 1);
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    return 0;
}

7
10 13 43 1 534 3 48

1 3 10 13 43 48 534

Problem to topic