見出し画像

C言語教室 解答編 第28回 - と、最近のソート事情

kzn

今回はソートの大本命、クイックソートです。

C言語教室 第28回 いろいろなソート(続続)

ソートといえば、特に理由がなければライブラリ関数にあるクイックソートを呼んでしまうのですが、まずクイックソートとはどうやってソートするのか自分でコードを書いてみて、さらに少し癖のあるライブラリ関数の呼び方に挑戦します。

まだ課題をやっていないという方は、是非、挑戦をしてください。挑戦したら結果をお知らせいただけたら幸いです。締切は設けていないので、挑戦したらぜひお知らせください。

まだ課題を解いていないという方が、うっかり解答を見ないための閑話ですが、ソートも最後なので、最近のソート事情について書いてみたいと思います。

ライブラリに関数もあることだし、もうソートについてなんて勉強の時しかやらなくてもいいのではと思うかもしれませんが、まだまだソートは発展中です。まず最近はひとつのCPUの中に多くのCOREが搭載されており、重い仕事をするのであれば、どうやって多くのCPUに分担させて実行するかがポイントになっています。そのためにはスレッドを使って処理を分割する必要があり、ソートをするのでも、どのように分割すれば良いのかが腕の見せどころになっています。

ソートアルゴリズムをマルチスレッドで

【C言語】マルチコアプロセッサ向け並行ソートアルゴリズム【並列ソート】

スレッドを使うときには、どの程度の粒度で分割するのかが問題となりますし、それぞれのスレッドに割り当てられるスタックサイズにも気を遣わなければなりません。とはいえ最近のCPUであればうまくいけば一桁くらいの性能向上を見込むことができるので、マルチスレッド化は必須となっていくのかもしれません。

これとは別ですが、今のOSは多くのメモリを使うときに、仮想メモリに割り当てるので、ソートをするのにもアクセスするメモリが比較的まとまった領域に集まっていれば良いのですが、離れたところをランダムにアクセスするとページファイルにアクセスしまくって致命的な速度低下を引き起こすこともあります。このため可能な範囲でアクセスするメモリを固める必要があったりします。

もっと大きなデータをソートするときは、もうメモリの中でソートすることを諦めてファイルから読み込んでファイルに吐き出すようなアルゴリズムを選択する場合もあります。この時も素直に読んでいく方法もあるのですが、適切なアルゴリズムを使いつつ mmapを使って、あたかもメモリの中をアクセスするように書いていくことも出来ます。

このようにまだまだ自力でソートを書く羽目になることは続きそうです。

そういえば、AIが新しいアルゴリズムを見つけたという話題もあるようです。

ディープマインドがAIで高速アルゴリズムを発見、C++に採用

また量子コンピュータでもソートの研究が始まっているようです。まだ動かすためのハードウェアが使えないですけどね。

Quantum Sort 作ってみた【量子ソート】

課題に進みます。今回の課題は

課題
1. 整数配列のコードを参考にして文字列(へのポインタ)配列をクイックソートでソートしてください。
2. ライブラリ関数 qsort() を使って文字列(へのポインタ)配列をソートしてください。
なお、いずれも文字列の比較にはstrcmp()を使うこと。

https://note.com/kazushinakamura/n/ne4b64ddb489e

でした。どちらも教室の中で整数配列に対するコードを説明しているので、それらを元にすれば大丈夫です。

まず最初の課題から。

#include <stdio.h>
#include <string.h>

void swap(char **a, char **b) {
  char* temp = *a;
  *a = *b;
  *b = temp;
}

int partition(char **arr, int low, int high) {
  char* pivot = arr[high];
  int i = low - 1;

  for (int j = low; j <= high - 1; j++) {
    if (strcmp(arr[j], pivot) < 0) {
      i++;
      swap(&arr[i], &arr[j]);
    }
  }
  swap(&arr[i + 1], &arr[high]);
  return (i + 1);
}

void quick_sort(char **arr, int low, int high) {
  if (low < high) {
    int pi = partition(arr, low, high);
    quick_sort(arr, low, pi - 1);
    quick_sort(arr, pi + 1, high);
  }
}

void print_array(char **arr, int size) {
  for (int i = 0; i < size; i++)
    printf("%s ", *arr++);
  printf("\n");
}

void main() {
  char* arr[] = {"apple", "orange", "grape", "peach", "banana"};
  int n = sizeof(arr) / sizeof(arr[0]);

  printf("Original array: ");
  print_array(arr, n);

  quick_sort(arr, 0, n - 1);

  printf("Sorted array  : ");
  print_array(arr, n);
}

この結果は以下になります。

Original array: apple orange grape peach banana 
Sorted array  : apple banana grape orange peach

教室で説明したコードの型を適切に変更していけば、文字列配列に対応するものになるはずです。もう char** も怖くないですね。

次はライブラリ関数を呼ぶ形です。

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

int compare(const void *s1, const void *s2 ) {
  /* Compare all of both strings */
  return strcmp(*(char**)s1, *(char**)s2);
}

void print_array(char **arr, int size) {
  for (int i = 0; i < size; i++)
    printf("%s ", *arr++);
  printf("\n");
}

void main() {
  char* arr[] = {"apple", "orange", "grape", "peach", "banana"};
  int n = sizeof(arr) / sizeof(arr[0]);

  /* Output original */
  printf("Original array: ");
  print_array(arr, n);

  /* Sort remaining args using Quicksort algorithm */
  qsort(arr, n, sizeof(char*), compare);

  /* Output sorted */
  printf("Sorted array  : ");
  print_array(arr, n);
}

結果は先のものと同じです。比較関数 compare で型変換の嵐がありますが、ライブラリ関数のプロトタイプ宣言の都合で、もう少し const を効かせることが出来そうにも見えるのですが、もしかしたら、ここまでなのかもしれません。

これで比較を strcmp に押し込んだので、大文字小文字を同じにしたければ、stricmp を使うだけで済みますし、ロケールを考慮するのであれば strcoll を使うこともできるわけです。

qsort は、このように比較関数を工夫することでいろいろな型の配列をソートすることができるわけです。他にも倍精度浮動小数点型の配列をソートするのであれば、以下のように書くことが出来ます。

#include <stdlib.h>
#include <stdio.h>

int compare(const void *v1, const void *v2 ) {
  const double a = *((double*)v1);
  const double b = *((double*)v2);
  if (a == b) return 0;
  else if (a < b) return -1;
  else return 1;
}

void print_array(double *arr, int size) {
  for (int i = 0; i < size; i++)
    printf("%f ", *arr++);
  printf("\n");
}

void main() {
  double arr[] = {9.5, 1.1, 2.2, 8.4, 5.9, 6.1};
  int n = sizeof(arr) / sizeof(arr[0]);

  /* Output original */
  printf("Original array: ");
  print_array(arr, n);

  /* Sort remaining args using Quicksort algorithm */
  qsort(arr, n, sizeof(double), compare);

  /* Output sorted */
  printf("Sorted array  : ");
  print_array(arr, n);
}

ここで浮動小数点数型の等号比較をしているのが気に入らない方は、丁寧に以下のように書いても良いでしょう。

// 追加のインクルードファイル
#include <float.h>
#include <math.h>

int compare(const void *v1, const void *v2 ) {
  const double a = *((double*)v1);
  const double b = *((double*)v2);
  if (fabs(a - b) <= DBL_EPSILON) return 0;
  else if (a < b) return -1;
  else return 1;
}

もっとも qsort では実質的に等号比較の結果を使っていないようなので、あまり気にする必要は無さそうです。

最後にスレッドを使う場合には、qsort はリエントラント(再入可能)では無いので、qsort_r というリエントラントなバージョンも用意されていることを覚えておいてください。まだリエントラントの説明をしていないのですが、ライブラリ関数を使うにも、いろいろ考慮する部分があるんですとだけ言っておきます。

実は、少々事情がありまして、少しテンポを早めています。だんだん課題もややこしくなってきたので、次の教室までに答案が間に合わないかもしれませんが、締め切ってしまうわけではないので、ご自身のテンポで挑戦していただければと思います。

さて、ソートもここまでとします。次回からは、ソースファイルの分割と、コンパイルとリンク、変数の種類とスコープなんてあたりに進む予定です。

ヘッダ画像は、いらすとや さんより
https://www.irasutoya.com/2020/04/blog-post_243.html

#C言語 #答え合わせ #プログラミング講座 #ソート #クイックソート #qsort #文字列の比較 #浮動小数点数の比較


この記事が気に入ったらサポートをしてみませんか？