選択ソートって実はこんなのでした！

AyumiKatayama

2023年6月6日 07:28

間違っていた選択ソート

先日来、バブルソートはこんなのだ、選択ソートはあんなのだなどと書いてきましたが、こちらの記事のコメントで遊月さんからご指摘いただきました。

「それって、選択ソートと違うんじゃない？」

そう！
あれは選択ソートではなかったんです！orz

そして正しい選択ソート

改めて。
こちらが選択ソートです。

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

int cnt = 0;
void sort(int *array, unsigned int size) {
  for (int k = 0; k < size; k++) printf("%d ", array[k]); 
  printf("\n");

  for (int i = 0; i < size - 1; i++) {
    int min = i;
    for (int j = i+1; j < size; j++) {
      if (array[min] > array[j]) {
        min = j;
      }
    }
    if (min != i) {
      int temp = array[min];
      array[min] = array[i];
      array[i] = temp;
	  cnt++;
 	  for (int k = 0; k < size; k++) printf("%d ", array[k]); 
  	  printf("\n");
    }
  }
  printf("sort swaped %d\n ", cnt);
  printf("\n");
}

int main() {
  int data[10] = {6, 3, 8, 9, 5, 4, 1, 7, 0, 2};

  unsigned int size = sizeof(data) / sizeof(data[0]);
  sort(data, size);

  return 0;
}

ついでに、実行結果はこちら。

6 3 8 9 5 4 1 7 0 2
0 3 8 9 5 4 1 7 6 2
0 1 8 9 5 4 3 7 6 2
0 1 2 9 5 4 3 7 6 8
0 1 2 3 5 4 9 7 6 8
0 1 2 3 4 5 9 7 6 8
0 1 2 3 4 5 6 7 9 8
0 1 2 3 4 5 6 7 8 9

数字の羅列だけでは面白くないので、ちょっと塗り絵してみました。
ピンクは後ろに移動した数字
青は前に移動した数字です。

ちなみに、前回までの「バブルソート風選択ソート」だとこんな感じ。

一目瞭然ですね。
かなり余分に数字が動いています。
「７」などは元の位置から動かなくていいものを、あっちに行ったりこっちに行ったりしています。
「でも、バブルソートよりはマシなのではないか」とも感じるのですが、バブルソートは、実は途中で止めることができます。常に全点検しているので一度も交換しなければそこでソート完了と判断できるのです。でも、このソートの場合はそれはできません。先頭のみしか比較していないので、一度も交換しなかったとしても、2番目、3番目がどうなるのか判断できないためです。

も一つついでに、バブルソートはこんな風になります。

今回の間違いについて

そもそもは、AI に聞いたことが発端でした。
AI を鵜呑みにしたわけではありません。
一応、Wikiも参照したのですが、先頭の日本語解説だけで判断しました。後方に記載されているアルゴリズムを見れば間違えなかったものを。手を抜くとこういうことになるという、いい見本です。

謝辞

遊月さん、ご指摘ありがとうございました。
大変、助かりました。
これからもよろしくお願いします。