HOME

TOP OF THE PAGE

SELECTION SORT

BUBBLE SORT

Arranging a List in Ascending Order

(Basic Algorithms)

The great staple of Computer Science problems is sorting or arranging a list of items in ascending or descending order. It is a problem that proves to be a fertile ground for trying, comparing, and analysing different ideas and approaches. So, without any further delay, let's jump to it!

Let us arrange the following list of eight numbers in ascending order, i.e., from the smallest to the largest.

52121749 73249262

How do we solve the problem?

The first method that most people think of is to look at the numbers, pick up the smallest, then the second smallest, and so on, until all the numbers are correctly picked. In Computer Science, this algorithm is called Selection Sort because you sort the list by selecting the required items.

In the form of an algorithm, this method becomes:

Method I: Selection Sort
Input: List of items L
  1. K = 1
  2. repeat N-1 times, where N is the number of items in the list
    1. Let smallest = Item K in L
    2. repeat until end of list L
      1. Compare next item X with smallest
      2. if X < smallest
        then
            smallest = X
      (end of repeat until)
    3. swapItem K and smallest
    4. increment K
    (end of repeat N-1 times)
    3. (end of algorithm)
Output: Ordered List L

In the first run, we find the smallest item from the given list of numbers, which is 12 and it is swapped with Item K (K = 1). So, the list at the end of the first run through the algorithm looks like:

1252 1749 73249262

In the second run, we start the process from Item 2 (remember that K = 2 now) and find the smallest element, which is 17. The list after the swap looks like
1217 5249 73249262
Make sure, you now follow why the list looks like the following as we run through the repeat in Step 2 in outermost loop.

12172449 73529262

12172449 73529262
(nothing swapped because 49 is already in the correct place)

12172449 5273 9262

12172449 526292 73

12172449 526273 92

How many comparisons did we do?

If you notice carefully, there are two repeat statements. The first one runs N-1 times. The second also seems to run for N-1 times but with a difference: it is also influenced by K. See if you can convince yourselves that the second repeat runs from K to the end of the list each time.

Therefore, the second loop does N-1 comparisons the first time, N-2 comparisons the second time, N-3, the third time, N-4, the fourth time and all the way down to 1 comparison the last (or the N-1) time.

The total number of comparisons is thus \[ N-1 + N-2 + N-3 + \ldots + 1 = \frac{(N-1)(N)}{2} \] For our problem, N = 8 and the number of comparisons is \[(8-1)(8)/2 = (7\times8)/2 = \fbox{28}\]

Any other way?

Here is another equally simple way - in fact, it is the one many students come up with when asked to arrange a list of items. Computer Scientists call it Bubble Sort.

In this method, we compare every item with its next item. If the second item is smaller, we swap the two and continue until no more swaps are possible. At this point, the items in the list must be in ascending order.

Its name comes from the fact that the largest item bubbles through to the end of the list each time we run through the list. It is obvious then that we need to run through the list N-1 times.

Method II: Bubble Sort
Input: List of items L
  1. K = 1
  2. repeat N-1 times, where N is the number of items in the list
    1. repeat for $i = 1$ to $N-K$
      1. Compare the $i^{th}$ item $X_i$ with the next item $X_{i+1}$
      2. if $X_{i+1} < X_i$
        then
            swap $X_i$ and $X_{i+1}$
      (end of repeat for)
    2. increment K
    (end of repeat N-1 times)
    3. (end of algorithm)
Output: Ordered List L

Again, here is the input list.

52121749 73249262

At the end of the first round of repeat for loop, we have the following list.

1217 4952 2473 6292
Note that the largest item 92 is now at the end of the list.

In the second round, we compare pairs of items starting from the first item to N-2 item (remember that K = 2). The list at the end of second round is

12174924 5262 7392
Note that the second largest item 73 has now moved into its correct position.

By the end of the third round, every item is in correct position and ...

121724 49 5262 7392

... there are no more swaps in the fourth round. The list is in ascending order.

How many comparisons did we do?

There are two repeat statements in this algorithm too. The first one runs N-1 times. The second repeat runs from 1 to N-K each time.

Therefore, the second loop does N-1 comparisons the first time, N-2 comparisons the second time, N-3, the third time, N-4, the fourth time and all the way down to 1 comparison the last (or the N-1) time.

The total number of comparisons is thus \[ N-1 + N-2 + N-3 + \ldots + 1 = \frac{(N-1)(N-2)}{2} \] In our particular instance of the problem, it took only 4 rounds of comparisons, that is \[ (8-1) + (8-2) + (8-3) + (8-4) = \fbox{22}\]

Note that both Selection and Bubble sorts are impractical for large problems.
To sort a list of 1000 items, these require 498,501 comparisons and for 100,000 items, the number is
almost 5 billion comparisons!!

A few questions

These questions are for self-assessment. Please do them for practice. Feel free to discuss with your friends but make sure you get the answers.
  1. Do Selection and Bubble sorts on the following list of items. Make sure you do every step according to the given algorithms.
    59, 18, 84, 25, 22, 94,
    39, 77, 6, 96
  2. What happens to Selection and Bubble Sorts if the original list itself is sorted correctly in ascending order? How many comparisons are still needed?
  3. What happens to Selection and Bubble Sorts if the original list is sorted in descending order? How many comparisons are needed to arrange it in ascending order?
  4. Search the web to see why most researchers say that Bubble Sort is an extremely bad algorithm.