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 EXAMPLE 2 – BUBBLE SORT
EXAMPLE 3 – SELECTION
SORT
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/ |
|