quick sort

Posted on | In | Comments:

quick partition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int partition(int a[], int lo, int hi) {
  int pv = a[lo], i = lo, j = hi;
  while (true) {
    while (j >= lo && a[j] >= pv) --j;
    while (i <= hi && a[i] <= pv) ++i;

    // TODO
    if (i >= j) break;
    swap(a[i], a[j]);
    ++i, --j;
  }

  swap(a[lo], a[j]);

  return j;
}

knuth shuffle

1
2
3
4
void shuffle(int a[]){
    for (int i = 0; i < a.length; ++i)
        swap(k, random(0, k));
}

quick sort

1
2
3
4
5
6
7
void qsort(int a[], int lo, int hi) {
  if (lo >= hi) return;
  int p = partition(a, lo, hi);

  qsort(a, lo, p - 1);
  qsort(a, p + 1, hi);
}

quick select

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int findKth(int a[], int k) {
  shuffle(a);
  int lo = 0, hi = a.lenght - 1;

  while (lo < hi) {
    int p = partition(a, lo, hi);
    if (p == k)
      return a[k];
    else if (p < k)
      lo = p + 1;
    else
      hi = p - 1;
  }
}