Lecture Data Structures: Lesson 44

Lecture Data Structures: Lesson 44 provide students with knowledge about sorting; sorting integers; elementary sorting algorithms: selection sort, insertion sort, bubble sort; selection sort; swap action (selectionsorting); selection sort analysis; lighter bubbles rise to the top;...
Nội dung trích xuất từ tài liệu:
Lecture Data Structures: Lesson 44Sorting Lecture No.44 Data StructureDr. Sohail AslamSortingIntegers Howtosorttheintegersinthisarray? 20 8 5 10 7 5 7 8 10 20ElementarySortingAlgorithms SelectionSort InsertionSort BubbleSortSelectionSort Mainidea: •findthesmallestelement •putitinthefirstposition •findthenextsmallestelement •putitinthesecondposition •… Andsoon,untilyougettotheendofthelistSelectionSortExample a: 19 5 7 12 00 11 22 33 a: 5 19 7 12 0 1 2 3 a: 5 7 19 12 0 1 2 3 a: 5 7 12 19 0 1 2 3 a: 5 7 12 19 0 1 2 3SelectionSort:Code void selectionSort(int *arr, int N) { int posmin, count, tmp; for(count=0;countSelectionSort:Codeint findIndexMin(int *arr, int start, int N){ int posmin=start; int index; for(index=start; index < N; index++) if (arr[index]SwapAction(SelectionSorting) 20 8 5 10 7 5 8 20 10 7 5 7 20 10 8 5 7 8 10 20 5 7 8 10 20SelectionSortAnalysis Whatisthetimecomplexityofthisalgorithm? Worstcase==Bestcase==Averagecase Eachiterationperformsalinearsearchontherestofthe array • firstelement N+ • secondelement N1+ • … • penultimateelement 2+ • lastelement 1 • Total N(N+1)/2 =(N2+N)/2InsertionSort  Basicidea(sortingcards): • Startsbyconsideringthefirsttwoelementsofthe arraydata,ifoutoforder,swapthem • Considerthethirdelement,insertitintotheproper positionamongthefirstthreeelements. • Considertheforthelement,insertitintotheproper positionamongthefirstfourelements. • ……InsertionSortExample a: 19 12 5 7 0 1 2 3 a: 12 19 5 7 0 1 2 3 a: 5 12 19 7 0 1 2 3 a: 5 7 12 19 0 1 2 3InsertionSort:Code void insertionSort(int *arr, int N) { int pos, count, val; for(count=1; count < N; count++) { val = arr[count]; for(pos=count-1; pos >= 0; pos--) if (arr[pos] > val) arr[pos+1]=arr[pos]; else break; arr[pos+1] = val; } }InsertionSortanimation countvalpos a: 19 12 5 7 1120 0 1 2 3 a: 19 12 19 5 7 1121 0 1 2 3 a: 19 12 19 5 7 0 1 2 3 a: 12 19 5 7 0 1 2 3InsertionSortanimation(cont) countvalpos a: 12 19 5 7 251 0 1 2 3 a: 12 19 19 5 7 250 0 1 2 3 a: 12 19 12 19 7 251 0 1 2 3 a: 12 5 12 19 7 0 1 2 3 a: 5 12 19 7 0 1 2 3InsertionSortanimation(cont) countvalpos a: 5 12 19 7 372 0 1 2 3 a: 5 12 19 19 7 371 0 1 2 3 a: 5 12 12 19 19 370 0 1 2 3 a: 5 12 7 12 19 0 1 2 3 a: 5 7 12 19 0 1 2 3InsertionSortAnalysis  Whatisthetimecomplexityofthisalgorithm?  Worstcase>Averagecase>Bestcase  Eachiterationinsertsanelementatthestartofthe array,shiftingallsortedelementsalong •secondelement 2+ •… •penultimateelement N1+ •lastelement N •Total (2+N)(N1)/2=O(N2)BubbleSort Basicidea(lighterbubblesrisetothetop): • Exchangeneighbouringitemsuntilthelargestitem reachestheendofthearray • RepeatfortherestofthearrayBubbleSortExample a: 19 5 12 7 a: 5 12 7 19 0 1 2 3 0 1 2 3 a: 5 19 12 7 a: 5 7 12 19 0 1 2 3 0 1 2 3 a: 5 12 19 7 a: 5 7 12 19 0 1 2 3 0 1 2 3 a: 5 12 7 19 a: 5 7 12 19 0 1 2 3 0 1 2 3 a: 5 12 7 19 a: 5 7 12 19 0 1 2 3BubbleSort:Code void bubbleSort(int *arr, int N){ int i, temp, bound = N-1; int swapped = 1; while (swapped > 0 ) { swapped = 0; for(i=0; I < bound; i++) if ( arr[i] > arr[i+1] ) { temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; swapped = i; } bound = swapped; } } ...