目次

概要
アルゴリズム
プログラム例

概要

クイックソートとは、データを昇順、降順に並び替えるアルゴリズムの１つです。

例えば、
99, 3, 4, 7, 55, 1, 6, 2という順列を与えると、
1, 2, 3, 4, 6, 7, 55, 99や 99, 55, 7, 6, 4, 3, 2, 1が求められます。

データを並び替える機能はCやPythonでは、qsort関数sort関数によって標準で搭載されています。

Fortranには同様の機能は標準で搭載されていませんので、クイックソートのプログラムを自分で書いて実装してみます。

クイックソートには`安定の保証がないデメリットがあります。
今回は単純な数列の並び替えを想定しますので、解説の対象外とします。
今後ソート関係の記事を書き終えたら個別に記事を作成して解説します。
[記事ができたらここにURLを入れる。]

アルゴリズム

アルゴリズムについての詳細な説明は既に多くのWebサイトで解説されていますので、本記事では説明を省略します。
参考として、以下のWebサイトのリンクを記載します。

プログラム例

99 3 4 7 55 1 6 2をクイックソートのアルゴリズムにより、昇順に並び替えてみます。

実行結果

途中過程を含めたクイックソートによる並び替えの過程を以下に示します。

【実行結果】長いので畳んでいます。　

元の順番 >>
99  3  4  7 55  1  6  2

【99  3  4  7 55  1  6  2 】を対象に調べます。
   STEP：１
          中央値： 7
   LOOP
     STEP：２
          【99】 から前進して【 7】より”小さい”かチェック
               NG : 99 >  7
     STEP：３
          【 2】 から後進して【 7】より”大きい”かチェック
               NG :  7 >  2
     STEP：４
          99 と  2 を入れ替えます。
               before : 99  3  4  7 55  1  6  2
               after  :  2  3  4  7 55  1  6 99
   LOOP
     STEP：２
          【 3】 から前進して【 7】より”小さい”かチェック
               OK :  3 <  7
               OK :  4 <  7
               NG :  7 >  7
     STEP：３
          【 6】 から後進して【 7】より”大きい”かチェック
               NG :  7 >  6
     STEP：４
           7 と  6 を入れ替えます。
               before :  2  3  4  7 55  1  6 99
               after  :  2  3  4  6 55  1  7 99
   LOOP
     STEP：２
          【55】 から前進して【 7】より”小さい”かチェック
               NG : 55 >  7
     STEP：３
          【 1】 から後進して【 7】より”大きい”かチェック
               NG :  7 >  1
     STEP：４
          55 と  1 を入れ替えます。
               before :  2  3  4  6 55  1  7 99
               after  :  2  3  4  6  1 55  7 99
   LOOP
     STEP：２
          【55】 から前進して【 7】より”小さい”かチェック
               NG : 55 >  7
     STEP：３
          【 1】 から後進して【 7】より”大きい”かチェック
               NG :  7 >  1
     GOAL
          分類結果(iとjがすれ違っているため終了)
           6           5
               前半部分： 2  3  4  6  1
               後半結果：55  7 99

【 2  3  4  6  1 】を対象に調べます。
     STEP：１
          中央値： 4
   LOOP
     STEP：２
          【 2】 から前進して【 4】より”小さい”かチェック
               OK :  2 <  4
               OK :  3 <  4
               NG :  4 >  4
     STEP：３
          【 1】 から後進して【 4】より”大きい”かチェック
               NG :  4 >  1
     STEP：４
           4 と  1 を入れ替えます。
               before :  2  3  4  6  1
               after  :  2  3  1  6  4
   LOOP
     STEP：２
          s【 6】 から前進して【 4】より”小さい”かチェック
               NG :  6 >  4
     STEP：３
          【 6】 から後進して【 4】より”大きい”かチェック
               OK :  4 <  6
               NG :  4 >  1
     GOAL
          分類結果(iとjがすれ違っているため終了)
           4           3
               前半部分： 2  3  1
               後半結果： 6  4

【 2  3  1 】を対象に調べます。
     STEP：１
          中央値： 3
   LOOP
     STEP：２
          【 2】 から前進して【 3】より”小さい”かチェック
               OK :  2 <  3
               NG :  3 >  3
     STEP：３
          【 1】 から後進して【 3】より”大きい”かチェック
               NG :  3 >  1
     STEP：４
           3 と  1 を入れ替えます。
               before :  2  3  1
               after  :  2  1  3
   LOOP
     STEP：２
          【 3】 から前進して【 3】より”小さい”かチェック
               NG :  3 >  3
     STEP：３
          【 1】 から後進して【 3】より”大きい”かチェック
               NG :  3 >  1
     GOAL
          分類結果(iとjがすれ違っているため終了)
           3           2
               前半部分： 2  1
               後半結果： 3

【 2  1 】を対象に調べます。
     STEP：１
          中央値： 2
   LOOP
     STEP：２
          【 2】 から前進して【 2】より”小さい”かチェック
               NG :  2 >  2
     STEP：３
          【 1】 から後進して【 2】より”大きい”かチェック
               NG :  2 >  1
     STEP：４
           2 と  1 を入れ替えます。
               before :  2  1
               after  :  1  2
   LOOP
     STEP：２
          【 2】 から前進して【 2】より”小さい”かチェック
               NG :  2 >  2
     STEP：３
          【 1】 から後進して【 2】より”大きい”かチェック
               NG :  2 >  1
     GOAL
          分類結果(iとjがすれ違っているため終了)
           2           1
               前半部分： 1
               後半結果： 2

【 6  4 】を対象に調べます。
     STEP：１
          中央値： 6
   LOOP
     STEP：２
          【 6】 から前進して【 6】より”小さい”かチェック
               NG :  6 >  6
     STEP：３
          【 4】 から後進して【 6】より”大きい”かチェック
               NG :  6 >  4
     STEP：４
           6 と  4 を入れ替えます。
               before :  1  2  3  6  4
               after  :  1  2  3  4  6
   LOOP
     STEP：２
          【 6】 から前進して【 6】より”小さい”かチェック
               NG :  6 >  6
     STEP：３
          【 4】 から後進して【 6】より”大きい”かチェック
               NG :  6 >  4
     GOAL
          分類結果(iとjがすれ違っているため終了)
           5           4
               前半部分： 4
               後半結果： 6

【55  7 99 】を対象に調べます。
     STEP：１
          中央値： 7
   LOOP
     STEP：２
          【55】 から前進して【 7】より”小さい”かチェック
               NG : 55 >  7
     STEP：３
          【99】 から後進して【 7】より”大きい”かチェック
               OK :  7 < 99
               NG :  7 >  7
     STEP：４
          55 と  7 を入れ替えます。
               before :  1  2  3  4  6 55  7 99
               after  :  1  2  3  4  6  7 55 99
   LOOP
     STEP：２
          【55】 から前進して【 7】より”小さい”かチェック
               NG : 55 >  7
     STEP：３
          【 7】 から後進して【 7】より”大きい”かチェック
               NG :  7 >  7
     GOAL
          分類結果(iとjがすれ違っているため終了)
           7           6
               前半部分： 7
               後半結果：55 99

【55 99 】を対象に調べます。
     STEP：１
          中央値：55
   LOOP
     STEP：２
          【55】 から前進して【55】より”小さい”かチェック
               NG : 55 > 55
     STEP：３
          【99】 から後進して【55】より”大きい”かチェック
               OK : 55 < 99
               NG : 55 > 55
     GOAL
          分類結果(iとjがすれ違っているため終了)
           7           7
               前半部分：55
               後半結果：99
並び替え後 >>
 1  2  3  4  6  7 55 99

サンプルプログラム

module global_variable
    implicit none
    ! グローバル変数
    integer(4) num(8)
    integer(4) N
    data num/99, 3, 4, 7, 55, 1, 6, 2/
end module
program ABC306c
    use global_variable
    N = size(num)
    !入力
    !並び替え前
    write (*, '(a)') '元の順番 >>'
    write (*, '(*(i2,1x))') num

    !並び替え
    call quicksort(num, 1, N)

    !結果の出力
    write (*, '(a)') '並び替え後 >>'
    write (*, '(*(i2,1x))') num
end
!sub:クイックソート
recursive subroutine quicksort(a, first, last)
    use global_variable
    implicit none
    integer(4) a(N), i, j, t, k
    integer(4) first, last, center

    i = first
    j = last
    write (*, '(/,a)', advance='no') '【'
    write (*, '(*(i2,1x),a)', advance='no') (a(k), k=i, j)
    write (*, '(a)') '】を対象に調べます。'
    !基準値の設定
    !先頭と末尾の平均を基準値とする例
    write (*, '(5x,a)') 'STEP：１'
    center = a(int((first + last)/2))
    write (*, '(10x,a,i2)') '中央値：', center
    do
        write (*, '(3X,a)') 'LOOP'

        !STEPX：中央値より"大きい"値を先頭から検索
        write (*, '(5x,a)') 'STEP：２'
        write (*, '(10x,a,i2,a,i2,a)') '【', a(i), '】 から前進して【', center, '】より”小さい”かチェック'
        do while (a(i) < center)
            write (*, '(15x,a,i2,a,i2)') 'OK : ', a(i), ' < ', center
            i = i + 1
        end do
        write (*, '(15x,a,i2,a,i2)') 'NG : ', a(i), ' > ', center

        !STEPX：中央値より"小さい"値を末尾から検索
        write (*, '(5x,a)') 'STEP：３'
        write (*, '(10x,a,i2,a,i2,a)') '【', a(j), '】 から後進して【', center, '】より”大きい”かチェック'
        do while (center < a(j))
            write (*, '(15x,a,i2,a,i2)') 'OK : ', center, ' < ', a(j)
            j = j - 1
        end do
        write (*, '(15x,a,i2,a,i2)') 'NG : ', center, ' > ', a(j)

        !GOAL：分類の終了
        if (i > j) then
            write (*, '(5x,a)') 'GOAL'
            write (*, '(10x,a,i2)') '分類結果(iとjがすれ違っているため終了)'
            write (*, *) i, j
            write (*, '(15x,a,*(i2,1x))') '前半部分：', (a(k), k=first, i - 1)
            write (*, '(15x,a,*(i2,1x))') '後半結果：', (a(k), k=i, last)
            exit
        else if (i == j) then
            write (*, '(5x,a)') 'GOAL'
            write (*, '(10x,a,i2)') '分類結果(iとjがすれ違っているため終了)'
            write (*, *) i, j
            write (*, '(15x,a,*(i2,1x))') '前半部分：', (a(k), k=first, i)
            write (*, '(15x,a,*(i2,1x))') '後半結果：', (a(k), k=i + 1, last)
            exit
        end if

        !STEPX：値の入れ替え
        write (*, '(5x,a)') 'STEP：４'
        write (*, '(10x,i2,a,i2,a)') a(i), ' と ', a(j), ' を入れ替えます。'
        write (*, '(15x,a,*(i2,1x))') 'before : ', (a(k), k=1, last)
        t = a(i); a(i) = a(j); a(j) = t
        i = i + 1
        j = j - 1
        write (*, '(15x,a,*(i2,1x))') 'after  : ', (a(k), k=1, last)
    end do
    !範囲を前半部分に絞って、再度行う
    if (first < i - 1) call quicksort(a, first, i - 1)
    !範囲を後半部分に絞って、再度行う
    if (j + 1 < last) call quicksort(a, j + 1, last)

end subroutine quicksort