Join Peggy Fisher for an in-depth discussion in this video Sorting arrays, part of Learning Java.
- It is often necessary to have an array in sorted order, especially if you want to later use it with a binary search on the array, which requires the array to be sorted first. There are many different algorithms available for sorting. In this segment we're going to go through a few of the most popular. Let's start with a selection sort. The selection sort starts with the first value in the array and then compares it to the remaining items, searching for the smallest if we're trying to sort in ascending order, or searching for the largest if we're trying to sort in descending order value in the list.
Once it is located, it swaps the two values. It continues this process, looking for the next value until the entire list is sorted. The selection sort requires a nested loop. We'll take a look at the two nested loops when we look at the program source code. The number of times the sort passes through the array is always one less than the number of items in the array. In the selection sort the inner loop finds the next smallest or largest value, and the outer loop places that value into its proper location.
Let's look at an example program. In this program you can see in the main we declare an array of random numbers. We call the selection sort method, passing the array. Let's scroll down to the method. In the selection sort method you can see we have our outer loop, which actually starts at the end of the array and works its way towards the beginning. Then the inner loop starts with the very first element and compares it to all the remaining elements in the array, trying to find the smallest number.
After it's done, it swaps the two values. These three statements are used to swap two values. Let's run the program so we can see how it works. You can see here's our original array, and then we're going to print out the sorted array when we're done. As you can tell, this array actually sorted them in descending order. So 99 was the largest number and four was the smallest. Here's another example of the selection sort process. If we started with a smaller array of five elements, the first time through the array would choose the two as the smallest number and swap it with the 15.
Then it swaps three and four, then 15 and four, and finally it tries to swap 25, but it was already in the right spot. As you can see, it executed four iterations. As I mentioned earlier, there is another sort called the insertion sort. This sort can be compared to organizing a handful of playing cards. Let's say that you start with one card, you continue to pick up the next random card one at a time. As you pick up each card, you insert it into its correct position in your hand of organized cards.
The insertion sort splits an array into two sub-arrays. The first sub-array, like the cards in your hand, is always sorted and increases in size as the sort continues. The second sub-array, like the cards to be picked up, is unsorted and it contains all the elements yet to be inserted into the first sub-array and decreases in size as the sort continues. The insertion sort passes through the entire array only one time. The insertion sort can be very fast and efficient when used with smaller arrays.
Unfortunately, it loses its efficiency when dealing with large amounts of data. Here's how the insertion sort works. We're starting with that same five element array. This time the first thing it does is compare 15 and four and put them in order. Now it includes the two. Now it included the three and put the three between the two and the four, and finally it included the 15, and the 25 was already in the right position. Let's look at an example program for the insertion sort. As you can see, I'm using the same array that I used for the selection sort.
I also have a method here declared for the insertion sort. Let's scroll down to look at that method. This also has an inner and an outer loop. The outer loop here is starting with the first position. Notice that it starts with one and not zero because it's going to break the array up into little sub-arrays, and the sub-array at position zero is already sorted. Then it goes to the inner loop to see if the next value needs to be inserted somewhere in the sub-array. When you're done, the array is sorted. Let's try running this program as well.
It looks a lot like the results of the selection sort. We started by putting 99 as the first element because this is sorting it in descending order. Okay, in this segment we reviewed two of the most common sorting algorithms used, but I want to make sure you know there are more, such as a bubble sort, a quick sort, and a merge sort.
- Downloading and exploring NetBeans
- Understanding Java basics: data types, strings, arrays, and more
- Controlling flow with functions and loops
- Creating classes
- Sorting and searching arrays
- Manipulating files
- Handling errors
- Building GUIs