BUPT-homework/semester3/pset5/7-3-Quick-Sort.c

#include <stdio.h>
#define CUTOFF 3
#define SIZE 10

void swap(int *l, int *r) {
  int tmp = *l;
  *l = *r;
  *r = tmp;
}

void print(int arr[]) {
  for (int i = 0; i < SIZE; i++) {
    printf("%d,", arr[i]);
  }
  printf("\n");
}

int med3(int arr[], int l, int r) {
  // remember, it's (l + r)
  int center = (l + r) / 2;
  // printf("l:%d\t r:%d\t center:%d\n", l, r, center);
  if (arr[l] > arr[center]) {
    swap(&arr[l], &arr[center]);
  }
  if (arr[l] > arr[r]) {
    swap(&arr[l], &arr[r]);
  }
  if (arr[center] > arr[r]) {
    swap(&arr[center], &arr[r]);
  }
  // arr[l] <= arr[center] <= arr[r]
  swap(&arr[center], &arr[r - 1]); // Hide pivot

  return r - 1; // Return pivot
}

void insert(int arr[], int l, int r) {
  // actually bubble sort is easier to implement
  printf("insert(%d,%d):", l, r - l + 1);
  // rememver using <=, because r is visited
  for (int i = l; i <= r; i++) {
    for (int j = l; j <= r - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(&arr[j], &arr[j + 1]);
      }
    }
  }
  print(arr);
}

void Qsort(int arr[], int l, int r, int pivotIndex) {
  int i, j;

  if (l + CUTOFF <= r) {
    if (pivotIndex == -1) {
      pivotIndex = med3(arr, l, r);
      i = l;
      j = r - 1;
    } else {
      i = l - 1;
      j = r;
    }
    while (1) {
      while (arr[++i] < arr[pivotIndex]) {
      }
      while (arr[--j] > arr[pivotIndex]) {
      }
      if (i < j && i != pivotIndex && j != pivotIndex) {
        swap(&arr[i], &arr[j]);
      } else {
        break;
      }
    }
    // printf("i:%d\n", i);
    swap(&arr[i], &arr[pivotIndex]); // swap back arr[pivotIndex]

    printf("Qsort(%d,%d):", l, r);
    print(arr);
    // from here on, use med3-generated arr[pivotIndex]
    if (i != r) {
      Qsort(arr, l, i - 1, -1);
    } else {
      Qsort(arr, l, i, -1);
    }
    Qsort(arr, i + 1, r, -1);

  } else {
    insert(arr, l, r);
  }
}

int main(void) {
  int arr[] = {49, 38, 65, 97, 76, 13, 27, 50, 2, 8};

  int pivotIndex; // pivot == 8, pivot == 4, other 2 cases pivot <= 3
  scanf("%d", &pivotIndex);

  swap(&arr[pivotIndex], &arr[SIZE - 1]);
  // make sure arr[0] is smaller, arr[r] is larger.


  // remember the pivot index is changed to SIZE - 1
  Qsort(arr, 0, SIZE - 1, SIZE - 1);
  // Qsort(arr, 0, SIZE - 1, pivotIndex);

  return 0;
}