CompSci 100E26.1IntrotoSortingÿ Sorting "Ideal" Computer Science Topic Theory and Practice meet Efficient Sorting Saves MoneyÿFirst look at some simple (quick and dirty?) algorithmsÿ Selection Sort1. Find smallest; swap with element [0]2. Consider rest of list [1], [2], ...; find smallest,swap with element [1]3. Continue process until you get to endCompSci 100E26.2Selection Sorting Example N items in an array named Data [ 2 | 4 | 7 | 3 | 1 | 8 | 5 ] Find smallest of elements 1 thru N of Data Interchange this with 1st element of array Data [ 1 | 4 | 7 | 3 | 2 | 8 | 5 ] Find smallest of elements 2 thru N of Data Interchange this with 2nd element of array Data [ 1 | 2 | 7 | 3 | 4 | 8 | 5 ] ... Find smallest of elements K thru N of Data Interchange this with Kth element of array Data [ 1 | 2 | 3 | 7 | 4 | 8 | 5 ] [ 1 | 2 | 3 | 4 | 7 | 8 | 5 ] [ 1 | 2 | 3 | 4 | 5 | 8 | 7 ] Done when K = N [ 1 | 2 | 3 | 4 | 5 | 7 | 8 ] CompSci 100E26.3Selecton Sort Codepublic int locMin(int[] nums, int start){int loc = start;for (int k = start + 1; k < nums.length; k++){if (nums[k] < nums[loc])loc=k;}return loc;}public void SelectSort(int[]nums){for (int k = 0; k < nums.length; k++) {int minloc = locMin(nums, k);int temp = nums[k];nums[k] = nums[minloc];nums[minloc] = temp;}}CompSci 100E26.4Selection Sortingÿ Think about Selection Sortÿ Loop Invariant What can we say about our partially sorted list that is true each time around?ÿ Complexity What is the big Oh? Develop relationship for Selection SortCompSci 100E26.5More Sortingÿ Other Simple Sorts Simple means O(N2) Bubble Sort? (XXX)o Worst of the O(N2)ÿ Insertion Sort Develop Algorithm (method often used when updating a sorted list, one item at a time) More complicated to program than selection sorto But, has some very nice propertiesCompSci 100E26.6Example[ 5| 4 | 6 | 9 | 3 | 8 | 1 ] 4[ 5| 4 | 6 | 9 | 3 | 8 | 1 ] 4[ 5| 5 | 6 | 9 | 3 | 8 | 1 ] 4[ 4| 5 | 6 | 9 | 3 | 8 | 1 ][ 4 | 5 | 6 | 9 | 3 | 8 | 1 ] 6[ 4 | 5 | 6 | 9 | 3 | 8 | 1 ] 6[ 4 | 5 | 6 | 9 | 3 | 8 | 1 ] [ 4 | 5 | 6 | 9 | 3 | 8 | 1 ] 9[ 4 | 5 | 6 | 9 | 3 | 8 | 1 ] 9[ 4 | 5 | 6 | 9 | 3 | 8 | 1 ][ 4 | 5 | 6 | 9 | 3 | 8 | 1 ] 3[ 4 | 5 | 6 | 9 | 3 | 8 | 1 ] 3[ 4 | 5 | 6 | 9 | 9 | 8 | 1 ] 3[ 4 | 5 | 6 | 6 | 9 | 8 | 1 ] 3[ 4 | 5 | 5 | 6 | 9 | 8 | 1 ] 3[ 4 | 4 | 5 | 6 | 9 | 8 | 1 ] 3[ 3 | 4 | 5 | 6 | 9 | 8 | 1 ] [ 3 | 4 | 5 | 6 | 9 | 8 | 1 ] 8[ 3 | 4 | 5 | 6 | 9 | 8 | 1 ] 8[ 3 | 4 | 5 | 6 | 9 | 9 | 1 ] 8[ 3 | 4 | 5 | 6 | 8 | 9 | 1 ][ 3 | 4 | 5 | 6 | 8 | 9 | 1 ] 1[ 3 | 4 | 5 | 6 | 8 | 9 | 1 ] 1[ 3 | 4 | 5 | 6 | 8 | 9 | 9 ] 1[ 3 | 4 | 5 | 6 | 8 | 8 | 9 ] 1[ 3 | 4 | 5 | 6 | 6 | 8 | 9 ] 1[ 3 | 4 | 5 | 5 | 6 | 8 | 9 ] 1[ 3 | 4 | 4 | 5 | 6 | 8 | 9 ] 1[ 3 | 3 | 4 | 5 | 6 | 8 | 9 ] 1[ 1 | 3 | 4 | 5 | 6 | 8 | 9 ]CompSci 100E26.7Insertion Sort Codepublic void insertSort(int[]nums){int j, k, temp;for (k = 1; k < nums.length; k++) {temp = nums[k];for(j=k;j>0;j--){ // decrement!if (temp<nums[j-1])nums[j] = nums[j-1];elsebreak;}nums[j] = temp;}}CompSci 100E26.8Insertion Sortÿ Loop Invariant?ÿ Complexity? For almost sorted?ÿ Is stable! What does that
View Full Document
Unlocking...