Merge sort, Insertion sort
Merge sort, Insertion sort
SortingI/Slide2SortingSelectionsortorbubblesort1.FindtheminimumvalueinthelistSwap itwiththevalue inthefirstposition2.3.Repeatthe stepsabove forremainderof the list (startingat thesecondposition)InsertionsortMergesortQuicksortShellsortHeapsortTopologicalsort
Sorting I / Slide 2 Sorting Selection sort or bubble sort 1. Find the minimum value in the list 2. Swap it with the value in the first position 3. Repeat the steps above for remainder of the list (starting at the second position) Insertion sort Merge sort Quicksort Shellsort Heapsort Topological sort
Sorting//Slide3Bubble sort and analysisfor(i=0; i<n-l;i++) for(j=0; j<n-1-i; j++)if(a[j+l]a[jl ( // compare the two neighborstmp= a[j]; // swap a[j] and a[j+l]a[j] =a[j+l];a[j+1] = tmp;Worst-caseanalysis:N+N-1+...+1=N(N+1)/2,so O(N^2)
Sorting I / Slide 3 Worst-case analysis: N+N-1+ .+1= N(N+1)/2, so O(N^2) for (i=0; i<n-1; i++) { for (j=0; j<n-1-i; j++) { if (a[j+1] < a[j]) { // compare the two neighbors tmp = a[j]; // swap a[j] and a[j+1] a[j] = a[j+1]; a[j+1] = tmp; } } } Bubble sort and analysis
SortingI/Slide4Insertion:Incremental algorithm principleMergesort:Divide and conquer principle
Sorting I / Slide 4 Insertion: Incremental algorithm principle Mergesort: Divide and conquer principle
SortingI/Slide5Insertion sort1) Initiallyp =12)Letthefirstpelementsbesorted.3)Insertthe(p+1)thelementproperlyinthelist(goinverselyfromrighttoleft)sothatnowp+1elementsare sorted4)incrementpandgotostep(3)
Sorting I / Slide 5 Insertion sort 1) Initially p = 1 2) Let the first p elements be sorted. 3) Insert the (p+1)th element properly in the list (go inversely from right to left) so that now p+1 elements are sorted. 4) increment p and go to step (3)