Bubble, Selection and Insertion Sort and Binary Search (ISC Class 12 Computer Science)

Understand Sorting by Bubble, Selection and Insertion and Binary Search

for (int i = 0; i < n - 1; i++)
    for (int j = 0; j < n - 1 - i; j++)
        if (a[j] > a[j + 1]) {
            int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
        }

for (int i = 1; i < n; i++) {
    int key = a[i], k = i - 1;
    while (k >= 0 && a[k] > key) { a[k + 1] = a[k]; k--; }
    a[k + 1] = key;
}

Sorting by Bubble, Selection and Insertion and Binary Search: key facts

Bubble sort counts

• •Passes: n - 1
• •Comparisons without a flag: n(n-1)/2
• •Swaps = number of inversions
• •Largest goes last each pass

For n = 5, comparisons are 4 + 3 + 2 + 1 = 10.

Selection and insertion sort

• •Selection: n - 1 passes, at most n - 1 swaps
• •Insertion: n - 1 insertions, shifts instead of swaps
• •Insertion is fastest on nearly sorted data

Selection does the same comparisons on any data.

Binary search step

• •mid = (lo + hi) / 2
• •a[mid] < key: lo = mid + 1
• •a[mid] > key: hi = mid - 1
• •Stop when lo > hi

Needs a sorted array.

Searching effort

• •Linear search: up to n comparisons
• •Binary search: about log2 n comparisons
• •1000 sorted items need at most 10 steps

Binary search halves the range each step.

How to answer Sorting by Bubble, Selection and Insertion and Binary Search questions

1. 1Write the array and draw the sorted and unsorted regions.
2. 2Bubble sort: write the array after every pass and mark each swap.
3. 3Selection sort: find the minimum of the unsorted part, note its index, then swap it to the front.
4. 4Insertion sort: take the key, shift larger elements right one by one, and place the key.
5. 5Binary search: write lo, hi and mid for every step until found or lo > hi.
6. 6Count the swaps, shifts or comparisons the question asks for.

Sorting by Bubble, Selection and Insertion and Binary Search in real life

The idea, met in an everyday situation. Answer the question in your own words, then compare with the model answer. The one-line hook is what to remember.

Tricks to remember Sorting by Bubble, Selection and Insertion and Binary Search

Short memory aids. Say each one aloud once, then use it on a question the same day.

• Bubble: biggest floats to the end

  After pass 1 the largest is at the last place; after pass 2 the second largest.

  Use it when: Bubble sort tracing.

• Selection: select, then swap

  Find the minimum of the rest, then do one swap.

  Use it when: Selection sort tracing.

• Insertion: cards in hand

  Pick up a card, shift bigger ones right, slot it in.

  Use it when: Insertion sort tracing.

• Binary needs order

  Sorted first, then halve: lo, mid, hi.

  Use it when: Binary search conditions.

Sorting by Bubble, Selection and Insertion and Binary Search: solved examples

Ordered from board level to HOTS. Try each one before you open the solution.

static int bsearch(int[] a, int key) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (a[mid] == key) return mid;
        else if (a[mid] < key) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Where students lose marks in Sorting by Bubble, Selection and Insertion and Binary Search

The slips examiners see most often, and what to write instead.

• ✗Mistake: Inner loop of bubble sort runs to n instead of n - 1 - i

  With j < n, the last pass of the loop has j = n - 1, so a[j + 1] is a[n], which is out of bounds and throws ArrayIndexOutOfBoundsException. Not reducing the limit by i is a separate, smaller fault: it only adds redundant comparisons with elements already in place, and the array still gets sorted.

  Wrong working

  for (j = 0; j < n; j++) compares a[j] with a[j + 1]

  Right working

  for (j = 0; j < n - 1 - i; j++)

  ✓Do this: Use n - 1 - i as the limit.

  Usually costs: 1 mark

• ✗Mistake: Binary search on an unsorted array

  Halving relies on order; an unsorted array gives wrong answers.

  Wrong working

  Applying mid comparison on 8 3 5 1

  Right working

  Sort first, then search

  ✓Do this: State the pre-condition.

  Usually costs: 1 mark

• ✗Mistake: Wrong mid update

  lo = mid or hi = mid can loop for ever.

  Wrong working

  else if (a[mid] < key) lo = mid;

  Right working

  else if (a[mid] < key) lo = mid + 1;

  ✓Do this: Move past mid on each side.

  Usually costs: 1 mark

Practice questions on Sorting by Bubble, Selection and Insertion and Binary Search

Write each answer on paper first. Open the hint only if you are stuck, and the answer only when you have finished.

1. Q1 · 1 mark · MCQBoard level

   Binary search can be applied only when the array is
   (a) of integers (b) sorted (c) of even length (d) two-dimensional

   Hint

   The halving decision depends on order.

   Answer

   (b) sorted

2. Q2 · 2 marks · Short answerBoard level

   How many passes does the basic bubble sort need for an array of 6 elements, and which element is in its final position after pass 1?

   Hint

   n - 1 passes.

   Answer

   Five passes (n - 1). After pass 1 the largest element is in the last position.

3. Q3 · 4 marks · Short answerHarder board level

   Write a complete bubble sort for an int array a of length n in ascending order and trace it for 3, 2, 1.

   Hint

   Inner loop limit n - 1 - i.

   Answer

   for (int i = 0; i < n - 1; i++)
       for (int j = 0; j < n - 1 - i; j++)
           if (a[j] > a[j + 1]) {
               int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
           }

   Trace for 3 2 1: pass 1: (3,2) swap gives 2 3 1; (3,1) swap gives 2 1 3. Pass 2: (2,1) swap gives 1 2 3. Three swaps; sorted: 1 2 3.

4. Q4 · 3 marks · Short answerHarder board level

   Sort 4, 9, 1, 7 in descending order by selection sort, showing the array after each pass.

   Hint

   Select the largest of the unsorted part each time.

   Answer

   Pass 1: largest 9 (index 1) swaps with index 0: 9 4 1 7. Pass 2: largest of 4 1 7 is 7 (index 3) swaps with index 1: 9 7 1 4. Pass 3: largest of 1 4 is 4 swaps with index 2: 9 7 4 1. Sorted: 9 7 4 1.

5. Q5 · 4 marks · Case-basedHOTS / competency

   For the already sorted array 1, 2, 3, 4, 5, count the comparisons made by (a) basic bubble sort with no flag, (b) bubble sort with a swap flag, (c) selection sort and (d) insertion sort. Which technique suits nearly sorted data best?

   Hint

   Count the comparisons per pass.

   Answer

   (a) 4 + 3 + 2 + 1 = 10 comparisons. (b) The first pass makes 4 comparisons with no swap, so it stops: 4. (c) Selection sort always finds the minimum over the rest: 4 + 3 + 2 + 1 = 10 comparisons and no real swaps. (d) Insertion sort compares each key once with its left neighbour: 4 comparisons. Insertion sort (or flagged bubble sort) suits nearly sorted data.

Test your recall

Answer in your head or on paper first, then open the card. Pulling an answer out of memory makes it stick far better than re-reading.

1. 1.Which element is in place after pass 1 of bubble sort?Show answer

   The largest.

2. 2.Which sort shifts elements instead of swapping them?Show answer

   Insertion sort.

3. 3.What is the limit of the inner loop in bubble sort?Show answer

   n - 1 - i.

4. 4.How many comparisons does selection sort make for n = 5?Show answer

   10.

5. 5.What is mid in binary search?Show answer

   (lo + hi) / 2.

6. 6.What does binary search return when the key is absent?Show answer

   -1 in the usual program (lo exceeds hi).

Sorting by Bubble, Selection and Insertion and Binary Search: frequently asked questions