Find the kth smallest number in list (QuickSelect)
It is simple. Get the list and sort all items Theta(N*log2(N)) and take k-th item. Another way is to take incomplete quicksort and sort well only items <= k-th item.
The good explination is in this example and here.
Complexity
Work = n + n/2 + n/4 + …
To sum it all up, we can use the similarity rule:
Work/2 = n/2 + n/4 + n/8 + …
Hence:
Work – (Work/2) = n Work/2 = n Work = 2n Work = O(n)
public static class ArrayExtensions { public static T GetNthElement<T>(this T[] source, int nth) where T: IComparable<T> { if (source == null) throw new ArgumentNullException(); if (source.Count() == 0) throw new ArgumentOutOfRangeException(); var count = source.Count(); var from = 0; var to = count - 1; while(from < to) { var left = from; var right = to; int pivot = (left + right) / 2; var pivotValue = source[pivot]; while (left < right) { if(source[left].CompareTo(pivotValue) >= 0) { source.Swap(left, right); right--; } else { left++; } } if (source[left].CompareTo(pivotValue) > 0) left--; if (nth <= left) { to = left; } else { from = left + 1; } } return source[nth]; } private static void Swap<T>(this T[] array,int index1, int index2) { if (index1 == index2) return; var temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; } }
[TestMethod] public void Find3rdLowerElement3() { var l = new int[] { 2, 1, 51, 52, 56, 35, 20 }; var x = l.GetNthElement(6); Assert.AreEqual(x, 56); x = l.GetNthElement(0); Assert.AreEqual(x, 1); x = l.GetNthElement(1); Assert.AreEqual(x, 2); }
Result StandardOutput: 5,9,2,1,0,3,5,2 LEFT:0 RIGHT:7 PIVOT:3 2,9,2,1,0,3,5,5 LEFT:0 RIGHT:6 PIVOT:3 5,9,2,1,0,3,2,5 LEFT:0 RIGHT:5 PIVOT:3 3,9,2,1,0,5,2,5 LEFT:0 RIGHT:4 PIVOT:3 0,9,2,1,3,5,2,5 LEFT:0 RIGHT:3 PIVOT:3 0,9,2,1,3,5,2,5 LEFT:1 RIGHT:3 PIVOT:3 0,1,2,9,3,5,2,5 LEFT:1 RIGHT:2 PIVOT:3 nth:3 pivot:3 from:0 to:7 -> nth:3 pivot:3 from:1 to:7 0,2,1,9,3,5,2,5 LEFT:1 RIGHT:7 PIVOT:4 0,2,1,9,3,5,2,5 LEFT:2 RIGHT:7 PIVOT:4 0,2,1,9,3,5,2,5 LEFT:3 RIGHT:7 PIVOT:4 0,2,1,5,3,5,2,9 LEFT:3 RIGHT:6 PIVOT:4 0,2,1,2,3,5,5,9 LEFT:3 RIGHT:5 PIVOT:4 0,2,1,2,3,5,5,9 LEFT:4 RIGHT:5 PIVOT:4 nth:3 pivot:4 from:1 to:7 -> nth:3 pivot:4 from:1 to:3 0,2,1,2,5,3,5,9 LEFT:1 RIGHT:3 PIVOT:2 0,2,1,2,5,3,5,9 LEFT:1 RIGHT:2 PIVOT:2 nth:3 pivot:2 from:1 to:3 -> nth:3 pivot:2 from:2 to:3 0,1,2,2,5,3,5,9 LEFT:2 RIGHT:3 PIVOT:2 nth:3 pivot:2 from:2 to:3 -> nth:3 pivot:2 from:3 to:3