Difference between revisions of "Sorting Arrays"

Latest revision as of 03:30, 8 December 2011

COMP 1010 Home > More With Arrays > Sorting Arrays

Introduction

In the previous section we learned how to search an array, but many searching algorithms have a requirement that the array is sorted. This chapter will cover algorithms that sort arrays. There are a number of sorting algorithms, but we will only cover the most basic ones; they 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 begins, it will compare the first two elements 30 and 10. Since 30 larger then 10, the algorithm will swap them.

Current Array

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

Next, the algorithm will compare the 2nd and 3rd element 30 and 20. Since 30 is greater than 20, the algorithm will swap them.

Current Array:

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

Next, the algorithm will compare the 3rd and 4th elements, 30 and 40. Since 30 is less than 40 , the algorithm will not swap them.

Current Array:

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

Next, the algorithm will compare the 4th and 5th elements, 40 and 60. Since 40 is less than 60 , the algorithm will not swap them.

Current Array:

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

Next, the algorithm will compare the 5th and 6th elements, 60 and 05. Since 60 is greater than 05 , the algorithm will swap them.

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) all the elements are in the correct order. 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. There are many algorithms which improve on this implementation. 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| 

Pseudocode:

 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 implementation of a selection sort 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.