Selection Sort and Bubble Sort Pass by Pass (ICSE Class 10 Java)

Understand Selection Sort and Bubble Sort Pass by Pass

int t = a[i];
a[i] = a[j];
a[j] = t;

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

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;
        }

Selection Sort and Bubble Sort Pass by Pass: key facts

Swap with a temporary variable

• •t = a[i]
• •a[i] = a[j]
• •a[j] = t

Three statements, in this order.

Passes and comparisons

Passes	n - 1
Comparisons	n(n - 1)/2
n = 5	10
n = 6	15

For the simple version without early exit.

Selection sort rule

Pass i: find the smallest from i to n - 1 | Swap it with a[i]

At most one swap per pass.

Bubble sort rule

Pass i: compare a[j] and a[j+1] for j = 0 to n - 2 - i | Swap if a[j] is greater than a[j+1]

For descending use less than.

How to answer Selection Sort and Bubble Sort Pass by Pass questions

1. 1Copy the array in a row and number the indices.
2. 2For selection sort: for each pass find the smallest value in the unsorted part, note its index and swap; write the array after each pass.
3. 3For bubble sort: for each pass go through neighbouring pairs from the left, swap when out of order, and write the array after the pass.
4. 4Shorten the inner loop by one for each completed pass (the end is already in place).
5. 5Count the swaps and the comparisons if asked.

Selection Sort and Bubble Sort Pass by Pass 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 Selection Sort and Bubble Sort Pass by Pass

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

• Select = search then one swap

  Selection sort searches the rest of the array and swaps once per pass.

  Use it when: Describing selection sort.

• Bubble = neighbours

  Bubble sort only compares neighbours and bubbles the biggest to the end.

  Use it when: Describing bubble sort.

• n - 1 passes

  The last element falls in place by itself, so n - 1 passes are enough.

  Use it when: Loop limits.

Selection Sort and Bubble Sort Pass by Pass: solved examples

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

int[] a = {64, 25, 12, 22, 11};
int n = a.length;
for (int i = 0; i < 2; i++) {
    int m = i;
    for (int j = i + 1; j < n; j++)
        if (a[j] < a[m]) m = j;
    int t = a[m]; a[m] = a[i]; a[i] = t;
}
for (int i = 0; i < n; i++)
    System.out.print(a[i] + " ");

int[] a = {5, 1, 4, 2, 8};
int n = a.length;
for (int j = 0; j < n - 1; j++)
    if (a[j] > a[j + 1]) {
        int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
    }
for (int i = 0; i < n; i++)
    System.out.print(a[i] + " ");

int[] a = {5, 1, 4, 2, 8};
int n = a.length, swaps = 0;
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;
            swaps++;
        }
for (int i = 0; i < n; i++)
    System.out.print(a[i] + " ");
System.out.println(swaps);

Where students lose marks in Selection Sort and Bubble Sort Pass by Pass

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

• ✗Mistake: Swapping without a temporary variable

  a[i] = a[j]; a[j] = a[i]; makes both elements equal to the old a[j].

  Wrong working

  a[i] = a[j]; a[j] = a[i];

  Right working

  int t = a[i]; a[i] = a[j]; a[j] = t;

  ✓Do this: Use three statements and t.

  Usually costs: 1 to 2 marks

• ✗Mistake: Running the bubble inner loop up to n - 1

  a[j + 1] would be a[n], an index outside the array: ArrayIndexOutOfBoundsException.

  Wrong working

  for (j = 0; j < n; j++) if (a[j] > a[j+1])

  Right working

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

  ✓Do this: The last j must be n - 2.

  Usually costs: 1 mark

• ✗Mistake: Swapping inside the inner loop of selection sort every time a smaller value is found

  The selection sort swaps once per pass, after finding the smallest index.

  Wrong working

  if (a[j] < a[i]) swap in the j loop

  Right working

  Record m = j in the loop; swap after the loop

  ✓Do this: Find first, swap later.

  Usually costs: 1 mark

Practice questions on Selection Sort and Bubble Sort Pass by Pass

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

   In bubble sort for ascending order, two adjacent elements a[j] and a[j+1] are interchanged when:
   (a) a[j] < a[j+1] (b) a[j] > a[j+1] (c) a[j] == a[j+1] (d) j is even

   Hint

   The bigger one must move right.

   Answer

   (b) a[j] > a[j+1]

2. Q2 · 1 mark · Very short answerBoard level

   After the first pass of selection sort in ascending order, which value is at index 0?

   Hint

   Smallest selected.

   Answer

   The smallest element of the array.

3. Q3 · 2 marks · Short answerHarder board level

   Write the array after the first pass of selection sort (ascending) on {7, 3, 9, 1}.

   Hint

   Find the smallest and swap with index 0.

   Answer

   {1, 3, 9, 7} (1 at index 3 is swapped with 7 at index 0)

4. Q4 · 3 marks · Short answerHarder board level

   Trace bubble sort (ascending) on {3, 2, 1}. Show the array after each pass and state the number of swaps made.

   Hint

   Pass 1 has two comparisons, pass 2 has one.

   Answer

   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. Total swaps: 3.

5. Q5 · 1 mark · Assertion-reasonHOTS / competency

   Assertion (A): After n - 1 passes of selection sort on an array of n elements, the array is sorted.
   Reason (R): Each pass places the next smallest element at its correct position.
   (a) Both A and R are true and R is the correct explanation of A. (b) Both A and R are true but R is not the correct explanation of A. (c) A is true but R is false. (d) A is false but R is true.

   Hint

   What about the last element?

   Answer

   (a) Both are true and R explains A: when n - 1 elements are in place the last one is too.

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.How many passes does selection sort need for n elements?Show answer

   n - 1.

2. 2.Which element is in its final place after bubble sort pass 1 (ascending)?Show answer

   The largest.

3. 3.What is the variable t used for in a swap?Show answer

   To hold one value temporarily.

4. 4.How many comparisons for n = 5 in the simple version?Show answer

   10

5. 5.Which sort swaps adjacent elements?Show answer

   Bubble sort.

6. 6.What changes to sort in descending order?Show answer

   The comparison operator.

Selection Sort and Bubble Sort Pass by Pass: frequently asked questions