Cơ sở dữ liệu - Chapter 10: Sorting

Nội dung text: Cơ sở dữ liệu - Chapter 10: Sorting

1. Chapter 10 - Sorting 1
2. Sorting 2
3. Sorting 3
4. Sorting 4
5. Sorting •Natural Merge •Balanced Merge Divice-and- •Polyphase Merge Conquer •Insertion •Selection •Bubble •Quick •Shell •Heap •Quick •Merge 5
6. Straight Insertion Sort 6
7. Straight Insertion Sort 7
8. Straight Insertion Sort 8
9. Straight Insertion Sort 9
10. Straight Insertion Sort 10
11. Straight Insertion Sort 11
12. Straight Insertion Sort 12
13. Straight Insertion Sort Algorithm InsertionSort () Sorts the contiguous list using straight insertion sort Post sorted list. 1. if (count > 1) 1. current = 1 2. loop (current =0) AND (temp.key < datawalker.key) 1. datawalker+1 = datawalker 2. walker = walker -1 4. datawalker+1 = temp 5. current = current + 1 End InsertionSort 13
14. Shell Sort • Also is called diminishing-increment sort 14
15. Shell Sort 15
16. Shell Sort 16
17. Example of Shell Sort 17
18. Example of Shell Sort 18
19. Choosing incremental values • From more of the comparisons, it is better when we can receive more new information. • Incremental values should not be multiples of each other, other wise, the same keys compared on one pass would be compared again at the next. • The final incremental value must be 1. 19
20. Choosing incremental values Incremental values may be: 1, 4, 13, 40, 121, kt = 1 ki-1 = 3 * ki + 1 t = |log3(n)| -1 or : 1, 3, 7, 15, 31, kt = 1 ki-1 = 2 * ki + 1 t = |log2(n)| -1 20
21. Shell Sort Algorithm ShellSort () Sorts the contiguous list using Shell sort Post sorted list. 1. k = first_incremental_value 2. loop (k >= 1) 1. segment = 1 2. loop (segment <= k ) 1. SortSegment(segment) 2. segment = segment + 1 3. k = next_incremental_value End ShellSort 21
22. Shell Sort Algorithm SortSegment(val segment , val k ) Sorts the segment beginning at segment using insertion sort, step between elements in the segment is k. Post sorted segment. 1. current = segment + k 2. loop (current =0) AND (temp.key < data[walker].key) 1. data[walker + k] = data[walker] 2. walker = walker – k 4. data[walker + k] = temp 5. current = current + k End SortSegment 22
23. Insertion Sort Efficiency 23
24. Selection Sort 24
25. Straight Selection Sort 25
26. Straight Selection Sort 26
27. Straight Selection Sort 27
28. Straight Selection Sort 28
29. Straight Selection Sort 29
30. Straight Selection Sort 30
31. Straight Selection Sort 31
32. Selection Sort Algorithm SelectionSort () Sorts the contiguous list using straight selection sort Post sorted list. 1. current = 0 2. loop (current < count - 1) 1. smallest = current 2. walker = current + 1 3. loop (walker < count) 1. if (data [walker].key < data [smallest].key) 1. smallest = walker 2. walker = walker+1 4. swap(current, smallest) 5. current = current + 1 End SelectionSort 32
33. Heap Sort 33
34. Build Heap (first stage) 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 34
35. Heap Sort (second stage) 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 45 56 78 0 1 2 3 4 5 0 1 2 3 4 5 45 56 78 0 1 2 3 4 5 0 1 2 3 4 5 56 78 32 45 56 78 0 1 2 3 4 5 0 1 2 3 4 5 56 78 23 32 45 56 78
36. Heap Sort Algorithm HeapSort () Sorts the contiguous list using heap sort. Post sorted list. Uses Recursive function ReheapDown. 1. position = count / 2 -1 // Build Heap 2.loop (position >=0) 1. ReheapDown(position, count-1) 2. position = position - 1 3. last = count – 1 // second stage of heapsort 4.loop (last > 0) 1. swap(0, last) 2. last = last - 1 3. ReheapDown(0, last - 1) End HeapSort 36
37. Selection Sort Efficiency 37
38. Exchange Sort 38
39. Bubble Sort 39
40. Bubble Sort 40
41. Bubble Sort 23 41
42. Bubble Sort Algorithm BubbleSort () Sorts the contiguous list using straight bubble sort Post sorted list. 1. current = 0 2. flag = FALSE 3. loop (current current) 1. if (data [walker].key < data [walker-1].key) 1. flag = FALSE 2. swap(walker, walker – 1) 2. walker = walker - 1 4. current = current + 1 End BubbleSort 42
43. Exchange Sort efficiency 43
44. Divide-and-conquer sorting Algorithm DivideAndConquer() 1. if (the list has length greater than 1) 1. partition the list into lowlist, highlist 2. lowlist. DivideAndConquer() 3. highlist. DivideAndConquer() 4. combine(lowlist, highlist) End DivideAndConquer 44
45. Divide-and-conquer sorting Partition Combine Merge Sort easily hard Quick Sort hard easily 45
46. Quick Sort Algorithm QuickSort() Sorts the contiguous list using quick sort. Post Sorted list. Uses function recursiveQuickSort. 1. recursiveQuickSort(0, count -1) End QuickSort 46
47. Quick Sort Algorithm recursiveQuickSort(val low , val high ) Sorts the contiguous list using quick sort. Pre low and high are valid positions in contiguous list. Post Sorted list. Uses functions recursiveQuickSort, Partition. 1. if (low < high) // Otherwise, no sorting is needed. 1. pivot_position = Partition(low, high) 2. recursiveQuickSort(low, pivot_position -1) 3. recursiveQuickSort(pivot_position +1, high) End recursiveQuickSort 47
48. Partition Algorithm • Given a pivot value, the partition rearranges the entries in the list as below: 48
49. Partition Algorithm Algorithm: • Temporarily leave the pivot value at the first position. • use a for loop running on a variable i, last_small is the position all entries at or before it have keys less than pivot. • if the entry at i >= pivot, i can be increased. • Otherwise, last_small is increased and two entries at position last_small and i are swapped: 49
50. Partition Algorithm • When the loop terminates: • At last, swap the pivot from position low to position last_small. 50
51. Partition in Quick Sort Partition(val low , val high ) Partitions the entries between indices low and high to two sublists. Pre low and high are valid positions in contiguous list, with low , val j ) interchanges entries in positions i and j. 51
52. Partition(val low , val high ) // i is used to scan through the list. // last_small is the position of the last key less than pivot 1. swap (low, (low+high)/2) // First entry is now pivot. 2. pivot = entrylow 3. last_small = low 4. i = low + 1 5. loop (i = pivot, when last_small < j < i 1. if (datai < pivot) 1. last_small = last_small + 1 2. swap(last_small, i) // Move large entry to right and small to left. 6. swap(low, last_small) // Put the pivot into its proper position. 7. return last_small End Partition 52
53. Quick Sort Efficiency 53
54. Merge Sort 54
55. Merge Sort Algorithm MergeSort() // for linked list Sorts the linked list using merge sort Post sorted list. Uses recursiveMergeSort. 1. recursiveMergeSort(head) End MergeSort 55
56. Merge Sort Algorithm recursiveMergeSort(ref sublist ) Sorts the linked list using recursive merge sort. Post The nodes referenced by sublist have been reaaranged so that their keys are sorted into nondecreasing order. The pointer parameter sublist is reset to point at the node containing the smallest key. Uses functions recursiveMergeSort, Divide, Merge. 1. if (sublist is not NULL) AND (sublist->link is not NULL) 1. Divide(sublist, second_list) 2. recursiveMergeSort(sublist) 3. recursiveMergeSort(secondlist) 4. Merge(sublist, secondlist) End recursiveMergeSort 56
57. Merge Sort Algorithm Divide(val sublist , ref secondlist ) Divides the list into two halves. Pre sublist is not NULL. Post The list of nodes referenced by sublist has been reduced to its first half, and secondlist points to the second half of the sublist. If the sublist has an odd number of entries, then its first half will be one entry larger than its second. 1. midpoint = sublist 2. position = sublist->link // Traverse the entire list 3. loop (position is not NULL) // Move position twice for midpoint's one move. 1. position = position->link 2. if (position is not NULL) 1. midpoint = midpoint->link 2. position = position->link 4. secondlist = midpoint->link 5. midpoint->link = NULL End Divide 57
58. Merge two sublists 58
59. Merge two sublists Algorithm Merge (ref first , ref second ) Merges two sorted lists to a sorted list. Pre first and second point to ordered lists of nodes. Post first points to an ordered list containing all nodes that were referenced by first and second. Second became NULL. 59
60. Algorithm Merge (ref first , ref second ) // lastSorted is a pointer points to the last node of sorted list. // combined is a dummy first node, points to merged list. 1. lastSorted = address of combined 2. loop (first is not NULL) AND (second is not NULL) // Attach node with smaller key 1. if (first->data.key data.key) 1. lastSorted->link = first 2. lastSorted = first 3. first = first->link // Advance to the next unmerged node 2. else 1. lastSorted->link = second 2. lastSorted = second 3. second = second->link 3. if (first is NULL) 1. lastSorted->link = second 2. second = NULL 4. else 1. lastSorted->link = first 5. first = combined.link 60 End Merge