Java

TOPIC 07 – ARRAY SORTING ALGORITHMS

 

 

LESSON NOTE

 

 

SURPRISING COMPLEXITY

The task of sorting an array sounds fairly simple.  At first glance, new programmers may think that it would be similar to searching arrays.  However, sorting an arrays requires considerably more advanced algorithms that searching.

 

MANY DIFFERENT APPROACHES (ALGORITHMS)

 

There are many different ways to sort arrays.  Some are easier to understand than others.  Some of them are easier to code than others.  Some are more efficient at sorting than others.  In fact, we will see that efficiency is a very important concept related to sorting arrays.

 

APPROACH #1 (INSERTION SORT)

 

Let’s pretend that you are playing cards and you’ve just been dealt a hand.  You want to sort your hand from smallest to largest.  Here is the approach that you might use:

 

Consider the first two cards.  Place them in order.  These two cards make up the sorted part of your hand.

 

Consider the third card.  Insert it into the sorted part of your hand so that it remains sorted.

 

Consider the fourth card.  Insert it into the sorted part of your hand so that it remains sorted.

 

Keep on going until you have a fully sorted hand.

 

This approach can be used to sort arrays.  It is called insertion sort.

 

APPROACH #2 (SELECTION SORT)

 

You start off by finding the minimum value in your array.  You swap that element with the element in the first spot.

 

You then find the minimum value of the unsorted array and swap that element with the element in the 2nd spot.

 

You keep on going until you have completed the entire array.

 

This approach is called Selection Sort.

 

APPROACH #3 (BUBBLE SORT)

 

Consider the first two elements of an array.  You will swap them locations if you need to in order to make sure the larger value is last.  You will then consider the second and third elements of the array and do the same.  Then, the 3rd and 4th elements.  You will go on until you reach the end of the array.  By this point, you have the largest value in the array at the end.

 

(Note that this seems very “painful” just to get the largest value at the end.)

 

You now restart the process over again.  This time, you will get the 2nd largest value in the 2nd last place.

 

The next time through, you will get the 3rd largest value in the 3rd last place.

 

You continue until you have done the entire array.

 

You continue until you have done the entire array.  In fact, you can continue until no swaps are needed.

 

OTHER APPROACHES (MERGE SORT & QUICK SORT)

 

Both of these two approaches are very difficult to explain using words.  They both break the array down into small parts and then gradually merge those parts back together. 

 

The implementation of such approaches usually includes recursion.

 

The main difference between merge sort and quick sort is the way in which they break up the array before merging.

 

If you wish to learn more, then a simple google search will turn up plenty of resources.

 

ARRAY TRACE

 

It is common to consider how the array will gradually get sorted by looking at an array trace after each iteration in a sort algorithm.

 

Here are a few array trace examples:

 

EXAMPLE 1 – INSERTION SORT

Here is an example array trace showing how the Insertion sort approach would sort the array below.  Note that the array is shown as a simple list of numbers.

           

         

EXAMPLE 2 – BUBBLE SORT


Here is a detailed array trace of the bubble sort approach.  It actually shows the state of the array after each comparison and also lists the comparison’s result on the right.  Each “block” demonstrates what happens in an iteration.

 

           

 

           

 

EXAMPLE 3 – SELECTION SORT


Here is an example that shows the sorted section, the current spot that needs to get the smallest value, and the smallest value in the unsorted section.

           

 

EXAMPLE 4 – MERGE SORT

 

The following trace shows the array as it is broken apart and then merged back together again.

 

           

 

BUILT-IN FUNCTION

 

Java provides a built-in function to sort arrays.  It uses an implementation of quick sort.

 

The function is inside the Arrays class.  This class is not part of the default library and therefore needs to be imported.  To do this, we simply place the statement below at the very top of your program (above the public class Name line).

 

     import java.util.Arrays;

 

The function’s prototype is:

     public static void sort(int[] a)

 

To here is an example of using the function:

 

     int[] x = {2,-1,42,21,7,-4,20,38,4,17,33};

     Arrays.sort(x);

 

Of course, the above will sort the array but won’t display it on the screen. 

 

 

Sources

 

Array trace images - http://aprogrammerslife.wordpress.com/category/programs/