選択ソートは配列の整列されていない部分から最小値または最大値を持つ要素を探して、その値を未整列の先頭要素に移動(交換)することを繰り返して整列を行うアルゴリズムです。

プログラミングで配列は仮想的に整列済みと未整列の2つの部分に分けられます。未整列の先頭要素は整列済みの最後の要素と考えることができます。

アルゴリズム分析

配列の値を昇順(小さい順)に並び替える解説です。

A は配列で、 n を要素の数として説明します。[] 内の数値は配列のインデックスで範囲は 0 から n-1 です。

1. A[0] から A[n-1] で最小値を持つ要素を探し出し、それを A[0] と交換する。A[0] は整列済みとなる。
2. A[1] から A[n-1] で最小値を持つ要素を探し出し、それを A[1] と交換する。A[0] から A[1] は整列済みとなる。
3. A[2] から A[n-1] で最小値を持つ要素を探し出し、それを A[2] と交換する。A[0] から A[2] は整列済みとなる。
4. 未整列部分の先頭インデックスを [n-2] まで進めていき、最終的に A[n-2] から A[n-1] の範囲で最小値の検索と交換を行うと整列が完了する。

1度目の処理で A[0] に最小値が入り A[0] は整列済みとなるので、次の処理では未整列の部分は A[1] 以降の部分となります。また A[n-2] 以降の整列が完了すれば未整列の要素はただひとつ A[n-1] となっていますので n-1 回(要素数よりも1つ少ない回数)でソートが完了します。

最小値を探す方法は、未整列部分の要素の値をそれぞれ比較しながら最小値を持つ要素を示すインデックスを保持する一時変数を利用します。最小値の検索が終われば最小値の要素と未整列の先頭部分の要素の値を交換します。下で示すサンプルコードを見てもらうほうが理解しやすいと思います。

図解

値を昇順に(小さい順)に並び替える図解です。

特徴

バブルソート によく似たアルゴリズムですが、選択ソートでは最小値(または最大値)を未整列部分の先頭に移動させるだけなので、各ループでの値の交換回数が最大1回で済みます。最小値(または最大値)を探すために要素の値を繰り返し比較する回数は バブルソート と同じになります。バブルソートよりも交換回数が少ないので選択ソートの方が高速です。

サンプルコード

C言語

void selectionSort() が配列を昇順に並び替える選択ソートの実装です。

/*
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * This program demonstrates the use of the selection sort algorithm.  For
 * more information about this and other sorting algorithms, see
 * http://linux.wku.edu/~lamonml/kb.html
 * 
 */

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

#define NUM_ITEMS 100

void selectionSort(int numbers[], int array_size);
int numbers[NUM_ITEMS];

int main()
{
    int i;

    // seed random number generator
    srand(getpid());

    // fill array with random integers
    for (i = 0; i < NUM_ITEMS; i++) {
        numbers[i] = rand();
    }

    // perform selection sort on array
    selectionSort(numbers, NUM_ITEMS);

    printf("Done with sort.\n");

    for (i = 0; i < NUM_ITEMS; i++) {
        printf("%i\n", numbers[i]);
    }

    return 0;
}

void selectionSort(int numbers[], int array_size)
{
    int i; // 配列の先頭を指すインデックス
    int j; // 残りの要素を指すインデックス
    int min; // 最小値を持つ要素のインデックス
    int temp; // 交換用の一時変数

    for (i = 0; i < array_size-1; i++) {
        min = i; // 配列の先頭を最小値の要素とする
        for (j = i+1; j < array_size; j++) { // 比較のループ
            if (numbers[j] < numbers[min]) {
                min = j; // 最小値を持つ要素を更新
            }
        }
        // 最小値を持つ要素を先頭の要素と交換
        temp = numbers[i];
        numbers[i] = numbers[min];
        numbers[min] = temp;
    }
}

Python

def selectionsort(l):
    n = len(l)
    for index in range(n-1):
        least = index
        for x in range(index + 1, n):
            if l[x] < l[least]:
                least = x
        tmp = l[index]
        l[index] = l[least]
        l[least] = tmp
    return l

if __name__ == '__main__':
    from random import shuffle
    l = list(range(0, 15))
    lcopy = l[:]
    shuffle(l)
    print('Unsorted')
    print(l)
    assert l != lcopy
    print('Sorted')
    print(selectionsort(l))
    assert l == lcopy

選択ソートのデモンストレーション プログラム: selection-sort.py

• バブルソート
• 挿入ソート

---