Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Algorithms and data structures (CSC112) - Chapter 8

Không đóng trình duyệt đến khi xuất hiện nút TẢI XUỐNG Tải xuống

Lecture Algorithms and data structures: Chapter 8 - Selection Sort. In this topic, we will examine code to determine the run time of various operations. We will introduce machine instructions, we will calculate the run times of: operators +, -, =, +=, ++, etc; control statements if, for, while, do-while, switch; functions; recursive functions. | Review Merge Sort Merge Sort Algorithm Time Complexity Best case Average case Worst case Examples Example Selection Sort Selection Sort Selection Sort Algorithm Time Complexity Best case Average case Worst case Examples Selection Sort The list is divided into two sublists, sorted and unsorted, which are divided by an imaginary wall. We find the smallest element from the unsorted sublist and swap it with the element at the beginning of the unsorted data. After each selection and swapping, the imaginary wall between the two sublists move one element ahead, increasing the number of sorted elements and decreasing the number of unsorted ones. Each time we move one element from the unsorted sublist to the sorted sublist, we say that we have completed a sort pass. A list of n elements requires n-1 passes to completely rearrange the data. Selection Sort Algorithm Scan the array to find its smallest element and swap it with the first element. Then, starting with the second element, scan the elements to its right to find the smallest among them and swap it with the second elements. Generally, on pass i (0 i n-2), find the smallest element in A[in-1] and swap it with A[i]: A[0] . . . A[i-1] | A[i], . . . , A[min], . . ., A[n-1] in their final positions Selection Sort Selection Sort Start with the 1st element, scan the entire list to find its smallest element and exchange it with the 1st element Start with the 2nd element, scan the remaining list to find the the smallest among the last (N-1) elements and exchange it with the 2nd element Example: 89 45 68 90 29 34 17 17 | 45 68 90 29 34 89 29 | 68 90 45 34 89 34 | 90 45 68 89 45 | 90 68 89 68 | 90 89 89 | 90 90 23 78 45 8 32 56 8 78 45 23 32 56 8 23 45 78 32 56 8 23 32 78 45 56 8 23 32 45 78 56 8 23 32 45 56 78 Original List After pass 1 After pass 2 After pass 3 After pass 4 After pass 5 Sorted Unsorted Selection Sort Algorithm for i 0 to N-2 do { min i; for j i+1 to N-1 do { if (A[j] Merge Sort Merge Sort Algorithm Time Complexity Best case Average case Worst case Examples Example Selection Sort Selection Sort Selection Sort Algorithm Time Complexity Best case Average case Worst case Examples Selection Sort The list is divided into two sublists, sorted and unsorted, which are divided by an imaginary wall. We find the smallest element from the unsorted sublist and swap it with the element at the beginning of the unsorted data. After each selection and swapping, the imaginary wall between the two sublists move one element ahead, increasing the number of sorted elements and decreasing the number of unsorted ones. Each time we move one element from the unsorted sublist to the sorted sublist, we say that we have completed a sort pass. A list of n elements requires n-1 passes to completely rearrange the data. Selection Sort Algorithm Scan the array to find its smallest element and swap it with the first element. Then, starting with the second element,