Page 1 1 Data Structures/ Algorithms and Generic Programming Sorting Algorithms Today ?Sorting ?Bubble Sort ?Insertion Sort ?Shell Sort Comparison Based Sorting ?Input – 2,3,1,15,11,23,1 ?Output – 1,1,2,3,11,15,23 ?Class ‘Animals’ ? Sort Objects – Rabbit, Cat, Rat ?? ? Class must specify how to compare Objects ? ‘<‘ and ‘>’ operators Sorting Definitions ? In place sorting ?Sorting of a data structure does not require any external data structure for storing the intermediate steps ? External sorting ?Sorting of records not present in memory ? Stable sorting ?If the same element is present multiple times, then they retain the original positions STL Sorting ?sort function template ?void sort (iterator begin, iterator end) ?void sort (iterator begin, iterator end, Comparator cmp) Bubble Sort ?Simple and uncomplicated ?Compare neighboring elements ?Swap if out of order ?Two nested loops ?O(N 2 ) Page 2 1 Data Structures/ Algorithms and Generic Programming Sorting Algorithms Today ?Sorting ?Bubble Sort ?Insertion Sort ?Shell Sort Comparison Based Sorting ?Input – 2,3,1,15,11,23,1 ?Output – 1,1,2,3,11,15,23 ?Class ‘Animals’ ? Sort Objects – Rabbit, Cat, Rat ?? ? Class must specify how to compare Objects ? ‘<‘ and ‘>’ operators Sorting Definitions ? In place sorting ?Sorting of a data structure does not require any external data structure for storing the intermediate steps ? External sorting ?Sorting of records not present in memory ? Stable sorting ?If the same element is present multiple times, then they retain the original positions STL Sorting ?sort function template ?void sort (iterator begin, iterator end) ?void sort (iterator begin, iterator end, Comparator cmp) Bubble Sort ?Simple and uncomplicated ?Compare neighboring elements ?Swap if out of order ?Two nested loops ?O(N 2 ) 2 Bubble Sort for (i=0; i<n-1; i++) { for (j=0; j<n-1-i; j++) /* compare the two neighbors */ if (a[j+1] < a[j]) { /* swap a[j] and a[j+1] */ tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; } } http://www.ee.unb.ca/brp/lib/java/bubblesort/ Insertion Sort ?O(N 2 ) sort ?N-1 passes ?After pass p all elements from 0 to p are sorted ?Following step inserts the next element in correct position within the sorted part Insertion Sort Insertion Sort … Insertion Sort - Analysis ?Pass p involves at most p comparisons ?Total comparisons: ? = O(N²) i = 2 ? i N Insertion Sort - Analysis ?Worst Case ? ? Reverse sorted list ? Max possible number of comparisons ? O(N²) ?Best Case ? ? Sorted input ? 1 comparison in each pass ? O(N) Page 3 1 Data Structures/ Algorithms and Generic Programming Sorting Algorithms Today ?Sorting ?Bubble Sort ?Insertion Sort ?Shell Sort Comparison Based Sorting ?Input – 2,3,1,15,11,23,1 ?Output – 1,1,2,3,11,15,23 ?Class ‘Animals’ ? Sort Objects – Rabbit, Cat, Rat ?? ? Class must specify how to compare Objects ? ‘<‘ and ‘>’ operators Sorting Definitions ? In place sorting ?Sorting of a data structure does not require any external data structure for storing the intermediate steps ? External sorting ?Sorting of records not present in memory ? Stable sorting ?If the same element is present multiple times, then they retain the original positions STL Sorting ?sort function template ?void sort (iterator begin, iterator end) ?void sort (iterator begin, iterator end, Comparator cmp) Bubble Sort ?Simple and uncomplicated ?Compare neighboring elements ?Swap if out of order ?Two nested loops ?O(N 2 ) 2 Bubble Sort for (i=0; i<n-1; i++) { for (j=0; j<n-1-i; j++) /* compare the two neighbors */ if (a[j+1] < a[j]) { /* swap a[j] and a[j+1] */ tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; } } http://www.ee.unb.ca/brp/lib/java/bubblesort/ Insertion Sort ?O(N 2 ) sort ?N-1 passes ?After pass p all elements from 0 to p are sorted ?Following step inserts the next element in correct position within the sorted part Insertion Sort Insertion Sort … Insertion Sort - Analysis ?Pass p involves at most p comparisons ?Total comparisons: ? = O(N²) i = 2 ? i N Insertion Sort - Analysis ?Worst Case ? ? Reverse sorted list ? Max possible number of comparisons ? O(N²) ?Best Case ? ? Sorted input ? 1 comparison in each pass ? O(N) 3 Lower Bound on ‘Simple’ Sorting ? Inversions ?An ordered pair (i, j) such that i<j but a[i] > a[j] ?34,8,64,51,32,21 ?(34,8), (34,32), (34,21), (64,51) … ? Once an array has no inversions it is sorted ? So sorting bounds depend on ‘average’ number of inversions performed Theorem 1 ? Average number of inversions in an array of N distinct elements is N(N-1)/4 ? List L, Reverse list L 1 ? All possible number of pairs is ? N(N-1)/2 ? Average = N(N-1)/4 2 ) N ( Theorem 2 ?Any algorithm that sorts by exchanging adjacent elements requires O(N²) average time ?Average number of inversions = O(N 2 ) ?Number of swaps required = O(N 2 ) Tighter Bound ?O( N log N ) ?Optimal bound for comparison based sorting algorithms ?Achieved by Quick Sort, Merge Sort, and Heap Sort Shell Sort ? Also referred to as Diminishing Increment Sort ? Incrementing sequence – h 1 , h 2 ,..h k ? h 1 = 1 ? After a phase using h k , for each i, a[i] <= a[i+h k ] ? In other words – all elements spaced h k apart are sorted ? Start with h = ?N/2?; keep reducing by half in each iteration Shell Sort Page 4 1 Data Structures/ Algorithms and Generic Programming Sorting Algorithms Today ?Sorting ?Bubble Sort ?Insertion Sort ?Shell Sort Comparison Based Sorting ?Input – 2,3,1,15,11,23,1 ?Output – 1,1,2,3,11,15,23 ?Class ‘Animals’ ? Sort Objects – Rabbit, Cat, Rat ?? ? Class must specify how to compare Objects ? ‘<‘ and ‘>’ operators Sorting Definitions ? In place sorting ?Sorting of a data structure does not require any external data structure for storing the intermediate steps ? External sorting ?Sorting of records not present in memory ? Stable sorting ?If the same element is present multiple times, then they retain the original positions STL Sorting ?sort function template ?void sort (iterator begin, iterator end) ?void sort (iterator begin, iterator end, Comparator cmp) Bubble Sort ?Simple and uncomplicated ?Compare neighboring elements ?Swap if out of order ?Two nested loops ?O(N 2 ) 2 Bubble Sort for (i=0; i<n-1; i++) { for (j=0; j<n-1-i; j++) /* compare the two neighbors */ if (a[j+1] < a[j]) { /* swap a[j] and a[j+1] */ tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; } } http://www.ee.unb.ca/brp/lib/java/bubblesort/ Insertion Sort ?O(N 2 ) sort ?N-1 passes ?After pass p all elements from 0 to p are sorted ?Following step inserts the next element in correct position within the sorted part Insertion Sort Insertion Sort … Insertion Sort - Analysis ?Pass p involves at most p comparisons ?Total comparisons: ? = O(N²) i = 2 ? i N Insertion Sort - Analysis ?Worst Case ? ? Reverse sorted list ? Max possible number of comparisons ? O(N²) ?Best Case ? ? Sorted input ? 1 comparison in each pass ? O(N) 3 Lower Bound on ‘Simple’ Sorting ? Inversions ?An ordered pair (i, j) such that i<j but a[i] > a[j] ?34,8,64,51,32,21 ?(34,8), (34,32), (34,21), (64,51) … ? Once an array has no inversions it is sorted ? So sorting bounds depend on ‘average’ number of inversions performed Theorem 1 ? Average number of inversions in an array of N distinct elements is N(N-1)/4 ? List L, Reverse list L 1 ? All possible number of pairs is ? N(N-1)/2 ? Average = N(N-1)/4 2 ) N ( Theorem 2 ?Any algorithm that sorts by exchanging adjacent elements requires O(N²) average time ?Average number of inversions = O(N 2 ) ?Number of swaps required = O(N 2 ) Tighter Bound ?O( N log N ) ?Optimal bound for comparison based sorting algorithms ?Achieved by Quick Sort, Merge Sort, and Heap Sort Shell Sort ? Also referred to as Diminishing Increment Sort ? Incrementing sequence – h 1 , h 2 ,..h k ? h 1 = 1 ? After a phase using h k , for each i, a[i] <= a[i+h k ] ? In other words – all elements spaced h k apart are sorted ? Start with h = ?N/2?; keep reducing by half in each iteration Shell Sort 4 Shell Sort Shell Sort - Analysis ?Each pass (h k ) is O(h k (N/h k ) 2 ) ?h = 1, 2, 4,…N/2 ?Total sums to O(N 2 )?1/h k ??1/h k = 2 ?So ..O(N 2 ) Brain Tweezer int n, k = 20; for(n = 0; n < k; n--) printf(“X”); Change, remove, add ONLY one character anywhere to make this code print X 20 times (give or take a few) DoneRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!