お尻の位置合わせ

heap sortはheapツリー構造を用いてソートする方式であり、O(N x logN)の時間的複雑さを有する.空のアレイは必要ないため、マージ・ソートよりもメモリが少なくなります.
お尻のソート前に理解しなければならない完全なバイナリツリーとお尻について説明します.

バイナリツリーとは?

バイナリツリー(Binary Tree)とは、各ノードにデータを配置し、2つのノードをそれぞれ貼り付ける構造で、無条件に2つのサブノードを持つ.

完全なバイナリツリーとは、ルートの左側のサブノードから右側のサブノードまで、真ん中が空ではなく埋め込まれた構造を指します.

お尻って何?

hop(heap)は、完全バイナリツリーに基づいて、hop生成アルゴリズム(heapify algorithm)によってデータ順序を変更するツリーである.

最大キーストローク:親ノード>子ノード

最小HIP(Min Heap):親ノード<子ノード

hip生成アルゴリズム(Heapify Algorithm)は、特定のノードの2つのサブノードにおいて、より大きく自己位置を変化させるアルゴリズムである.このときのサブノードに他のサブノードがないまで繰り返します.また,1段下がるごとにサブノード数が2倍になるため,時間的複雑度はO(logN)である.

ステージ

次の例では、お尻の位置合わせの手順を示します.

サブノードを有する親ノードに対してhipソートアルゴリズムを適用する.

は、第1のノード(8)と最後のノード(3)を交換し、最後のノード(8)を除く.

の残りのノードにhipソートアルゴリズムを適用する.(3交換7)

は、最初のノード(7)と最後のノード(1)を交換し、最後のノード(7)を除外する.

の残りのノードにhipソートアルゴリズムを適用する.(1と4の交換)

は、最初のノード(4)と最後のノード(1)を交換し、最後のノード(4)を除外する.

の残りのノードにhipソートアルゴリズムを適用する.(1と3の交換)

は、最初のノード(3)と最後のノード(1)を交換し、最後のノード(3)を除外する.

サブノードがないため、自身を除いてソートが完了する.

インプリメンテーション

#include <stdio.h>

int number = 9;
int arr[] = {7, 6, 5, 8, 3, 5, 9, 1, 6};

int main(void) {
  // 힙 생성 
  for (int i=1; i<number; i++) {
    int c = i;
    do {
      int root = (c - 1) / 2;    // 부모 인덱스를 가리킨다.
      if (arr[root] < arr[c]) {  // 부모보다 값이 크면 값을 교환
        int temp = arr[root];
        arr[root] = arr[c];
        arr[c] = temp;
      }
      c = root; 
    } while(c != 0);
  }
  // 힙을 재차 구성하고 힙의 크기를 1 감소
  for (int i = number-1; i>=0; i--) {   // 가장 큰 값인 루트을 맨뒤로 보낸다(제외시킴)
    int temp = arr[0];
    arr[0] = arr[i];
    arr[i] = temp;

    int root = 0;
    int c = 1;
    do {
      c = 2 * root + 1;
      // 자식 중에 더 큰 값 찾기 
      if (c < i-1 && arr[c]< arr[c+1]) {  
        c++;
      }
      //  루트보다 자식의 값이 크면 교환
      if (c < i && arr[root]< arr[c]) {
        int temp = arr[root];
        arr[root] = arr[c];
        arr[c] = temp;
      }
      root = c;
    } while(c < 1);
  }

  for (int i=0; i < number; i++) {
    printf("%d ", arr[i]);
  }

  return 0;
}

ソート数

カウントソート(Counting Sort)は、10 이하의 정수のような所定の範囲で最も速いソートアルゴリズムであり、時間的複雑さはO(N)である.

ステージ

各

要素を検査し、その要素の個数を増やします.

チェックが完了すると、要素の個数が順番に出力されます.

インプリメンテーション

#include <stdio.h>

int main(void) {
  int temp;
  int count[6];
  int array[30] = {1, 3, 2, 4, 3, 2, 5, 3, 1, 2,
                   3, 4, 4, 3, 5, 1, 2, 3, 5, 2,
                   3, 1, 4, 3, 5, 1, 2, 1, 1, 1};
  for (int i=1; i <= 5; i++) {
    count[i] = 0;
  }
  for (int i=0; i<30; i++) {
    count[array[i]]++;
  }
  for (int i=1; i<=5; i++) {
    if (count[i] != 0) {
      for (int j=0; j<count[i]; j++) {
        printf("%d ", i);
      }
    }
  }
  return 0;
}