Sorting
Introduction
The AP Computer Science test expects you to know 3 sorting methods.
- Selection sort
- Insertion sort
- Merge sort
The blackjack program I have put together needs sorting too. When a hand is scored in Blackjack Aces can be either 1 or 11 in favor of the highest hand you can make without going over 21. By sorting the hands with Aces last the hand can be scored quite easily. So this seemed to be good time to go over sorting.
The Selection sort and Insertion sort are quite easy to implement. Why not start with the easiest part first? To keep it simpler still only int arrays will be used for sorting.
Selection Sort
In selection sort you visit each element of the array up to the second to last element. At each step you look through the array from i to the end, find the smallest value and swap it for the ith element. The pseudo-code should clarify:
int sortArray[] = {4,5,9,6,1,0,3,8,7,2}; int tmp, tmp_idx; for (int i=0; i < sortArray.length - 1; i++) { tmp = sortArray[i]; tmp_idx = i; for (int j = i + 1; j < sortArray.length; j++) { if (sortArray[j] < tmp) { tmp = sortArray[j]; tmp_idx = j; } } // swap the values if the i-th was the smallest this swap doesn't do anything // you could test for that if you wanted (which is the way it's done in // the final code) sortArray[tmp_idx] = sortArray[i]; sortArray[i] = tmp; }
Insertion Sort
Start at the second element and visit the rest of the list. Check the elements before the ith position and see if it is less than any previous elements. If not it stays where it is and move on. This has the appearance of removing the number shifting the elements before it to create a space and placing the number where it belongs.
In the actual implementation you visit each previous element starting at the element immediately to the left and do compare-swaps until one of 2 conditions apply either the number is now at the begining of the list or the element to the immediate left is less. This method accomplishes the shifting of the elements and the comparisons in a way more neatly suited for looping. Again, pseudo-code should help your understanding.
int sortArray[] = {4,5,9,6,1,0,3,8,7,2}; int tmp, tmp_idx; int j; for (int i = 1; i < sortArray.length; i++) { for (j = i; j > 0 && sortArray[j] < sortArray[j - 1]; j--) { // swap tmp = sortArray[j]; sortArray[j] = sortArray[j - 1]; sortArray[j - 1] = tmp; } }
Create a Sort Lab
To experiment with these I have created a SortLab class. I have borrowed the shuffle method (from the blackjack program) and reworked it for use in the SortLab class. I did this the old fashioned way by cutting and pasting and then changing the names to fit the names of the SortLab fields. The constructors allow you to default to an int array of size 10 or to experiment with other sizes. The arrays are intialized with positive whole numbers. Then they are shuffled to use for sorting. A display method is implemented to print out the values in the array. There is also a swap method to switch values. The selection sort is implemented in 2 different ways. One with an inline swap and a check if a swap is necessary (the first element could have been the lowest of all remaining elements). The other using the swap method with no check.
public class SortLab { int[] labArray = null; int len = 10; public SortLab(int n) { this.len = n; labArray = new int[this.len]; for (int i = 0; i < this.len; i++) { labArray[i] = i; } this.shuffle(); } public SortLab() { this(10); } // This shuffle routine adapted from the work done previously private void shuffle() { int rindex; int swap; for (int i = 0; i < this.len; i++) { rindex = (int) ((Math.random() * ((double) (this.len - i))) + i); swap = this.labArray[i]; this.labArray[i] = this.labArray[rindex]; this.labArray[rindex] = swap; } } void swap(int k, int l) { int tmp; tmp = this.labArray[k]; this.labArray[k] = this.labArray[l]; this.labArray[l] = tmp; } public void display() { for (int i = 0; i < this.len; i++) { System.out.print(this.labArray[i] + " "); } System.out.println(); } public void selection() { int tmp, tmp_idx; for (int i = 0; i < this.len - 1; i++) { //select the ith element save value and index tmp = this.labArray[i]; tmp_idx = i; // Check if selected is the lowest of the remaining array // if not switch them for (int j = i + 1; j < this.len; j++) { if (this.labArray[j] < tmp) { // found something less save it and it's index tmp = this.labArray[j]; tmp_idx = j; } } // if tmp_idx != i then swap the values (move the lowest val in) if (tmp_idx != i) { this.labArray[tmp_idx] = this.labArray[i]; this.labArray[i] = tmp; } } } // Alternate implementation of selection sort using swap function public void selectionA() { int tmp, tmp_idx; for (int i = 0; i < this.len - 1; i++) { tmp = this.labArray[i]; tmp_idx = i; for (int j = i + 1; j < this.len; j++) { if (this.labArray[j] < tmp) { tmp = this.labArray[j]; tmp_idx = j; } } swap(i, tmp_idx); } } public void insertion() { int j; for (int i = 1; i < this.len; i++) { for (j = i; j > 0 && this.labArray[j] < this.labArray[j - 1]; j--) { this.swap(j, j - 1); } } } public static void main(String[] args) { SortLab select = new SortLab(); SortLab selectA = new SortLab(); SortLab insert = new SortLab(); System.out.println("Selection Sort"); System.out.print("unsorted: "); select.display(); select.selection(); System.out.print("sorted: "); select.display(); System.out.println("SelectionA Sort"); System.out.print("unsorted: "); selectA.display(); selectA.selectionA(); System.out.print("sorted: "); selectA.display(); System.out.println(); System.out.println(); System.out.println("Insertion Sort"); System.out.print("unsorted: "); insert.display(); insert.insertion(); System.out.print("sorted: "); insert.display(); } }
Output 1
run: Selection Sort unsorted: 4 7 2 6 1 5 3 9 8 0 sorted: 0 1 2 3 4 5 6 7 8 9 SelectionA Sort unsorted: 1 3 9 6 8 7 5 4 2 0 sorted: 0 1 2 3 4 5 6 7 8 9 Insertion Sort unsorted: 4 5 9 6 1 0 3 8 7 2 sorted: 0 1 2 3 4 5 6 7 8 9 BUILD SUCCESSFUL (total time: 0 seconds)
AP Exam
One way they may ask you about these sorts is to show you interim passes on the list and ask you what type of sort is being done. With a few simple additions our SortLab class can print out interim results to show you how this would look. By placing print statement at the end of the outer loop you can get a print out that shows you the developing sorted lists.
Look at the bottom of the outer loop in each of the 3 sort implementations. I have also added a fourth routine that implements insertion sort with an explicit shift of elements. Some practice exams implement insertion sort in this fashion. Take a look at the output trail it's operation is no different than the first insertion sort. But it uses an extra inner loop.
public void selection() { int tmp, tmp_idx; for (int i = 0; i < this.len - 1; i++) { //select the ith element save value and index tmp = this.labArray[i]; tmp_idx = i; // Check if selected is the lowest of the remaining array // if not switch them for (int j = i + 1; j < this.len; j++) { if (this.labArray[j] < tmp) { // found something less save it and it's index tmp = this.labArray[j]; tmp_idx = j; } } // if tmp_idx != i then swap the values (move the lowest val in) if (tmp_idx != i) { this.labArray[tmp_idx] = this.labArray[i]; this.labArray[i] = tmp; } System.out.print("interim: "); this.display(); } } // Alternate implementation of selection sort using swap function public void selectionA() { int tmp, tmp_idx; for (int i = 0; i < this.len - 1; i++) { tmp = this.labArray[i]; tmp_idx = i; for (int j = i + 1; j < this.len; j++) { if (this.labArray[j] < tmp) { tmp = this.labArray[j]; tmp_idx = j; } } swap(i, tmp_idx); System.out.print("interim: "); this.display(); } } public void insertion() { int j; for (int i = 1; i < this.len; i++) { for (j = i; j > 0 && this.labArray[j] < this.labArray[j - 1]; j--) { this.swap(j, j - 1); } System.out.print("interim: "); this.display(); } } public void insertionShift() { int j; int tmp; for (int i = 1; i < this.len; i++) { // take ith element find where it should be inserted tmp = this.labArray[i]; for (j = i; j > 0 && this.labArray[j] < this.labArray[j - 1]; j--) { // no need to do anything // when the loop ends j will be the insertion position } // Shift elements from j to i-1 over 1 for (int k = i - 1; k >= j; k--) { this.labArray[k + 1] = this.labArray[k]; } this.labArray[j] = tmp; System.out.print("interim: "); this.display(); } } public static void main(String[] args) { SortLab select = new SortLab(); SortLab selectA = new SortLab(); SortLab insert = new SortLab(); SortLab insertA = new SortLab(); System.out.println("Selection Sort"); System.out.print("unsorted: "); select.display(); select.selection(); System.out.print("sorted: "); select.display(); System.out.println("SelectionA Sort"); System.out.print("unsorted: "); selectA.display(); selectA.selectionA(); System.out.print("sorted: "); selectA.display(); System.out.println(); System.out.println(); System.out.println("Insertion Sort"); System.out.print("unsorted: "); insert.display(); insert.insertion(); System.out.print("sorted: "); insert.display(); System.out.println("Insertion Sort with Explicit Shift"); System.out.print("unsorted: "); insertA.display(); insertA.insertion(); System.out.print("sorted: "); insertA.display(); }
Output 2
run: Selection Sort unsorted: 9 6 2 1 3 7 8 4 0 5 interim: 0 6 2 1 3 7 8 4 9 5 interim: 0 1 2 6 3 7 8 4 9 5 interim: 0 1 2 6 3 7 8 4 9 5 interim: 0 1 2 3 6 7 8 4 9 5 interim: 0 1 2 3 4 7 8 6 9 5 interim: 0 1 2 3 4 5 8 6 9 7 interim: 0 1 2 3 4 5 6 8 9 7 interim: 0 1 2 3 4 5 6 7 9 8 interim: 0 1 2 3 4 5 6 7 8 9 sorted: 0 1 2 3 4 5 6 7 8 9 SelectionA Sort unsorted: 9 0 5 7 2 8 4 3 1 6 interim: 0 9 5 7 2 8 4 3 1 6 interim: 0 1 5 7 2 8 4 3 9 6 interim: 0 1 2 7 5 8 4 3 9 6 interim: 0 1 2 3 5 8 4 7 9 6 interim: 0 1 2 3 4 8 5 7 9 6 interim: 0 1 2 3 4 5 8 7 9 6 interim: 0 1 2 3 4 5 6 7 9 8 interim: 0 1 2 3 4 5 6 7 9 8 interim: 0 1 2 3 4 5 6 7 8 9 sorted: 0 1 2 3 4 5 6 7 8 9 Insertion Sort unsorted: 3 0 5 2 6 4 7 9 1 8 interim: 0 3 5 2 6 4 7 9 1 8 interim: 0 3 5 2 6 4 7 9 1 8 interim: 0 2 3 5 6 4 7 9 1 8 interim: 0 2 3 5 6 4 7 9 1 8 interim: 0 2 3 4 5 6 7 9 1 8 interim: 0 2 3 4 5 6 7 9 1 8 interim: 0 2 3 4 5 6 7 9 1 8 interim: 0 1 2 3 4 5 6 7 9 8 interim: 0 1 2 3 4 5 6 7 8 9 sorted: 0 1 2 3 4 5 6 7 8 9 Insertion Sort with Explicit Shift unsorted: 1 9 3 8 5 7 6 4 0 2 interim: 1 9 3 8 5 7 6 4 0 2 interim: 1 3 9 8 5 7 6 4 0 2 interim: 1 3 8 9 5 7 6 4 0 2 interim: 1 3 5 8 9 7 6 4 0 2 interim: 1 3 5 7 8 9 6 4 0 2 interim: 1 3 5 6 7 8 9 4 0 2 interim: 1 3 4 5 6 7 8 9 0 2 interim: 0 1 3 4 5 6 7 8 9 2 interim: 0 1 2 3 4 5 6 7 8 9 sorted: 0 1 2 3 4 5 6 7 8 9 BUILD SUCCESSFUL (total time: 1 second)
Conclusion
That's 2 of the 3 sorts you need to know about. Questions on the AP may show code and of course try to hide what is really going on. If there is an inner loop shifting multiple elements then placing the value in after the shift think insertion sort. The insertion sort above combines the compare and the shift together but the effect is the same. Selection sorts you should see a single swap of 2 values then back out to the main loop. I like to think of it as "select the lowest value and swap it to the current front of the line".
Merge Sort should be next but its implementation is simplified by recursion. So before we go into Merge Sort I want to revisit recursion in my next blog post. Then tackle merge sort. Then I will get back to finishing up blackjack.
You should also visit wikipedia they have some nice animations of how these sorts work.
References
- Aho, Alfred V., John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms. Reading, MA: Addison-Wesley, 1983.
- "Selection Sort." Wikipedia. Wikimedia Foundation, 25 Mar. 2013. Web. 26 Mar. 2013. http://en.wikipedia.org/wiki/Selectionsort
- "Insertion Sort." Wikipedia. Wikimedia Foundation, 22 Mar. 2013. Web. 26 Mar. 2013. http://en.wikipedia.org/wiki/Insertionsort
- Litvin, Maria, and Gary Litvin. Be Prepared for the AP Computer Science Exam in Java. Andover: Skylight, 2009.
Date: 2013-03-28T17:58-0400
1.Heap Sort in C
ReplyDelete2.Bubble Sort in C
3.Insertion Sort in C
4.Selection Sort in C
5.Quick Sort in C
Nice animations of the sorts and thanks for the C code versions
ReplyDelete