【C言語】クイックソートによる配列データの整列

ある程度プログラミングに慣れた人向けの練習問題の一つとして、整列アルゴリズム（ソート）の実装があります。

この記事では、クイックソートを用いた配列データの整列をプログラムに実装する方法について解説しています。

クイックソートの概要

プログラムを作成する前に、クイックソートについての簡単な説明を行います。

クイックソートとは、配列データの要素を整列させる整列アルゴリズム（ソート）の一つです。

アルゴリズム

クイックソートでは「対象配列から基準となる要素を一つ選び、その値より小さい要素の部分配列と大きい要素の部分配列に分割する」という操作を行います。

分割された部分配列についても同様の操作を繰り返し、部分配列の要素の数が1になったときにその要素の位置が確定となります。

なお、分割の基準となる要素の選び方としては、それぞれの部分配列の要素数が等しくなる要素を選ぶ方法、対象配列における最大値（もしくは最小値）の要素を選ぶ方法などがあります。

計算量

クイックソートの計算量は、配列の分割の際に基準となる要素をどのような方法で選ぶかに依存しています。

例えば、それぞれの部分配列の要素数が等しくなるような要素を基準として選ぶ場合、計算量はO記法でO(NlogN)です。

対象の配列における最大値（もしくは最小値）の要素を分割の基準として選ぶ場合、計算量はO記法でO(N^2)となります。

実際にプログラムを作成してみる

前述のアルゴリズムに従ってプログラムを作成します。

プログラム作成の手順

プログラム作成の手順は以下の通りです。

実装例

上記の手順に従ってプログラムを作成します。使用する言語はC言語です。

#include <stdio.h>

void swap(int data[], int a, int b){
  int temp;
  temp = data[a];
  data[a] = data[b];
  data[b] = temp;
}

void quick_sort(int data[], int left, int right){
  int pivot, l, r;
  pivot = data[right];
  l = left;
  r = right;
  while(l != r){
    while(data[l] < pivot){
      l = l + 1;
    }
    while(l < r && data[r-1] >= pivot){
      r = r - 1;
    }
    if(l < r){
      swap(data, l, r-1);
    }
    swap(data, l, right);
    if(l-1 > left){
      quick_sort(data, left, l-1);
    }
    if(r+1 < right){
      quick_sort(data, r+1, right);
    }
  }
}

int main(void){

  int data[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
  int n, i, j, step, temp;

  /* 整列前のデータを表示する */
  printf("---shell sort---\nBefore : ");
  for(n=0; data[n]!='\0'; n++){
    printf("%d ",data[n]);
  }

  /* クイックソートを用いてデータを整列する */
  quick_sort(data, 0, n-1);

  /* 整列後のデータを表示する */
  printf("\nAfter  : ");
  for(n=0; data[n]!='\0'; n++){
    printf("%d ",data[n]);
  }

  return 0;
}

このプログラムを実行すると以下の出力結果が得られます。

---quick sort---
Before : 9 8 7 6 5 4 3 2 1 
After  : 1 2 3 4 5 6 7 8 9 

この出力結果から無事にクイックソートが実装できていることがわかります。

おすすめの記事

本記事を読まれた方には、以下の記事もおすすめします。

【中・上級者への道！】C言語の次に勉強するべきプログラミング言語は何？【オススメは○○】