TMF1434 Data Structure and Algorithms PDF

TMF1434 DATA STRUCTURE AND ALGORITHMS Semester 2, 2023/2024 Instructor: Azman Bujang Masli [email protected] +6082-583652 2 LEC09 Sorting Algorithms 3 Acknowledgement The following slides were drawn or copied from your textbook “Data Structures Using C++” by D....

TMF1434 DATA STRUCTURE AND ALGORITHMS Semester 2, 2023/2024 Instructor: Azman Bujang Masli [email protected] +6082-583652 2 LEC09 Sorting Algorithms 3 Acknowledgement The following slides were drawn or copied from your textbook “Data Structures Using C++” by D. S. Malik 4 Learning Objectives Learn various sorting algorithms Bubble sort Selection sort Insertion sort Shellsort Quicksort Mergesort Explore how to implement these various sorting algorithms Discover how these sorting algorithms perform 5 Sorting The process of rearranging (or organising) a sequence of objects in some logical order For example: ascending order (from lowest to highest) descending order (from highest to lowest) alphabetical order in ascending order (from ‘a’ to ‘z’) alphabetical order in descending order (from ‘z’ to ‘a’), etc. The sort key The part of a data item that we consider when sorting a data collection 6 Bubble Sort Array-based lists 7 Bubble Sort Simple but inefficient algorithm The largest numbers “bubble” up to the top Suppose list...list[n - 1], a list of n elements We want to sort these elements in increasing order In a series of n-1 iterations list[index] and list[index + 1] are compared If list[index] is greater than list[index + 1] Then list[index] and list[index + 1] are swapped 8 Illustrating Bubble Sort Initial list Iteration 1 Iteration 2 9 Illustrating Bubble Sort (cont’d) Iteration 3 Iteration 4 10 Bubble Sort Algorithm in C++ Bubble sort executes in O(n2) time 11 Selection Sort Array-based lists 12 Selection Sort Find the smallest item in the array Exchange this smallest item with the first entry (itself if the first entry is already the smallest) in the array Find the next smallest item in the array Exchange it with the second entry in the array Repeat these actions (find smallest item and exchange it) until the entire array is sorted The order would be defined by the user (e.g., descending or ascending) 13 Selection Sort Example  Selection Sort Algorithms 14 15 Selection Sort: Array-based Lists in C++ Definition of selectionSort 16 Selection Sort: Array-based Lists in C++ Definition of functions swap and minLocation 0 , 4 minIndex loc 17 Selection Sort: Array-based Lists in C++ (cont’d)  Add the functions in the definition of class arrayListType 18 Insertion Sort Array-based lists 19 Insertion Sort Goal Try to improve (that is, reduce) the number of key comparisons Consider the elements one at a time Insert each element in its proper place among those already considered (keeping them sorted) The element being considered is inserted merely by moving larger elements one position to the right, then inserting the element into the vacated position 20 Insertion Array Example 10 Iteration 1 14 Iteration 2 Iteration 3 Most items are sorted 37 Insert 37 on top of itself 13 Iteration 4 SORTED  Insertion Array Algorithms 21 22 Function insertionSort (Array-based lists) firstOutOfOrder = 1 Iteration 1 Temp = 10 Location =0 Iteration 2 firstOutOfOrder = 2 Temp = 14 Location =1 23 Insertion Sort Linked list-based lists 24 Insertion Sort: Linked List-based Lists If list stored in an array Traverse list in either direction using index variable If list stored in a linked list Traverse list in only one direction Starting at first node: links only in one direction Linked list 25 Finding location of node to be inserted firstOutOfOrder Pointer to node to be moved to its proper location lastInOrder Pointer to last node of the sorted portion of the list Linked list and pointers lastInOrder and firstOutOfOrder 26 Finding location of node to be inserted (cont’d)  Compare firstOutOfOrder info with first node info If firstOutOfOrder info smaller than first node info firstOutOfOrder moved before first node Otherwise, search list starting at second node to find location where to move firstOutOfOrder Compare 27 Finding location of node to be inserted (cont’d) Search list using two pointers current trailCurrent: points to node just before current Handle any special cases trailCurrent current 28 Finding location of node to be inserted (cont’d) CASE 1 CASE 2 CASE 3 TMF1434 - Sorting Algorithms 29 Finding location of node to be inserted (cont’d) Case 1 firstOutOfOrder->info less than first->info Node firstOutOfOrder moved before first Adjust necessary links lastInOrder firstOutOrder Linked list after moving the node with info 8 to the beginning 30 Finding location of node to be inserted (cont’d)  Case 3 (Correction) X X X trailCurrent current lastInOrder firstOutOrder 1 2 3  (Review Case 2 and Case 3 in your Texbook, pp. 546-547  Review function linkedInsertionSort in your Texbook, pp. 547-548) 31 Analysis of Selection Sort and Insertion Sort Average-case behaviour for a list of length n 32 Shellsort Array-based lists 33 Shellsort Reduces number of item movements in insertion sort by modifying it Introduced by D. L. Shell in 1959 Also known as diminishing-increment sort Main idea The elements of the list are viewed as sublists at a particular distance. Each sublist is sorted, so that elements that are far apart move closer to their final position. 34 Shellsort through Example Input list 10 20 15 45 36 48 7 60 18 50 2 19 43 30 55 distance = 7 Sorted sublists at distance 7 Divide list into group of 7 (sort each column) 10 20 15 45 36 48 7 10 18 15 2 19 43 7 60 18 50 2 19 43 30 55 20 50 45 36 48 30 55 60 Sorted list at distance 7 10 18 15 2 19 43 7 55 20 50 45 36 48 30 60 35 Shellsort through Example (cont’d) Input list from previous partition 10 18 15 2 19 43 7 55 20 50 45 36 48 30 60 distance = 4 Sorted sublists at distance 4 Divide list into group of 4 (sort each column) 10 18 15 2 10 18 7 2 19 43 7 55 19 30 15 36 20 50 45 36 20 43 45 55 48 30 60 48 50 60 Sorted list at distance 4 10 18 7 2 19 30 15 36 20 43 45 55 48 50 60 36 Shellsort through Example (cont’d) Input list from previous partition 10 18 15 2 19 43 7 55 20 50 45 36 48 30 60 distance = 1 Sorted list at distance 1 2 7 10 15 18 19 20 30 36 43 45 48 50 55 60 So what have just been done? 1) We arranged the data sequence in a two-dimensional array 2) We sorted the columns of the array 3) With distance = 1, we applied the idea behind insertion sort 37 Shellsort Algorithm  It is a variation on the basic insertion sort algorithm  Starts by comparing elements far apart, then elements less far apart, and finally comparing adjacent elements Insertion sort compares always adjacent elements  Actually, the data sequence is not arranged in a 2- dimensional array: it is held in a 1-dimensional array indexed appropriately  The algorithm uses an increment sequence to determine how far apart elements to be sorted are In our example, the sequence 1, 4, 7 is the increment sequence (aka interval sequence or gap sequence) 38 Function shellSort 39 How to Choose Increment Sequence? How do we choose an increment sequence? In general, this question cannot be answered satisfactorily. Typically, increment sequences are chosen to decrease roughly geometrically so that the number of increments is logarithmic in the size of the list. Shell’s original sequence: n/2, n/4, …, 1 (repeatedly divide by 2) Knuth’s increments: 1, 4, 13, …, (3k – 1)/2 Certain increment sequences must be avoided 1, 2, 4, 8, 16, 32, 64, 128, 256.... Bad performance 40 Analysis of Shellsort Worse case performance: O(n2) Best case performance: O(n log n) Average case performance: depends on the increment sequence  Quicksort 41 (Quick Sort; Quick-sort) Array-based lists 42 Quicksort: Array-based Lists A divide-and-conquer algorithm Partition the array into two (possibly unequal) halves using a pivot element Left half is all less than pivot Right half is all greater than pivot Quicksort the left sublist Quicksort the right sublist Merge the two sorted sublists 43 Quicksort: Array-based Lists (Cont…)  Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.  Quick sort partitions an array and then calls itself recursively twice to sort the two resulting subarrays. This algorithm is quite efficient for large-sized data sets as its average and worst case complexity are of Ο(n2), where n is the number of items.  Quick Sort Pivot Algorithm 44 Step 1 − Choose the highest index value as pivot Step 2 − Take two variables to point low (lo) and high (hi) of the list excluding pivot Step 3 − lo points to the low index Step 4 − hi points to the high index Step 5 − while value at lo is less than pivot move right ( » ) Step 6 − while value at hi is greater than pivot move left («) Step 7 − if both step 5 and step 6 does not match swap lo and hi Step 8 − if lo ≥ hi, the point where they met is new pivot Step 9 − Repeat steps 1- 8 for both left sublist and right sublist Sorted item Unsorted left sublist Unsorted right sublist 26 27 19 10 14 31 33 44 35 42  45 Quick Sort Algorithm Example Pivot = 54 54 46 Quicksort Example 47 How to choose a good pivot? Different ways to select a good pivot. 1. First element 2. Last element 3. Median-of-three elements  Pick three elements, and find the median x of these elements. Use that median as the pivot. 4. Random element  Randomly pick a element as a pivot. 48 Quicksort: Array-based Lists in C++ Given starting and ending list indices Function quickSort calls recQuickSort Function recQuickSort implements the recursive version of quicksort 49 Quicksort: Array-based Lists in C++ (cont’d) Function partition Passes starting and ending list indices Function swap Swaps certain elements of the list 50 Analysis of Quicksort for a list of length n 51 Mergesort / Merge Sort Skiena, S. S. (2008). The Algorithm Design Manual. Second Edition. Springer. 52 53 Mergesort A divide-and-conquer algorithm Divide the elements into two groups Sort each group recursively Merge the two sorted lists 54 Mergesort (Cont…) 55 How to Divide? For arrays  Divide the length of the array by two For linked lists  (See code in your Textbook on how to divide unordered linked lists, pp. 561-562)  The length of a linked list is not known  A linked list is not a random access data structure  Therefore, to divide a list into two sublists, use different strategy to find middle node 56 How to Divide? (cont’d)  So, to divide a linked list, use two pointers: middle and current  middle is initialised to the first node of the list  current is initialised to the third node of the list  If the list has only two nodes, we set current to NULL  Advance middle by one node, advance current by one node  If current is not NULL, advance again current by one node  If current is NULL, then middle points to the last node of the first sublist  Divide list into two sublists  Using the link of middle: assign pointer to node following middle  Set link of middle to NULL  57 Unsorted linked list Advance middle by one node, advance current by one node If current is not NULL, middle and current before traversing the list advance again current by one node If current is NULL, then middle points to the last node of the first sublist middle after traversing the list List after dividing it into two lists 58 How to Merge Efficiently? For linked lists Compare the elements of the sublists Adjust the references of the nodes with the smaller info (See code in your Textbook, pp. 564-565) 59 Analysis of Mergesort Maximum number of comparisons: O(n log2n) If W(n) denotes number of key comparisons Worst case to sort L: W(n) = O(n log2n) Let A(n) denote number of key comparisons in the average case Average number of comparisons for mergesort If n is a power of 2 A(n) = n log2n - 1.25n = O(n log2n) 60 Quick Review Selection sort Sorts a list by finding the smallest (or equivalently, the largest) element in the list, and moving it to the beginning (or the end) of the list. For a list of length n, where n> 0, selection sort makes (1/2)n(n -1) key comparisons 3(n-1) item assignments For a list of length n, where n> 0, on average insertion sort makes (1/4)n2 + O(n) = O(n2) key comparisons (1/4)n2 + O(n) = O(n2) item assignments 61 Quick Review (cont’d) Empirical studies suggest that for large lists of size n, the number of moves in Shellsort is in the range of n1.25 to 1.6n1.25. Let L be a list of n distinct elements. Any sorting algorithm that sorts L by comparison of the keys only, in its worst case, makes at least O(nlog2n) key comparisons. 62 Quick Review (cont’d) Both quicksort and mergesort sort a list by partitioning the list. To partition a list, quicksort first selects the pivot. The algorithm then rearranges the elements: elements in one of the sublists are less than the pivot elements in the second sublist are greater than or equal to the pivot. Mergesort partitions the list by dividing it in the middle. 63 Quick Review (cont’d) In quicksort The sorting work is done in partitioning the list. The number of key comparisons On average is O(nlog2n) In the worst case is O(n2) In mergesort The sorting work is done in merging the list. The number of key comparisons is O(nlog2n). 64 Any Question?