Quick sort/select

Question 1

Quick select

Finds kth smallest element in an unsorted list/array

Answer 1

• determine element
• put all smaller elements to left, larger ones to right
  if pivot element index == k, return it
• if pivot element’s index > k, then recur for left half of array
• else recur for right half

Find kth largest:
int left=0, right = nums.length-1;
while(left < right) {
int pivotIndex = partition(nums, left, right);
if (pivotIndex == k-1)
return nums[pivotIndex];
else if (pivotIndex < k-1)
left = pivotIndex+1;
else
right = pivotIndex-1;
}
return nums[left];

Partition function:

Question 2

Quick select partition function:

Answer 2

• choose last element as the pivot
• put all smaller elements to left, larger to right
• return the final index of this element as the pivot indexprivate int partition(int[] nums, int left, int right) {
  int pivotIndex = right;
  int index=0;
  for(int index2 = left; index2 < right-1; index2++) {
  if (nums[index2] < nums[pivotIndex]) {
  swap(nums, index, index2);
  index++;
  }
  }
  swap(nums, index, pivotIndex);
  return index;
  }