Elementary sorts

ACompressed recap

🧾

Bubble sort: adjacent swaps, pass k fixes the k-th largest, ≤ n(n−1)/2 comparisons, n − 1 with early exit on sorted input, swaps = inversions, stable. Selection sort: always n(n−1)/2 comparisons, ≤ n − 1 swaps, not stable. Insertion sort: shifts = inversions, Θ(n + I), best Θ(n), worst Θ(n²); binary insertion cuts only comparisons. Inversions: pairs i < j with A[i] > A[j], max n(n−1)/2. Stable: insertion, bubble, merge; in-place: bubble, selection, insertion, heap, quick.

BMerged rule card

3.1.1 Bubble sort and selection sort: passes, comparisons, swaps

• Bubble: adjacent swaps; pass k fixes the k-th largest; comparisons ≤ n(n−1)/2; best n − 1 (early exit); swaps = inversions; stable, in-place.
• Selection: min of the rest into place; always n(n−1)/2 comparisons; ≤ n − 1 swaps; in-place, not stable.

3.1.2 Insertion sort and inversions; stable and in-place sorting

• Insertion: insert A[i] into sorted prefix by shifting. Shifts = inversions; Θ(n + I).
• Best Θ(n) (sorted), worst Θ(n²) (reverse, I = n(n−1)/2), average n²/4.
• Binary insertion: O(n log n) comparisons, Θ(n²) shifts.
• Stable: insertion, bubble, merge, counting. In-place: bubble, selection, insertion, heap, quick.

CInterleaved GATE-style questions

Q1NAT2 marksBubble comparisons

Bubble sort with early exit on [5, 2, 9, 1, 7, 3]. Total comparisons?

Numerical answer: ________

Q2MCQ1 markSelection pass

Selection sort on [5, 2, 9, 1, 7, 3]. Array after the first pass?

• (A) [1, 2, 3, 5, 7, 9]
• (B) [1, 2, 9, 5, 7, 3]
• (C) [2, 5, 9, 1, 7, 3]
• (D) [1, 5, 2, 9, 7, 3]

Q3NAT1 markSwaps

Bubble sort on [50, 40, 30, 20, 10]. Swaps?

Numerical answer: ________

Q4NAT2 marksInversions

Number of inversions in [6, 5, 1, 2, 3, 4]?

Numerical answer: ________

Q5NAT2 marksShifts

Insertion sort on [2, 4, 6, 8, 1]. Number of shifts?

Numerical answer: ________

Q6MCQ1 markComparisons

Binary insertion sort reduces the number of:

• (A) both to O(n log n)
• (B) shifts to O(n log n)
• (C) comparisons to O(n log n), but shifts stay Θ(n²) in the worst case
• (D) neither

Q7MSQ2 marksIn-place

Which sorts are in-place?

• (A) Heapsort
• (B) Selection sort
• (C) Insertion sort
• (D) Merge sort (standard)

Q8NAT1 markBest case

Insertion sort on an already sorted array of 50 elements. Number of comparisons?

Numerical answer: ________

DAnswer Vault