Bubble Sort Algorithm with Example | DSA Tutorials

YASH PAL,

The bubble sort is the easiest and most frequently used sorting algorithm among all the sorting algorithms. But unfortunately, it’s also the slowest sorting algorithm. The bubble technique is the most simple comparison based in place sorting algorithm, which starts by taking the largest element at the end, then the second largest, then the third largest and soon.

Bubble Sort Algorithm

The bubble sort is generally considered to be the most inefficient sorting algorithm in common usage. Under best-case conditions (the list is already sorted), the bubble sort can approach a constant O(n) level of complexity. The general case is an O(n2). The advantage of this sorting method is that it is very simple and easy to implement. The disadvantage is that it is very inefficient.

The bubble sort works by comparing each item in the list with the item next to it, and swapping them if required. The algorithm repeats this process until it makes a pass all the way through the list without swapping any items (in other words, all items are in the correct order). This causes larger values to “bubble” to the end of the list while smaller values “sink” towards the beginning of the list. The algorithm got its name because after every pass, the largest element bubbles up and moves to the end of the array.

Let A be a list of n numbers. Sorting A refers to the operation of rearranging the elements of A so they are in increasing order, i.e., so that,

A[1] < A[2] < A[3] < … < A[N]

For example, suppose A originally is the list

8, 4, 19, 2, 7, 13, 5, 16

After sorting, A is the list

2, 4, 5, 6, 7, 8, 13, 16, 19

Bubble Sort algorithm steps

Suppose the list of numbers A[1], A[2], A[3] … A[N] is in memory. The bubble sort algorithm can be explained in the following steps as follows:

  • Step-1: Compare A[1] and A[2] and arrange them in the desired order, so that A[1] < A[2]. Then compare A[2] and A[3] and arrange them so that A[2] < A[3]. Then compare A[3] and A[4] and arrange them so that A[3] < A[4]. Continue until we compare A[N-1] with A[N] and arrange them so that A[N-1] < A[N]. Observe that Step 1 involves n-1 comparisons. (During step 1, the largest element is “bubble up” to the nth position or “sinks” to the nth position.) When Step 1 is completed, A[N] will contain the largest element.
  • Step-2: Repeat Step 1 with one less comparison; that is, now we stop after we compare and possibly rearrange A[N-2] and A[N-1]. (Step 2 involves N-2 comparisons, and when Step 2 is complete, the second largest element will occupy A[N-1].)
  • Step-3: Repeat Step 1 with two fewer comparisons; that is, we stop after we compare and possibly rearrange A[N-3] and A[N-2].
  • Step-(N-1): Compare A[1] with A[2] and arrange them so that A[1] < A[2].

After N-1 steps, the list will be sorted in increasing order.

The process of sequentially traversing through all or part of a list is frequently called a “pass”, so each of the above steps is called a pass. Accordingly, the bubble sort algorithm requires n-1 passes, where n is the number of input items. Let’s take an example to understand the bubble sort.

Bubble Sort Algorithm Example

Example 1: Suppose the following numbers are stored in an array A:

32, 51, 27, 85, 66, 23, 13, 57

Solution: We apply the bubble sort to the array A. We discuss each pass separately. We need 8-1 = 7 passes to complete the sorting using bubble sort.

A1 = 32, A2 = 51, A3 = 27, A4 = 85, A5 = 66, A6 = 23, A7 = 13, A8 = 57

Pass 1. We have the following comparisons:

  1. Compare A1 and A2. Since 32 < 51, the list remains unchanged.
  2. Compare A2 and A3. Since 51 > 27, interchange 51 and 27 as follows: 32, 27, 51, 85, 66, 23, 13, 57.
  3. Compare A3 and A4. Since 51 < 85, the list is not altered.
  4. Compare A4 and A5. Since 85 > 66, interchange 85 and 66 as follows: 32, 27, 51, 66, 85, 23, 13, 57.
  5. Compare A5 and A6. Since 85 > 23, interchange 85 and 23 as follows: 32, 27, 51, 66, 23, 85, 13, 57.
  6. Compare A6 and A7. Since 85 > 13, interchange 85 and 13 to yield: 32, 27, 51, 66, 23, 13, 85, 57.
  7. Compare A7 and A8. Since 85 > 57, interchange 85 and 57 to yield: 32, 27, 51, 66, 23, 13, 57, 85.

After pass 1, the last element of the array is the largest.

A1 = 32, A2 = 27, A3 = 51, A4 = 66, A5 = 23, A6 = 13, A7 = 57, A8 = 85

Pass 2. We have the following comparisons:

  1. Compare A1 and A2. Since 32 > 27, interchange 32 and 27 as follows: 27, 32, 51, 66, 23, 13, 57, 85.
  2. Compare A2 and A3. Since 32 < 51, the list remains unchanged.
  3. Compare A3 and A4. Since 51 < 66, the list remains unchanged.
  4. Compare A4 and A5. Since 66 > 23, interchange 66 and 23 as follows: 27, 32, 51, 23, 66, 13, 57, 85.
  5. Compare A5 and A6. Since 66 > 13, interchange 66 and 13 as follows: 27, 32, 51, 23, 13, 66, 57, 85.
  6. Compare A6 and A7. Since 66 > 57, interchange 66 and 57 to yield: 27, 32, 51, 23, 13, 57, 66, 85.

After Pass 2, the last two elements of the array are sorted.

A1 = 27, A2 = 32, A3 = 51, A4 = 23, A5 = 13, A6 = 57, A7 = 66, A8 = 85

Pass 3. We have the following comparisons.

  1. Compare A1 and A2. Since 27 < 32, the list remains unchanged.
  2. Compare A2 and A3. Since 32 < 51, the list remains unchanged.
  3. Compare A3 and A4. Since 51 > 23, interchange 51 and 23 as follows: 27, 32, 23, 51, 13, 57, 66, 85.
  4. Compare A4 and A5. Since 51 > 13, interchange 51 and 13 as follows: 27, 32, 23, 13, 51, 57, 66, 85.
  5. Compare A5 and A6. Since 51 < 57, the list remains unchanged.

After Pass 3, the last three elements of the array are sorted.

A1 = 27, A2 = 32, A3 = 23, A4 = 13, A5 = 51, A6 = 57, A7 = 66, A8 = 85

Pass 4. We have the following comparisons.

  1. Compare A1 and A2. Since 27 < 32, the list remains unchanged.
  2. Compare A2 and A3. Since 32 > 23, interchange 32 and 23 as follows: 27, 23, 32, 13, 51, 57, 66, 85.
  3. Compare A3 and A4. Since 32 > 13, interchange 13 and 32 as follows: 27, 23, 13, 32, 51, 57, 66, 85.
  4. Compare A4 and A5. Since 32 < 51, the list remains unchanged.

After Pass 4, the last four elements of the array are sorted.

A1 = 27, A2 = 23, A3 = 13, A4 = 32, A5 = 51, A6 = 57, A7 = 66, A8 = 85

Pass 5. We have the following comparisons.

  1. Compare A1 and A2. Since 27 > 23, interchange 27 and 23 as follows: 23, 27, 13, 32, 51, 57, 66, 85.
  2. Compare A2 and A3. Since 27 > 13, interchange 27 and 13 as follows: 23, 13, 27, 32, 51, 57, 66, 85.
  3. Compare A3 and A4. Since 27 < 32, the list remains unchanged.

After Pass 5, the last five elements of the array are sorted.

A1 = 23, A2 = 13, A3 = 27, A4 = 32, A5 = 51, A6 = 57, A7 = 66, A8 = 85

Pass 6. We have the following comparisons.

  1. Compare A1 and A2. Since 23 > 13, interchange 23 and 13 as follows: 13, 23, 27, 32, 51, 57, 66, 85.
  2. Compare A2 and A3. Since 23 < 27, the list remains unchanged.

After Pass 6, the last six elements of the array are sorted.

A1 = 13, A2 = 23, A3 = 27, A4 = 32, A5 = 51, A6 = 57, A7 = 66, A8 = 85

Pass 7. We have the following comparisons.

  1. Compare A1 and A2. Since 13 < 23, the list remains unchanged.

After Pass 7, the last seven elements of the array are sorted. And the array has only 8 elements, so now our array is completely sorted.

Now, no more comparison is required as the largest and the second largest are at the end of the array. Hence, the sorted array using the bubble sort algorithm is: 13, 23, 27, 32, 51, 57, 66, 85. Algorithm for bubble sort for an array of N elements, sorting will be done after N – 1 pass is given below:

Algorithm : bubblesort (arr [], N)
{
  for (i=0 to N-1)
  {
    for (j=0 to N - i - 1)
    {
      if( arr[j] > arr[j + 1])
      swap arr[j] and arr[j + 1]
    }
  }
}

Bubble sort program

Bubble Sort in C Programming Program | DSA Tutorials
Data Structures & Algorithms Tutorials for Beginners
Data Structures Tutorials