Sorting Arrays

COMP 1010 Home > More With Arrays > Sorting Arrays

Introduction In the previous section we learned how to search an array, but there is a requirement that the array will be sorted. In this chapter we are going to cover sorting algorithms to sort arrays, although there are number of sorting algorithms with different" time complexity ", the most common ones are Selection sort and bubble sort.

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 at an example.Lets sort the following array:

 |30|10|20|40|60|05| 

When the bubble sort algorithm starts, it will compare the first two elements |30|10| and it will swap them since 30 larger then 10.

Current Array

 |10|30|20|40|60|05| 

Next, the algorithm will compare the 2nd and 3rd element (|30|20|) and since 30 is larger than 20 the algorithm will swap them.

Current Array:

 |10|20|30|40|60|05| 

Next, the 3rd and 4th element will be compared (|30|40|) and since 30 is less than 40 , they won't be swapped.

Current Array:

 |10|20|30|40|60|05| 

Now the 4th element will be compared with the 5th element (|40|60|) and since 40 is less than 60, they won't be swapped.

Current Array:

 |10|20|30|40|60|05| 

Next, the 5th and 6th element will be compared (|60|05|) and since 60 is greater then 05, swap the elements

Current Array:

 |10|20|30|40|05|60| 

With each pass the element |05| will move to the front (because it is the smallest element in the array) until no more swapping can take place. At this point 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 code is a simple implementation of the bubble sort. The algorithm can be improved by sorting each pass. It is not necessary to check the last element since it is already in its place. This is because 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;
            }
        }
    }
} 

Section Summary

In this section you learned how to sort arrays with two algorithms; Selection Sort and Bubble sort. As you know already there are many more sorting algorithms with different efficiency factors. From the examples above you saw how to sort array of integers, in the future same techniques can be applied to sort arrays with any kind of objects.

Previous Page: Sorting Arrays

Next Page: More With Arrays Review Questions and Exercises