クイックソート

n/a原理

コード#コード#

static void quickSort(int[] a, int left, int right) {
  int pl = left;
  int pr = right;
  int x = a[(pl + pr) / 2]; // 피벗
  
  dp {
    while (a[pl] < x) pl++;
    while (a[pr] > x) pr--;
    if (pl <= pr)
      swap(a, pl++, pr--);
  } while (pl <= pr); // 피벗을 기준으로 그룹이 나뉘면 false가 된다.
  
  if (left < pr) quicksort(a, left, pr);
  if (pl < right) quickSort(a, pl, righ);
}

連結ソート

コード#コード#

static int[] buff;
buff = new int[n];

static void mergeSort(int[] a, int left, int right) {
  if (left < right) {
    int i;
    int center = (left + right) / 2;
    int p = 0;
    int j = 0;
    int k = left;
    
    mergeSort(a, left, center);
    mergeSort(a, center + 1, right);
    
    // a의 왼쪽 그룹을 buffer에 복사
    for (i = left; i <= center; i++)
      buff[p++] = a[i];
      
    // a의 오른쪽 그룹이 끝나기 전 and buffer가 끝나기 전까지
    while (i <= right && j < p)
      // 두 그룹을 비교하여 작은 값을 a의 처음부터 삽입
      a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
      
    // buffer의 요소가 남아있는 경우 a에 삽입
    while (j < p)
      a[k++] = buff[j++];
  }
}

buff = null;