Example 2:Selection 11
Example 2: Selection 11
Selection Problem:Given a list of n numbers,find the k-th smallest.s:2365218131120541 We can sort the list,which needs 0(nlog n). Can we do better,say,linear time? After all,sorting gives a lot more information than we requested. Not always a waste:consider dynamic programming where solutions to subproblems are also produced. 12
Selection ◼ Problem: Given a list of 𝑛 numbers, find the 𝑘-th smallest. ◼ We can sort the list, which needs 𝑂 𝑛 log 𝑛 . ◼ Can we do better, say, linear time? ◼ After all, sorting gives a lot more information than we requested. ❑ Not always a waste: consider dynamic programming where solutions to subproblems are also produced. 12
Idea of divide and conquer Divide the numbers into 3 parts <1), =0, >1) Depending on the size of each part,we know which part the k-th element lies in. Then search in that part. Question:Which v to choose? 13
Idea of divide and conquer ◼ Divide the numbers into 3 parts < 𝑣, = 𝑣, > 𝑣 ◼ Depending on the size of each part, we know which part the 𝑘-th element lies in. ◼ Then search in that part. ◼ Question: Which 𝑣 to choose? 13
Pivot Suppose we use a number v in the given list as a pivot. As said,we divide the list into three parts. S:Those numbers smaller than v S:Those numbers equal to v SR:Those numbers larger than v S:241」 S:L55 Sr:36218131120 14
Pivot ◼ Suppose we use a number 𝑣 in the given list as a pivot. ◼ As said, we divide the list into three parts. ❑ 𝑆𝐿: Those numbers smaller than 𝑣 ❑ 𝑆𝑣: Those numbers equal to 𝑣 ❑ 𝑆𝑅: Those numbers larger than 𝑣 14
After the partition S:241」S:L55 Sa:36218131120 The division is simple:just scan the list and put elements into the corresponding part. ▣O(n)time. To select the k-th smallest value,it becomes (s,月={ selection(SL,k) ifk≤|SL f|Sl<k≤ISl+lSwl selection(SR,k-SL -S)if k>S+l. Complexity? 15
After the partition ◼ The division is simple: just scan the list and put elements into the corresponding part. ❑ 𝑂(𝑛) time. ◼ To select the 𝑘-th smallest value, it becomes ◼ Complexity? 15