目次
概要
クイックソートとは、データを昇順、降順に並び替えるアルゴリズムの１つです。
例えば、
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