PadhaikoAll subjects

Sorting Algorithms

Data Structure and Algorithms (ENCT 252)

Open in the Padhaiko app

7.1 Definition of sorting and its applications

Definition

Sorting

Sorting is the algorithmic process of rearranging a collection of elements (or records) into a permutation ordered according to a comparison relation on a key field:


7.2 Types of sorting: Internal/external sort, stable/unstable sort, in-place/ not in-place sort, adaptive/ non-adaptive sort

Sorting algorithms are classified along four orthogonal dimensions: where data resides during sorting, whether equal-key order is preserved, how much auxiliary memory is needed, and whether existing order in the input speeds up execution.

1. Internal Sort vs. External Sort

Definition

Internal and External Sorting

AspectInternal SortingExternal Sorting
Storage MediumMain memory (RAM) onlySecondary storage (Disk / SSD) + RAM buffers
Dataset SizeBounded by available RAM capacityArbitrarily large (gigabytes to petabytes)
Access PatternFast random access to any indexSequential block-level read/write I/O
Primary BottleneckCPU key comparisons and data movementsDisk I/O seek and transfer time
Representative AlgorithmsQuick Sort, Heap Sort, Insertion Sort, Selection SortExternal -way Merge Sort, Polyphase Merge Sort

2. Stable Sort vs. Unstable Sort

Definition

Stable and Unstable Sorting

Let two distinct records and have equal sort keys () with appearing before () in the original unsorted input:

For example, when sorting student records [(Ram, 85), (Sita, 92), (Hari, 85)] by marks in ascending order, a stable sort preserves (Ram, 85) before (Hari, 85) to yield [(Ram, 85), (Hari, 85), (Sita, 92)], whereas an unstable sort may output [(Hari, 85), (Ram, 85), (Sita, 92)].Stability is essential when sorting multi-attribute tables (e.g., sorting employees alphabetically by name first, and then stably sorting by department).

3. In-Place Sort vs. Not In-Place Sort

Definition

In-Place and Not In-Place Sorting

4. Adaptive Sort vs. Non-Adaptive Sort

Definition

Adaptive and Non-Adaptive Sorting


7.3 Sorting algorithms and its efficiency: Bubble, insertion, selection, shell, quick, merge, radix and heap sorting

1. Bubble Sort

Principle: Bubble Sort is an exchange sort that repeatedly scans the array from left to right, comparing adjacent elements arr[j] and arr[j + 1] and swapping them if arr[j] > arr[j + 1]. After pass (), the -th largest element has "bubbled" to its final position at index . Adding a boolean swapped flag allows the algorithm to stop immediately if a pass makes zero swaps.

Bubble Sort (with Early-Exit Flag) in CC
#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;  /* Array is already sorted */
    }
}

Trace on arr = [5, 1, 4, 2, 8] (Notes Example)

Pass-by-Pass Trace of Bubble Sort on [5, 1, 4, 2, 8]
PassAdjacent Comparisons & SwapsArray After PassSorted Suffix
Pass 1; ; ; no swap[1, 4, 2, 5, 8][8]
Pass 2 no swap; ; no swap[1, 2, 4, 5, 8][5, 8]
Pass 3 no swap; no swap (swapped == 0 stop early)[1, 2, 4, 5, 8][1, 2, 4, 5, 8]

2. Insertion Sort

Principle: Insertion Sort partitions the array into a sorted prefix arr[0 .. i-1] and an unsorted suffix arr[i .. n-1]. In iteration (), it picks key = arr[i], shifts all elements in arr[0 .. i-1] that are strictly greater than key one position to the right, and inserts key into the vacated slot—just like sorting playing cards in hand.

Insertion Sort in CC
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

Trace on arr = [4, 3, 2, 10, 12, 1, 5, 6] (Notes Example)

Step-by-Step Trace of Insertion Sort on [4, 3, 2, 10, 12, 1, 5, 6]
Iteration ()keyElements Shifted RightArray After Insertion
Initial——[4, 3, 2, 10, 12, 1, 5, 6]
Shift [3, 4, 2, 10, 12, 1, 5, 6]
Shift [2, 3, 4, 10, 12, 1, 5, 6]
None ()[2, 3, 4, 10, 12, 1, 5, 6]
None ()[2, 3, 4, 10, 12, 1, 5, 6]
Shift [1, 2, 3, 4, 10, 12, 5, 6]
Shift [1, 2, 3, 4, 5, 10, 12, 6]
Shift [1, 2, 3, 4, 5, 6, 10, 12]

3. Selection Sort

Principle: In pass (), Selection Sort scans the entire unsorted subarray arr[i .. n-1] to find the index minIndex of its smallest element, and swaps arr[minIndex] with arr[i]. This grows the sorted prefix one element at a time using at most swaps.

Selection Sort in CC
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

Trace on arr = [64, 25, 12, 22, 11] (Notes Example)

Pass-by-Pass Trace of Selection Sort on [64, 25, 12, 22, 11]
Pass ()Unsorted SubarrayMinimum FoundSwap PerformedArray After Pass
Initial[64, 25, 12, 22, 11]——[64, 25, 12, 22, 11]
[64, 25, 12, 22, 11] (index )Swap 64 11[11, 25, 12, 22, 64]
[25, 12, 22, 64] (index )Swap 25 12[11, 12, 25, 22, 64]
[25, 22, 64] (index )Swap 25 22[11, 12, 22, 25, 64]
[25, 64] (index )Self-swap 25 25[11, 12, 22, 25, 64]

4. Shell Sort

Principle: Invented by Donald Shell, Shell Sort generalizes Insertion Sort by comparing and shifting elements separated by a gap (increment) sequence (classically Shell's halving sequence ).

Shell Sort in CC
void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

Trace on arr = [33, 31, 40, 8, 12, 17, 25, 42] (, Notes Example)

Pass-by-Pass Trace of Shell Sort on [33, 31, 40, 8, 12, 17, 25, 42]
Pass / GapInterleaved Sublists SortedArray After Pass
Initial—[33, 31, 40, 8, 12, 17, 25, 42]
(), , , [12, 17, 25, 8, 33, 31, 40, 42]
()Even indices (already sorted); Odd indices [12, 8, 25, 17, 33, 31, 40, 42]
()Standard insertion sort: swap , , [8, 12, 17, 25, 31, 33, 40, 42]

5. Quick Sort

Principle: Quick Sort is a divide-and-conquer exchange sort:

  1. Divide (Partition): Choose a pivot element from arr[low .. high] and rearrange the subarray in-place so that all elements lie to the left of index pi, the pivot itself is placed at its final sorted index pi, and all elements lie to the right of pi.
  2. Conquer: Recursively apply quickSort(arr, low, pi - 1) and quickSort(arr, pi + 1, high).
  3. Combine: Nothing to do—the array is sorted in place.
Quick Sort with Partitioning in CC
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];  /* Last element chosen as pivot */
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Trace on arr = [24, 27, 19, 9, 29, 14] (First-Element Pivot from Notes)

  1. Partitioning [24, 27, 19, 9, 29, 14] with pivot = 24:
    • Scan x right from index (A[1] = 27 > 24) and y left from index (A[5] = 14 < 24); swap .
    • Advance x across to index (29 > 24) and y left to index (9 < 24); pointers cross at index , so swap pivot A[0] = 24 with A[3] = 19/9 to place at index :
  1. Left Subarray [19, 14, 9] with pivot = 19:
    • Swap 19 with 9 ; remaining [9, 14] with pivot is already in order .
  2. Right Subarray [29, 27] with pivot = 29:
    • Swap 29 with 27 .
  3. Final Sorted Array: [9, 14, 19, 24, 27, 29].

6. Merge Sort

Principle: Merge Sort is a stable divide-and-conquer algorithm with guaranteed performance:

  1. Divide: Split the array A[left .. right] at midpoint mid = (left + right) / 2 into two halves of sizes and .
  2. Conquer: Recursively sort A[left .. mid] and A[mid + 1 .. right].
  3. Combine (Merge): Merge the two sorted subarrays into a single sorted sequence in linear time using two pointers i and j.
Merge Sort in CC
void merge(int A[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];

    for (int i = 0; i < n1; i++) L[i] = A[left + i];
    for (int j = 0; j < n2; j++) R[j] = A[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) A[k++] = L[i++];
        else              A[k++] = R[j++];
    }
    while (i < n1) A[k++] = L[i++];
    while (j < n2) A[k++] = R[j++];
}

void mergeSort(int A[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(A, left, mid);
        mergeSort(A, mid + 1, right);
        merge(A, left, mid, right);
    }
}

Trace on A = [24, 27, 19, 9, 29, 14] (Notes Example)

Divide-and-Conquer Split and Merge Tree for [24, 27, 19, 9, 29, 14]Text
                       [24, 27, 19, 9, 29, 14]
                       /                     \
             [24, 27, 19]                   [9, 29, 14]          <-- Divide
              /        \                     /        \
           [24]      [27, 19]              [9]      [29, 14]
                      /    \                         /    \
                   [27]    [19]                   [29]    [14]
                      \    /                         \    /
           [24]      [19, 27]              [9]      [14, 29]     <-- Merge
              \        /                     \        /
             [19, 24, 27]                   [9, 14, 29]
                       \                     /
                       [9, 14, 19, 24, 27, 29]                   <-- Final Sorted

7. Radix Sort

Principle: Radix Sort is a non-comparative integer sorting algorithm. Instead of comparing full keys, LSD (Least Significant Digit) Radix Sort processes numbers digit by digit from the units place () up to the most significant digit (), applying a stable bucket/counting sort at every digit pass.

LSD Radix Sort (Using Counting Sort Subroutine) in CC
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max) max = arr[i];
    return max;
}

void countSort(int arr[], int n, int exp) {
    int output[n], count[10] = {0};
    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

void radixSort(int arr[], int n) {
    int max = getMax(arr, n);
    for (int exp = 1; max / exp > 0; exp *= 10)
        countSort(arr, n, exp);
}

Trace on arr = [170, 45, 75, 90, 802, 24, 2, 66] (Notes Example)

The maximum number is , which has decimal digits ( buckets ):

Digit-by-Digit Passes of LSD Radix Sort
PassDigit Place ()Non-Empty Buckets ()Array After Pass
Initial——[170, 45, 75, 90, 802, 24, 2, 66]
Pass 1Units (), , , , [170, 90, 802, 2, 24, 45, 75, 66]
Pass 2Tens (), , , , , [802, 2, 24, 45, 66, 170, 75, 90]
Pass 3Hundreds (), , [2, 24, 45, 66, 75, 90, 170, 802]

8. Heap Sort

Definition

Binary Heap and Heap Property

A binary heap is a complete binary tree stored compactly in an array a[0 .. n-1] without pointers. For any node at -based index :

Two Phases of Heap Sort (Ascending Order):

  1. Phase 1 — Build Max-Heap ( time): Starting from the last internal node down to , call heapify(a, n, i) to sift smaller elements down and establish the Max-Heap property.
  2. Phase 2 — Repeated Extraction ( time): For down to :
    • Swap the maximum element at root a[0] with the last heap element a[i] (placing the maximum into its final sorted position at the end of the array).
    • Reduce the active heap size to and call heapify(a, i, 0) in time to restore the Max-Heap property.
Heap Sort in CC
void heapify(int a[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && a[left] > a[largest])
        largest = left;
    if (right < n && a[right] > a[largest])
        largest = right;

    if (largest != i) {
        int temp = a[i];
        a[i] = a[largest];
        a[largest] = temp;
        heapify(a, n, largest);
    }
}

void heapSort(int a[], int n) {
    /* Phase 1: Build Max-Heap bottom-up */
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(a, n, i);

    /* Phase 2: Extract max one by one */
    for (int i = n - 1; i > 0; i--) {
        int temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        heapify(a, i, 0);
    }
}

Trace on a = [22, 13, 17, 11, 10, 14, 12] (Notes Example)

Step-by-Step Trace of Heap Sort on [22, 13, 17, 11, 10, 14, 12]
StepOperationActive HeapSorted SuffixFull Array State
BuildAlready satisfies Max-Heap (; ; )[22, 13, 17, 11, 10, 14, 12][][22, 13, 17, 11, 10, 14, 12]
1Swap ; heapify size ()[17, 13, 14, 11, 10, 12][22][17, 13, 14, 11, 10, 12, 22]
2Swap ; heapify size ()[14, 13, 12, 11, 10][17, 22][14, 13, 12, 11, 10, 17, 22]
3Swap ; heapify size ()[13, 11, 12, 10][14, 17, 22][13, 11, 12, 10, 14, 17, 22]
4Swap ; heapify size ()[12, 11, 10][13, 14, 17, 22][12, 11, 10, 13, 14, 17, 22]
5Swap ; heapify size ()[11, 10][12, 13, 14, 17, 22][11, 10, 12, 13, 14, 17, 22]
6Swap ; size remaining[10][11, 12, 13, 14, 17, 22][10, 11, 12, 13, 14, 17, 22]

Master Comparison of All 8 Sorting Algorithms

Efficiency and Classification Summary of Sorting Algorithms
AlgorithmBest TimeAverage TimeWorst TimeAuxiliary SpaceStable?In-Place?Adaptive?
Bubble SortYesYesYes (with flag)
Insertion SortYesYesYes
Selection SortNoYesNo
Shell SortNoYesYes
Quick SortNoYesNo
Merge SortYesNoNo
Radix SortYesNoNo
Heap SortNoYesNo

Worked Examples

Example 7.1

7.1 (8 marks)

Sort the -element array 92, 83, 22, 49, 36, 98, 12, 9, 70, 51 in ascending order using both (a) Insertion Sort and (b) Shell Sort (with halving gaps ).

Part (a) — Tracing Insertion Sort pass by pass:

  • Initial: [92, 83, 22, 49, 36, 98, 12, 9, 70, 51]
  • (key = 83): [83, 92, 22, 49, 36, 98, 12, 9, 70, 51]
  • (key = 22): [22, 83, 92, 49, 36, 98, 12, 9, 70, 51]
  • (key = 49): [22, 49, 83, 92, 36, 98, 12, 9, 70, 51]
  • (key = 36): [22, 36, 49, 83, 92, 98, 12, 9, 70, 51]
  • (key = 98): [22, 36, 49, 83, 92, 98, 12, 9, 70, 51] (no shift)
  • (key = 12): [12, 22, 36, 49, 83, 92, 98, 9, 70, 51]
  • (key = 9): [9, 12, 22, 36, 49, 83, 92, 98, 70, 51]
  • (key = 70): [9, 12, 22, 36, 49, 70, 83, 92, 98, 51]
  • (key = 51): [9, 12, 22, 36, 49, 51, 70, 83, 92, 98]

Part (b) — Tracing Shell Sort with , , and :

  1. Pass 1 (): Compare pairs :
    • ; ; ; ; .
    • Array after : [92, 12, 9, 49, 36, 98, 83, 22, 70, 51].
  2. Pass 2 (): Insertion-sort the two interleaved sublists of stride :
    • Even indices : .
    • Odd indices : .
    • Interleaved array after : [9, 12, 36, 22, 70, 49, 83, 51, 92, 98].
  3. Pass 3 (): Standard insertion sort on the nearly sorted array swaps only , , and shifts past :
    • Final sorted array: [9, 12, 22, 36, 49, 51, 70, 83, 92, 98].
Answer:

Both Insertion Sort and Shell Sort () yield the sorted array [9, 12, 22, 36, 49, 51, 70, 83, 92, 98].

Example 7.2

7.2 (8 marks)

Trace Quick Sort step-by-step on the -element array 30, 25, 78, 19, 48, 28, 21, 44, 120 using the first element of each subarray as the pivot.

First partition on A[0..8] = [30, 25, 78, 19, 48, 28, 21, 44, 120] with pivot = 30: Elements are ( elements), so pivot 30 lands at index :

  • Pointer x stops at A[2] = 78 (); pointer y stops at A[6] = 21 (); swap .
  • Pointer x stops at A[4] = 48 (); pointer y stops at A[5] = 28 (); swap .
  • Pointers cross at index (A[4] = 28); swap pivot A[0] = 30 with A[4] = 28:

Recursively sorting Left Subarray A[0..3] = [28, 25, 21, 19]:

  • pivot = 28: all of are ; swap 28 with 19 .
  • On [19, 25, 21] with pivot = 19: both , so 19 stays at index .
  • On [25, 21] with pivot = 25: swap 25 with 21 .
  • Left half is now completely sorted: [19, 21, 25, 28].

Recursively sorting Right Subarray A[5..8] = [48, 78, 44, 120]:

  • pivot = 48: x stops at 78 (), y stops at 44 (); swap ; swap pivot 48 with 44 .
  • Left sub-partition [44] has element (sorted).
  • Right sub-partition [78, 120] with pivot = 78 has , so 78 stays at index and [120] is sorted.
Answer:

The sorted array produced by Quick Sort is [19, 21, 25, 28, 30, 44, 48, 78, 120].

Example 7.3

7.3 (8 marks)

Sort the -element array 42, 36, 56, 21, 63, 72, 62, 15 using Max-Heap Sort, showing both the bottom-up Max-Heap construction and each extraction + heapify step.

Phase 1 — Building the Max-Heap bottom-up (, start at down to ): Initial array: [42, 36, 56, 21, 63, 72, 62, 15].

  • (a[3] = 21, child a[7] = 15): , no change.
  • (a[2] = 56, children a[5] = 72, a[6] = 62): swap .
  • (a[1] = 36, children a[3] = 21, a[4] = 63): swap .
  • (a[0] = 42, children 63, 72): swap at index , then compare with children of index (56, 62) and swap at index :

Phase 2 — Extracting the maximum one by one and restoring the Max-Heap:

Heap Sort Extraction and Heapify Trace
StepSwap Root a[0] with a[i]Heap SizeSift-Down Path in heapifyArray After heapify
1 ()[63, 36, 62, 21, 15, 56, 42 | 72]
2 ()[62, 36, 56, 21, 15, 42 | 63, 72]
3 ()[56, 36, 42, 21, 15 | 62, 63, 72]
4 ()[42, 36, 15, 21 | 56, 62, 63, 72]
5 ()[36, 21, 15 | 42, 56, 62, 63, 72]
6 ()[21, 15 | 36, 42, 56, 62, 63, 72]
7 ()Done[15, 21, 36, 42, 56, 62, 63, 72]
Answer:
  • Constructed Max-Heap: [72, 63, 62, 21, 36, 56, 42, 15].
  • Final Sorted Array: [15, 21, 36, 42, 56, 62, 63, 72].
Example 7.4

7.4 (8 marks)

Sort the numbers 14, 2, 205, 978, 121, 4, 34, 1110, 666, 840 using LSD Radix Sort, showing the array state after each digit pass.

Determining the number of passes: The largest number is , which has decimal digits. Pad each number conceptually to digits: 0014, 0002, 0205, 0978, 0121, 0004, 0034, 1110, 0666, 0840.

Executing the stable bucket passes ():

4-Pass LSD Radix Sort Trace
PassDigit PlaceBucket Contents ()Array After Pass
Pass 1Units (), , , , , , [1110, 840, 121, 2, 14, 4, 34, 205, 666, 978]
Pass 2Tens (), , , , , , [2, 4, 205, 1110, 14, 121, 34, 840, 666, 978]
Pass 3Hundreds (), , , , , [2, 4, 14, 34, 1110, 121, 205, 666, 840, 978]
Pass 4Thousands (), [2, 4, 14, 34, 121, 205, 666, 840, 978, 1110]
Answer:

After passes (units, tens, hundreds, thousands), the sorted sequence is [2, 4, 14, 34, 121, 205, 666, 840, 978, 1110].


Exercises

Exercises

Question 1

Differentiate between internal sorting and external sorting. Consider the following Max-Heap: 50, 30, 20, 15, 10, 8, 16. Insert a new node with value 55 into this Max-Heap and show the step-by-step sifting-up process.

Difference between internal and external sorting:

  • Internal sorting holds all records in main memory (RAM) and uses random-access comparisons (e.g., Quick Sort, Heap Sort, Insertion Sort).
  • External sorting handles datasets larger than RAM stored on disk/SSD by sorting memory-sized chunks into runs and merging them via -way External Merge Sort to minimize disk I/O.

Inserting 55 into Max-Heap a[0..6] = [50, 30, 20, 15, 10, 8, 16]:

  1. Append at next leaf index :
  1. Sift up (compare with parent , where a[3] = 15): Since , swap a[7] and a[3]:
  1. Compare with parent , where a[1] = 30: Since , swap a[3] and a[1]:
  1. Compare with root , where a[0] = 50: Since , swap a[1] and a[0]:
Answer:

Internal sort runs entirely in RAM whereas external sort processes disk-resident datasets via run generation and -way merging. Inserting 55 at index sifts up along to yield the Max-Heap [55, 50, 20, 30, 10, 8, 16, 15].

Question 2

Explain Selection Sort with its algorithm and time complexity. Trace Selection Sort step-by-step on the data sequence 40, 90, 20, -10, 30, 5, 60, 100, 80 and compute the exact number of key comparisons performed.

Algorithm and complexity of Selection Sort: In pass (), Selection Sort scans arr[i .. n-1] to find the index minIndex of the minimum element and swaps arr[i] with arr[minIndex]. For elements, it always performs:

Pass-by-pass trace on [40, 90, 20, -10, 30, 5, 60, 100, 80]:

  • Pass 1 (): Min in arr[0..8] is -10 (index ). Swap 40 -10: [-10, 90, 20, 40, 30, 5, 60, 100, 80]
  • Pass 2 (): Min in arr[1..8] is 5 (index ). Swap 90 5: [-10, 5, 20, 40, 30, 90, 60, 100, 80]
  • Pass 3 (): Min in arr[2..8] is 20 (already at index ): [-10, 5, 20, 40, 30, 90, 60, 100, 80]
  • Pass 4 (): Min in arr[3..8] is 30 (index ). Swap 40 30: [-10, 5, 20, 30, 40, 90, 60, 100, 80]
  • Pass 5 (): Min in arr[4..8] is 40 (already at index ): [-10, 5, 20, 30, 40, 90, 60, 100, 80]
  • Pass 6 (): Min in arr[5..8] is 60 (index ). Swap 90 60: [-10, 5, 20, 30, 40, 60, 90, 100, 80]
  • Pass 7 (): Min in arr[6..8] is 80 (index ). Swap 90 80: [-10, 5, 20, 30, 40, 60, 80, 100, 90]
  • Pass 8 (): Min in arr[7..8] is 90 (index ). Swap 100 90: [-10, 5, 20, 30, 40, 60, 80, 90, 100]
Answer:

Selection Sort runs in time ( comparisons for ) and produces the sorted sequence [-10, 5, 20, 30, 40, 60, 80, 90, 100].

Question 3

Explain Merge Sort and trace all divide and merge steps to sort the data sequence 85, 76, 46, 92, 30, 41, 12.

Divide-and-conquer phases of Merge Sort:

  1. Split ([85, 76, 46, 92, 30, 41, 12]):
    • Left half ( elements): [85, 76, 46, 92] [85, 76] and [46, 92] [85], [76], [46], [92].
    • Right half ( elements): [30, 41, 12] [30, 41] and [12] [30], [41], [12].

Bottom-up Merge Steps:

  • Level 1 merges (pairs):
    • Merge [85] and [76] .
    • Merge [46] and [92] .
    • Merge [30] and [41] (and [12] stays [12]).
  • Level 2 merges:
    • Merge [76, 85] and [46, 92] .
    • Merge [30, 41] and [12] .
  • Level 3 final merge:
    • Merge [46, 76, 85, 92] and [12, 30, 41] .
Answer:

Merge Sort recursively splits the -element array to singletons and merges them in time to yield [12, 30, 41, 46, 76, 85, 92].

Question 4

Compare Quick Sort and Merge Sort. Then trace the sorting steps in LSD Radix Sort for the data: 345, 654, 934, 123, 056, 072, 555, 808, 911, 057.

Comparison between Quick Sort and Merge Sort:

AspectQuick SortMerge Sort
PartitioningBy value around a pivot (unequal split sizes possible)By index at the exact midpoint
Worst-Case Time (when pivot is extreme element) (guaranteed in all cases)
Auxiliary Space stack space (in-place) auxiliary merge buffer (not in-place)
StabilityUnstableStable

Tracing 3-pass LSD Radix Sort on 345, 654, 934, 123, 056, 072, 555, 808, 911, 057:

  1. Pass 1 — Units Digit ():
    • , , , , , , , .
    • After Pass 1: [911, 072, 123, 654, 934, 345, 555, 056, 057, 808].
  2. Pass 2 — Tens Digit ():
    • , , , , , , .
    • After Pass 2: [808, 911, 123, 934, 345, 654, 555, 056, 057, 072].
  3. Pass 3 — Hundreds Digit ():
    • , , , , , , .
    • After Pass 3: [056, 057, 072, 123, 345, 555, 654, 808, 911, 934].
Answer:

Quick Sort is in-place ( stack) and unstable with worst case, whereas Merge Sort is stable with worst case and extra space. LSD Radix Sort yields [056, 057, 072, 123, 345, 555, 654, 808, 911, 934].

Question 5

Provide the best-case, average-case, and worst-case time complexities in Big-Oh notation for Bubble Sort, Insertion Sort, Selection Sort, and Merge Sort. Then trace Bubble Sort pass-by-pass on 16, 36, 24, 37, 15 and state the total number of swaps performed.

Asymptotic time complexity table:

Best, Average, and Worst-Case Time Complexities
AlgorithmBest CaseAverage CaseWorst Case
Bubble Sort
Insertion Sort
Selection Sort
Merge Sort

Tracing Bubble Sort on [16, 36, 24, 37, 15] ():

  • Pass 1 ( comparisons):
    • no swap; ; no swap; ( swaps).
  • Pass 2 ( comparisons):
    • no swap; no swap; ( swap).
  • Pass 3 ( comparisons):
    • no swap; ( swap).
  • Pass 4 ( comparison):
    • ( swap).
  • Total comparisons ; total swaps .
Answer:

Bubble Sort performs comparisons and swaps across passes to produce [15, 16, 24, 36, 37].

Question 6

Explain why Shell Sort is considered an adaptive improvement over Insertion Sort, and trace Shell Sort on the -element array 36, 25, 40, 2, 7, 80, 15 using gaps .

Why Shell Sort improves upon Insertion Sort: Standard Insertion Sort moves elements only position per shift, so an element far from its destination requires up to shifts. Shell Sort first -sorts the array with large strides (), moving elements across long distances in a single exchange so that the final pass encounters an almost-sorted array and runs in near-linear time.

Tracing Shell Sort on [36, 25, 40, 2, 7, 80, 15] ():

  1. Pass 1 ():
    • Sublist 0 (indices ): .
    • Sublist 1 (indices ): .
    • Sublist 2 (indices ): .
    • Array after : [2, 7, 40, 15, 25, 80, 36].
  2. Pass 2 ():
    • Standard insertion sort shifts 40 past 15, 25 () and shifts 40, 80 past 36:
    • Final sorted array: [2, 7, 15, 25, 36, 40, 80].
Answer:

After , the array becomes [2, 7, 40, 15, 25, 80, 36]; after , the final sorted array is [2, 7, 15, 25, 36, 40, 80].

Past exam questions for Data Structure and Algorithms

← GraphsSearching Algorithms →