QuickSelect algorithm */
| 62 | |
| 63 | /* QuickSelect algorithm */ |
| 64 | static long long int quickSelect(long long int array[], long long int first, long long int last, long long int k) { |
| 65 | |
| 66 | if (last - first >= 1) { |
| 67 | |
| 68 | long long int pivotIndex = partition(array, first, last); |
| 69 | |
| 70 | if (pivotIndex == k) |
| 71 | return array[pivotIndex]; |
| 72 | |
| 73 | else if (k < pivotIndex) |
| 74 | return quickSelect(array, first, pivotIndex - 1, k); |
| 75 | |
| 76 | else |
| 77 | return quickSelect(array, pivotIndex + 1, last, k); |
| 78 | |
| 79 | } |
| 80 | |
| 81 | return array[first]; |
| 82 | |
| 83 | } |
| 84 | |
| 85 | /* Calculate mean given starting and ending array index */ |
| 86 | inline |