高速ソートを実行する C 言語標準ライブラリ関数

2年 ago
陽, 向宇
1 minute

C言語標準ライブラリに含まれる高速ソート機能であるqsort関数は次のプロトタイプを持ちます。

void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

パラメータの説明：

  1. ソート対象の配列の先頭要素へのポインター。
  2. nmemb: 配列の要素の数。
  3. サイズ: 各要素のバイト単位のサイズ。
  4. compr：2つの要素を比較する関数ポインタ。

任意の種類の配列をソートする qsort 関数を使用するには、要素の大きさを比較する関数のみを提供すればよい。この比較関数は、2 つの要素の大小関係を表す整数値を返す必要がある。返り値が 0 未満の場合、最初の要素は 2 番目の要素より小さいことを示す。返り値が 0 の場合、2 つの要素は等しいことを示す。返り値が 0 より大きい場合、最初の要素は 2 番目の要素より大きいことを示す。

qsort関数を用いて整数の配列をソートするサンプルコードは以下です。

#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int main() {
int arr[] = {4, 2, 8, 5, 1};
int n = sizeof(arr) / sizeof(arr[0]);
qsort(arr, n, sizeof(int), compare);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}

結果が 1 2 4 5 8 となれば、配列は昇順にソートされていることを示します.

クイックソートアルゴリズムを使用するqsort関数は、平均時間計算量は良好(O(nlogn))ですが、最悪時O(n^2)になることに注意してください。性能を重視する場合は、他のソートアルゴリズムの使用を検討してください。

bannerAds