Revision as of 21:31, 4 December 2011

COMP 1010 Home > More With Arrays > Sorting Arrays

Bubble Sort

Bubble sort is an easy algorithm to master when learning sorting arrays. This algorithm called bubble sort since it takes the larger elements "bubbles" and put them at the end of the array with each pass. Bubble sort compares each time two elements and if they are not in order swapping them.Next the algorithm compares next set of elements, this process continues until there is no more items to swap.

Pseudo code

procedure bubbleSort( A : list of sortable items )
  repeat
    swapped = false
    for i = 1 to length(A) - 1 inclusive do:
      if A[i-1] > A[i] then
        swap( A[i-1], A[i] )
        swapped = true
      end if
    end for
  until not swapped
end procedure

Let's look on an example:
Lets sort the following array |30|10|20|40|60|

When bubble sort algorithm will start it will compare the first two elements |30|10| it will swap them since 30 larger then 10.
Now array will look as follows:|10|30|20|40|60|05|

Next the algorithm will compare 2nd and 3rd element (|30|20|), since 30 is larger than 20 the algorithm will swap them.
Now array will look as follows: |10|20|30|40|60|05|

Next 3rd and 4th element will be compared (|30|40|) since 30 less than 40 , no swapping will be made.

Now array will look as follows:|10|20|30|40|60|05|

Now 4th element will be compared with 5th (|40|60|) since 40 is less than 60 no swapping will take place.
Now array will look as follows: |10|20|30|40|60|05|

Next 5th and 6th element will be compared (|60|05|) since 60 is grater then 05 swap the elements and new array will look as follows: |10|20|30|40|05|60|

With each pass the element |05| will move to the front until no more swapping will take place. In that case the array is sorted

Complete code for Bubble sort

public static void bubbleSort(int[] array)
   {
      int maxElement;  // Marks the last element to compare
      int index;       // Index of an element to compare
      int temp;        // Used to swap to elements
      
      // The outer loop positions maxElement at the last element
      // to compare during each pass through the array. Initially
      // maxElement is the index of the last element in the array.
      // During each iteration, it is decreased by one.
      for (maxElement = array.length - 1; maxElement >= 0; maxElement--)
      {
         // The inner loop steps through the array, comparing
         // each element with its neighbor. All of the elements
         // from index 0 thrugh maxElement are involved in the
         // comparison. If two elements are out of order, they
         // are swapped.
         for (index = 0; index <= maxElement - 1; index++)
         {
            // Compare an element with its neighbor.
            if (array[index] > array[index + 1])
            {
               // Swap the two elements.
               temp = array[index];
               array[index] = array[index + 1];
               array[index + 1] = temp;
            }
         }
      }
   }

The above is simple implementation of bubble sort, the above algorithm can be improved by shorting each pass. Since there is no necessity to check the last element since it is already in its place since the algorithm places the largest element at the end.

Selection Sort

Selection sorts are used to sort the array into ascending (or descending) order. The idea behind a selection sort is very simple: iterate through each element in the array, and for each element, look at all remaining elements to see if there is something smaller that should be in this position. If there is, exchange the two values.

Example: sort this array

|30|10|20|40|60|

1) Outer loop: iterate through each element

i = 0 (30)

2) Inner loop: iterate through the remaining elements to find a smaller element that should be in this position

j = 1 (10)

3) Since the element at i is greater than the element at j, swap them - the array will now be:

|10|30|20|40|60|

4) Again with the inner loop, we will move to the next element and compare:

i = 0 (10), j = 2 (20)

Since all the other elements in the list are greater than the 0th (10), nothing else will happen for this outer loop.

Loop 2: In the outer loop, we will move to the next element (1) and loop through the remaining elements (starting at 2)

i = 1 (30), j = 2(20)

Since the element at i is greater than the element at j, swap them and continue, giving us this array (which is now sorted!)

|10|20|30|40|60|

Here is an example of a very simple selection sorting algorithm:

// Selection sort algorithm

public static void selectionSort(int[] haystack) {
    for (int i = 0; i < haystack.length - 1; i++) {
        for (int j = i + 1; j < haystack.length; j++) {
            if (haystack[i] > haystack[j]) {
                //... Exchange elements
                int temp = haystack[i];
                haystack[i] = haystack[j];
                haystack[j] = temp;
            }
        }
    }
}