まずは基本的なqsort関数の使い方
クイックソートの特徴
クイックソートの高速なソートアルゴリズムと言われています。
計算量は、\(\mathcal{O}(\log n)\)～\(\mathcal{O}(n^2)\) です。
qsort関数の使い方
■sqrot関数の定義
| 定義 | void __cdecl qsort(void *_Base, size_t _NumOfElements, size_t _SizeOfElements, _CoreCrtNonSecureSearchSortCompareFunction _CompareFunction) |
| ヘッダファイル | stdlib.h |
| 戻り値 | なし（引数１がソートされた状態となります。） |
| 引数１ | _Base：ソートする配列のポインタ |
| 引数２ | _NumOfElements：配列の要素数 |
| 引数３ | _SizeOfElements：配列の１要素の大きさ |
| 引数４ | _CompareFunction：ソート方法を定義した関数 |
ポイント
この4番目の関数は、実装者が定義する必要があります。
この関数を定義することで、
- ソート対象の配列の型（int型やfloat型、double型、string型、構造体など）
- ソート条件（昇順や降順）
を実装者が自由に決められます。
■４つ目の引数の定義方法
ソート方法を定義する関数は、実装者が以下のように定義する必要があります。
| 定義 | int 関数名(const void *n1, const void *n2) |
| 戻り値 | n1 と n2 を比較した結果を返します。
n1 ⇒ n2 の順に配列が並んでいるとき、 通常の実装 |
プログラム
まずは、簡単なソートアルゴリズムのプログラムです。
- double型の値の配列を昇順でソート
- 配列のインデックスは保存しない
- 配列の要素数、配列の要素の値を、標準入力から読み込み
- 読み込んだ配列のソート前とソート後の値を出力
#include <stdio.h>
#include <stdlib.h>
#define TYPE double
/* qsort関数に渡す比較用の関数（昇順） */
int cmpare(const void *n1, const void *n2) {
if (*(TYPE *)n1 > *(TYPE *)n2) {
return 1;
} else if (*(TYPE *)n1 < *(TYPE *)n2) {
return -1;
}
return 0;
}
/* 配列の出力 */
void print_list(const TYPE *list, const int n) {
for (int i = 0; i < n; i ++) {
printf("%lf\n", list[i]);
}
}
int main(void) {
/* １．ソート対象の配列の準備 */
int n; // 配列の要素数
scanf("%d", &n);
TYPE *list = (TYPE *)malloc(n * sizeof(TYPE));
for (int i = 0; i < n; i ++) {
scanf("%lf", &list[i]);
}
/* ２．ソート前の配列の出力 */
printf("<BEFORE>\n");
print_list(list, n);
/* ３．ソート */
qsort(list, n, sizeof(TYPE), cmpare);
/* ４．ソート後の配列の出力 */
printf("<AFTER>\n");
print_list(list, n);
free(list);
return 0;
}
qsort関数に渡す４つ目の引数を、5－14行目のcmpareで定義しています。
実行例
5 4.5 100.0 1.1 3.14 5000.0
<BEFORE> 4.500000 100.000000 1.100000 3.140000 5000.000000 <AFTER> 1.100000 3.140000 4.500000 100.000000 5000.000000
5つの要素を持つ配列を標準入力から読み取り、昇順でソートされていることが確認できました。
別の型にしたければ、３行目のTYPEを違う型にすればOK。
ソートすることはできましたが、ソート後の配列しか得ることができないため、
このままでは、どの要素がどこに配置されたのか分かりません。
そこで、次に、ソート前の配列を構造体にすることで、
ソート前のインデックスが分かるように変更します。
配列のインデックスを保持したクイックソートの実装
考え方
今までは、
TYPE型の値×要素数
の配列についてソートしましたが、
インデックス, TYPE型の要素×要素数
の配列にします。
プログラム
- double型の値とインデックス番号を持った構造体を昇順でソート
- 配列の要素数、配列の要素の値を、標準入力から読み込み
- 読み込んだ配列のソート前とソート後の値を出力
#include <stdio.h>
#include <stdlib.h>
#define TYPE double
/* 配列の要素にする構造体 */
typedef struct {
int index; // ソート前のインデックス（要素番号）
TYPE value; // ソート対象の値
} element;
/* qsort関数に渡す比較用の関数（昇順） */
int cmpare_element(const void *n1, const void *n2) {
if (((element *)n1)->value > ((element *)n2)->value) {
return 1;
} else if (((element *)n1)->value < ((element *)n2)->value) {
return -1;
}
return 0;
}
/* element型の配列の出力 */
void print_element_list(const element *element_list, const int n) {
printf("index\tvalue\n");
for (int i = 0; i < n; i ++) {
printf(" %d\t%lf\n", element_list[i].index, element_list[i].value);
}
}
int main(void) {
/* １．ソート対象の配列の準備 */
int n; // 配列の要素数
scanf("%d", &n);
element *element_list = (element *)malloc(n * sizeof(element));
for (int i = 0; i < n; i ++) {
element_list[i].index = i;
scanf("%lf", &element_list[i].value);
}
/* ２．ソート前の配列の出力 */
printf("<BEFORE>\n");
print_element_list(element_list, n);
/* ３．ソート */
qsort(element_list, n, sizeof(element), cmpare_element);
/* ４．ソート後の配列の出力 */
printf("<AFTER>\n");
print_element_list(element_list, n);
free(element_list);
return 0;
}
6-10行目で、配列の要素を構造体 elememt で定義しています。
また12-22行目で、qsort関数に渡す４つめの引数を、cmpare_elementで定義し、
構造体 element のソート対象の値（value）で比較をするように書いています。
実行例
5 4.5 100.0 1.1 3.14 5000.0
<BEFORE> index value 0 4.500000 1 100.000000 2 1.100000 3 3.140000 4 5000.000000 <AFTER> index value 2 1.100000 3 3.140000 0 4.500000 1 100.000000 4 5000.000000
ソート前の要素番号が保持されたまま、並び替えができていることが確認できました。
（たとえばソート前の要素0の値（4.5）は、ソート後には要素2になっていることが分かると思います。）」
最後に
閲覧いただきありがとうございました。
要素番号を保持したまま、配列をソートするプログラムを実装しました。
C言語でなかなか見つからなかったので、今回、記事にしました。
お役に立てれば幸いです。
アルゴリズムの勉強方法
私は仕事以外では、プログラミングコンテストの問題でアルゴリズムを勉強しています。
ソートやデータ構造など、アルゴリズムの勉強をしたい方は下記の本がオススメです。
C/C++でサンプルコードが書かれているため、C/C++の人にはとてもありがたいです。
