COP 3540 Data Structures with OOPMajor TopicsIntroductory RemarksBasic idea of these simple sorts:Bubble SortBubble Sort processSlide 7Slide 8Discussion of Bubble Sort - MoreEfficiency of the Bubble Sort - ComparisonsEfficiency of the Bubble Sort - SwapsOverall – Bubble SortSelection SortHow Does the Selection Sort Work?Slide 15Selection Sort – in more detailSlide 17Slide 18Selection Sort itself:Selection Sort itself - moreSelection Sort itself - a bit more; EfficiencyInsertion SortSlide 23Insertion Sort – Here’s how it works: 1 of 3Insertion Sort – how it works: 2 of 3Insertion Sort – description 3 of 3.Slide 27Slide 28Code for Insertion Sort methodAnother Source: On your OWN to read.Slide 31Discussion of Insertion Sort – How really implemented!!First (of three): Brute Force Approach 1 of 3Second (of three): Let’s make it larger…Brute ForceThird (of three): Brute Force ApproachEfficiency of the Insertion SortEfficiency of the Insertion Sort (2 of 3)Efficiency of the Insertion Sort (3 of 3)Sorting ObjectsSlide 40Slide 41Slide 42Slide 43DiscussionSecondary Sort Fields?Comparing the Simple SortsSlide 471/47 COP 3540 Data Structures with OOPSimple SortingChapter 32/47 Major TopicsIntroductory Remarks Bubble Sort Selection Sort Insertion Sort Sorting Objects Comparing Sorts3/47 Introductory RemarksSo many lists are better dealt if ordered.Will look at simple sorting first.Note: there are books written on many advanced sorting techniques. •E.g. shell sort; quicksort; heapsort; etc. Will start with ‘simple’ sorts.Relatively slow, Easy to understand, and Excellent performance under circumstances. All these are O(n2) sorts.4/47 Basic idea of these simple sorts: Compare two itemsSwap or Copy overDepending on the specific algorithm…5/47 Bubble SortVery slow but simpleBasic idea:Start at one end of a list - say, an arrayCompare the first items in the first two positions•If the first one is larger, swap with the secondand move to the right; otherwise, move right.At end, the largest item is in the last position.6/47 Bubble Sort processAfter first pass, made n-1 comparisons and between 0 and n-1 swaps. Continue this process.Next time we do not check the last entry (n-1), because we know it is in the right spot. We stop comparing at (n-2).You see how it goes. Let’s look at some code.Author’s applets are available, if desired.7/47 class ArrayBub { private long[] a; // ref to array a private int nElems; // number of data items//-------------------------------------------------------------- public ArrayBub(int max) // constructor - sets size of array up via argument passed by client. { a = new long[max]; // create the array nElems = 0; // no items yet } public void insert(long value) // put element into array at the end { a[nElems] = value; // insert it nElems++; // increment size } public void display() // displays array contents { for(int j=0; j<nElems; j++) // for each element, System.out.print(a[j] + " "); // display it System.out.println(""); } public void bubbleSort() Here’s the real sort itself! { int out, in; for(out=nElems-1; out>1; out--) // outer loop (backward) for(in=0; in<out; in++) // inner loop (forward) if( a[in] > a[in+1] ) // out of order? swap(in, in+1); // swap them } // end bubbleSort() private void swap(int one, int two) Note: this method is private. So what does this tell you? { long temp = a[one]; a[one] = a[two]; a[two] = temp; } } // end class ArrayBub // Normally should also contain find() and delete() methods too…8/47 class BubbleSortApp { public static void main(String[] args) { int maxSize = 100; // array size // note; merely setting up a size ArrayBub arr; // reference to array // creating a pointer to the array arr = new ArrayBub(maxSize); // create the array // creating an instance of the array // class which will contain an array of maxSize. arr.insert(77); // insert 10 items don’t care how or where! It is up to the ArrayBub. arr.insert(99); arr.insert(44); arr.insert(55); arr.insert(22); arr.insert(88); arr.insert(11); arr.insert(00); arr.insert(66); arr.insert(33); arr.display(); // display items Asking the object to display the array elements arr.bubbleSort(); // bubble sort them Asking the array to sort itself arr.display(); // display them again Asking the array to display itself again } // end main() // note all the ‘services’ asked of the array object. } // end class BubbleSortApp////////////////////////////////////////////////////////////////The Bubble Sort Application9/47 Discussion of Bubble Sort - Morepublic void bubbleSort() Here’s the real sort itself! { int out, in; for(out=nElems-1; out>1; out--) // outer loop (backward) Note the elements probed…. for(in=0; in<out; in++) // inner loop (forward) if( a[in] > a[in+1] ) // out of order? swap(in, in+1); // swap them } // end bubbleSort() private void swap(int one, int two) Note: this method is private. What does this tell you? long temp = a[one]; a[one] = a[two]; a[two] = temp; }If the input numbers are: 77 99 44 55 22 88 11 0 66 33The sorted numbers will be: 0 11 22 33 44 55 66 77 88 99Clearly this sort is ‘ascending.’ It doesn’t have to be.Note the loop counter in the outer loop starts at end of array and decrements each cycle. Why? Note: the inner loop starts at the beginning of the array each time and increments until it hits to the current ‘limit,’ which is out-1. (See above)10/47 Efficiency of the Bubble Sort - ComparisonsCan readily see that there are fewer comparisons in each successive ‘pass.’Thus number of comparisons is computed as:(n-1)+(n-2)+… + 1 = n(n-1)/2;For 10 elements, the number is 10*9/2 = 45.So, the algorithm makes about n2/2 comparisons (ignoring the n which is negligible especially if
View Full Document
Unlocking...