COP 3540 Data Structures with OOPMajor TopicsIntroductory RemarksBasic idea of these simple sorts:Bubble SortBubble Sort processPowerPoint PresentationSlide 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 methodDiscussion of Insertion Sort – How really implemented!!First (of three):Second (of three): Let’s make it larger…Third (of three):Efficiency of the Insertion SortEfficiency of the Insertion Sort (2 of 3)Efficiency of the Insertion Sort (3 of 3)Sorting ObjectsSlide 38Slide 39Slide 40Slide 41DiscussionSecondary Sort Fields?Comparing the Simple SortsSlide 451/45 COP 3540 Data Structures with OOPSimple SortingChapter 32/45 Major TopicsIntroductory Remarks Bubble Sort Selection Sort Insertion Sort Sorting Objects Comparing Sorts3/45 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/45 Basic idea of these simple sorts: Compare two itemsSwap or Copy overSome have Move, Copy over, Move…Depending on the specific algorithm…5/45 Bubble SortVery slow but simpleBasic idea:Start at one end of a list - say, an array •Visualize left to right (or top to bottom) array of integers…Compare the first items in the first two positions•If the first one is larger, swap with the secondmove to the down one position;otherwise, simply down.At end, the largest item is in the lowest position.Equivalently, this element is in its correct position.Repeat, except for the last position.6/45 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) compares.Perhaps you can already see that the number of compares will be (n-1) + (n-2) _ …. (more ahead)You see how it goes. Let’s look at some code.Author’s applets are available, if desired.7/45 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, note the nested for loop! System.out.print(a[j] + " "); // display it System.out.println(""); } public void bubbleSort() Here’s the real sort itself! { int out, in; // note: local variables!! 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 mean? { long temp = a[one]; a[one] = a[two]; a[two] = temp; } } // end class ArrayBub // Normally should also contain find() and delete() methods too…Discuss especially the parameters;.!!!8/45 class BubbleSortApp { public static void main(String[] args) { int maxSize = 100; // array size // note; merely setting up a size ArrayBub arr; // reference to an object arr = new ArrayBub(maxSize); // creates object of type ArrayBub and feeds parameter to the // constructor which sets the size of the array. . 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/45 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) // always starts at a[0] but goes down one less each time… 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; }// end swap()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
View Full Document
Unlocking...