スライド 1

アルゴリズムとデータ構造
補足資料8-1
「クイックソートqsort.c」
横浜国立大学
理工学部
数物・電子情報系学科
富井尚志
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 90 85 70 86 92 63 85
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 90 85 70 86 92 63 85
左端
left
（定数）
真中
右端
right
（定数）
70
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）を基準にする。
・真中のキーよりも小さい要素は「左側」に移動。
・真中のキーよりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 90 85 70 86 92 63 85
左端
left
（定数）
左候補
i
（変数）
「左側」の入替候補を探す
右端
right
（定数）
70
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）を基準にする。
・真中のキーよりも小さい要素は「左側」に移動。
・真中のキーよりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 90 85 70 86 92 63 85
左端
left
（定数）
左候補
i
（変数）
比較：
基準より
小さい
OK!
「左側」の入替候補を探す
右端
right
（定数）
70
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 90 85 70 86 92 63 85
左端
left
（定数）
左候補
i
（変数）
比較：
基準より
大きい
NG!
「左側」の入替候補発見！
右端
right
（定数）
70
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 90 85 70 86 92 63 85
左端
left
（定数）
右端
right
（定数）
右候補
j
（変数）
左候補
i
（変数）
70
「右側」の入替候補を探す
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 90 85 70 86 92 63 85
左端
left
（定数）
比較：
基準より
大きい
OK!
左候補
i
（変数）
70
右端
right
（定数）
右候補
j
（変数）
「右側」の入替候補を探す
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 90 85 70 86 92 63 85
左端
left
（定数）
比較：
基準より
小さい
NG!
左候補
i
（変数）
70
右候補
j
（変数）
右端
right
（定数）
「右側」の入替候補発見！
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 90 85 70 86 92 63 85
左端
left
（定数）
左候補
i
（変数）
「左側」の入替候補
右候補
j
（変数）
70
右端
right
（定数）
「右側」の入替候補
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 90 85 70 86 92 63 85
左端
left
（定数）
入替
左候補
i
（変数）
「左側」の入替候補
右候補
j
（変数）
70
右端
right
（定数）
「右側」の入替候補
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65
左端
left
（定数）
85 70 86 92
90
入替
左候補
i
（変数）
「左側」の入替候補
85
63
右候補
j
（変数）
70
右端
right
（定数）
「右側」の入替候補
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 63 85 70 86 92 90 85
左端
left
（定数）
入替
左候補
i
（変数）
右候補
j
（変数）
右端
right
（定数）
70
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 63 85 70 86 92 90 85
左端
left
（定数）
左候補
i
（変数）
左候補
i
（変数）
右候補
j
（変数）
右候補
j
（変数）
右端
right
（定数）
70
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 63 85 70 86 92 90 85
左端
left
（定数）
右端
right
（定数）
左候補
i
（変数）
「左側」の入替候補を探す
70
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 63 85 70 86 92 90 85
左端
left
（定数）
左候補
i
（変数）
「左側」の入替候補発見！
比較：
NG!
右端
right
（定数）
70
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 63 85 70 86 92 90 85
左端
left
（定数）
左候補
i
（変数）
右候補
j
（変数）
70
右端
right
（定数）
「右側」の入替候補を探す
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 63 85 70 86 92 90 85
左端
left
（定数）
比較：
OK!
左候補
i
（変数）
70
右候補
j
（変数）
右端
right
（定数）
「右側」の入替候補を探す
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 63 85 70 86 92 90 85
左端
left
（定数）
左候補
i
（変数）
比較：
OK!
70
右候補
j
（変数）
右端
right
（定数）
「右側」の入替候補を探す
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 63 85 70 86 92 90 85
左端
left
（定数）
左候補
i
（変数）
比較：
NG!右候補
右端
right
（定数）
j
（変数）
70
「右側」の入替候補発見！
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 63 85 70 86 92 90 85
左端
left
（定数）
「左側」の入替候補
入替
左候補
i
（変数）
右候補
j
（変数）
70
右端
right
（定数）
「右側」の入替候補
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 63
左端
left
（定数）
「左側」の入替候補
85 70
入替
左候補
i
（変数）
右候補
j
（変数）
70
86 92 90 85
右端
right
（定数）
「右側」の入替候補
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 63 70 85 86 92 90 85
左端
left
（定数）
入替
左候補
i
（変数）
右候補
j
（変数）
右端
right
（定数）
70
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 63 70 85 86 92 90 85
左端
left
（定数）
左候補右候補左候補右候補
i
j
i
j
（変数）（変数）（変数）（変数）
右端
right
（定数）
70
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 63 70 85 86 92 90 85
左端
left
（定数）
右候補左候補
j
i
（変数）（変数）
右端
right
（定数）
iとjが逆転：
ここが分かれ目！
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 63 70 85 86 92 90 85
左端
left
（定数）
右端
j
↓
right
左端
i
↓
left
右端
right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
65 63 70 85 86 92 90 85
左端
left
（定数）
この区間をクイックソート
（再帰呼出）
右端
j
↓
right
左端
i
↓
left
右端
right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3件のデータ
65 63 70
左端
left
（定数）
この区間をクイックソート
（再帰呼出）
右端
j
↓
right
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3件のデータ
65 63 70
左端
left
（定数）
真中
右端
right
（定数）
63
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3件のデータ
65 63 70
左端
left
（定数）
左候補
i
（変数）
比較：
NG!
右端
right
（定数）
63
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3件のデータ
65 63 70
左端
left
（定数）
左候補
i
（変数）
比較：
OK!
右端
right
（定数）
右候補
j
（変数）
63
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3件のデータ
65 63 70
左端
left
（定数）
左候補
i
（変数）
比較：
NG! 右候補
右端
right
（定数）
j
（変数）
63
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3件のデータ
65 63 70
左端
left
（定数）
左候補
i
（変数）
入替
右候補
j
（変数）
右端
right
（定数）
63
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3件のデータ
63 65 70
左端
left
（定数）
左候補
i
（変数）
入替
右候補
j
（変数）
右端
right
（定数）
63
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3件のデータ
63 65 70
左端
left
（定数）
左候補
右候補
i j
（変数）
（変数）
左候補
右候補
i j
（変数）
（変数）
右端
right
（定数）
63
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3件のデータ
63 65 70
左端
left
（定数）
右候補
j
（変数）
左候補
i
（変数）
右端
right
（定数）
63
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3件のデータ
63 65 70
左端
left
（定数）
右候補
j
（変数）
左候補
i
（変数）
右端
right
（定数）
iとjが逆転：
ここが分かれ目！
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3件のデータ
63 65 70
左端
left
（定数）
右端
j
↓
right
左端
i
↓
left
右端
right
（定数）
この区間はこの区間をクイックソート
ソート完了
（再帰呼出）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
65 70
左端真中
left
（定数）
右端
right
（定数）
65
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
65 70
左端
left
（定数）
左候補
i
（変数）
比較：
NG!
右端
right
（定数）
65
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
65 70
左端
left
（定数）
左候補
i
（変数）
右端
比較： right
（定数）
OK!右候補
j
（変数）
65
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
65 70
左端
left
（定数）
左候補
右候補
i
j
（変数）
（変数）
右端
right
（定数）
比較：
NG!
65
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
65 70
左端
left
（定数）
左候補
右候補
i
j
（変数）
（変数）
右端
right
（定数）
同じ場所を
指しているので
入替不要
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
65 70
右候補
j
（変数）
左端
右端
left
right
（定数）
（定数）
左候補
右候補左候補
i
j
i
（変数）
（変数）（変数）
同じ場所を
指しているので
入替不要
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
65 70
右候補
j
（変数）
左端
left
（定数）
leftとjが逆転：
ソート完了！
右端
right
（定数）
左候補
i
（変数）
iとrightが一致：
ソート完了！
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
65 70
右候補
j
（変数）
左端
left
（定数）
leftとjが逆転：
ソート完了！
右端
right
（定数）
左候補
i
（変数）
iとrightが一致：
ソート完了！
呼び出し元に戻る
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3件のデータ
63 65 70
左端
left
（定数）
右端
j
↓
right
左端
i
↓
left
右端
right
（定数）
この区間をクイックソート
（再帰呼出）
↓
ソート完了！
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
呼び出し元に戻る
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
63 65 70 85 86 92 90 85
左端
left
（定数）
この区間をクイックソート
（再帰呼出）
↓
ソート完了！
右端
j
↓
right
左端
i
↓
left
右端
right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
63 65 70 85 86 92 90 85
左端
left
（定数）
右端
j
↓
right
左端
i
↓
left
右端
right
（定数）
この区間をクイックソート
（再帰呼出）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 86 92 90 85
左端
left
（定数）
右端
right
（定数）
この区間をクイックソート
（再帰呼出）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 86 92 90 85
左端
left
（定数）
真中
右端
right
（定数）
92
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 86 92 90 85
左端
left
（定数）
左候補
i
（変数）
右端
right
（定数）
比較：
OK!
92
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 86 92 90 85
左端
left
（定数）
左候補
i
（変数）
比較：
OK!
右端
right
（定数）
92
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 86 92 90 85
左端
left
（定数）
比較：
左候補NG!
右端
right
（定数）
i
（変数）
92
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 86 92 90 85
左端
left
（定数）
左候補
i
（変数）
比較：
NG!
右端
right
（定数）
右候補
j
（変数）
92
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 86 92 90 85
左端
left
（定数）
入替
左候補
i
（変数）
右端
right
（定数）
右候補
j
（変数）
92
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 86 85 90 92
左端
left
（定数）
入替
左候補
i
（変数）
右端
right
（定数）
右候補
j
（変数）
92
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 86 85 90 92
左端
left
（定数）
左候補
i
（変数）
左候補
右候補
i
j
（変数）
（変数）
右端
right
（定数）
右候補
j
（変数）
92
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 86 85 90 92
左端
left
（定数）
左候補
右候補
i
j
（変数）
（変数）
右端
right
（定数）
92
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 86 85 90 92
左端
left
（定数）
比較：
OK!
左候補
i
（変数）
右端
right
（定数）
92
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 86 85 90 92
左端
left
（定数）
比較：
NG!
右端
right
（定数）
左候補
i
（変数）
92
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 86 85 90 92
左端
left
（定数）
比較：
NG!
右候補
j
（変数）
右端
right
（定数）
92
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 86 85 90 92
左端
left
（定数）
右端
right
（定数）
右候補左候補
j
i
（変数）（変数）
92
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 86 85 90 92
左端
left
（定数）
右端
right
（定数）
右候補左候補
j
i
（変数）（変数）
92
基準
x
（定数）
逆転している
ので
入替不要
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 86 85 90 92
左端
left
（定数）
右端
right
（定数）
右候補左候補
j
i
（変数）（変数）
92
iとjが逆転：
ここが分かれ目！
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 86 85 90 92
左端
left
（定数）
この区間をクイックソート
（再帰呼出）
右端
j
↓
right
右端
right
（定数）
左端
i
↓
left
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
4件のデータ
85 86 85 90
左端
left
（定数）
この区間をクイックソート
（再帰呼出）
右端
right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
4件のデータ
85 86 85 90
左端
left
（定数）
右端
right
（定数）
真中
86
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
4件のデータ
85 86 85 90
左端
left
（定数）
左候補
i
（変数）
右端
right
（定数）
比較：
OK!
86
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
4件のデータ
85 86 85 90
左端
left
（定数）
左候補
i
（変数）
比較：
NG!
右端
right
（定数）
86
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
4件のデータ
85 86 85 90
左端
left
（定数）
左候補
i
（変数）
比較：
OK!
右端
right
（定数）
右候補
j
（変数）
86
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
4件のデータ
85 86 85 90
左端
left
（定数）
左候補
i
（変数）
比較：
NG!
右候補
j
（変数）
右端
right
（定数）
86
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
4件のデータ
85 86 85 90
左端
left
（定数）
入替
左候補
i
（変数）
右候補
j
（変数）
右端
right
（定数）
86
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
4件のデータ
85 85 86 90
左端
left
（定数）
入替
左候補
i
（変数）
右候補
j
（変数）
右端
right
（定数）
86
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
4件のデータ
85 85 86 90
左端
left
（定数）
左候補右候補左候補右候補
i
j
i
j
（変数）（変数）（変数）（変数）
右端
right
（定数）
86
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
4件のデータ
85 85 86 90
左端
left
（定数）
右候補左候補
j
i
（変数）（変数）
右端
right
（定数）
iとjが逆転：
ここが分かれ目！
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
4件のデータ
85 85 86 90
左端
left
（定数）
右端
j
↓
right
左端
i
↓
left
右端
right
（定数）
この区間をクイックソート
（再帰呼出）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
85 85
左端
left
（定数）
右端
right
（定数）
この区間をクイックソート
（再帰呼出）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
85 85
左端真中
left
（定数）
右端
right
（定数）
85
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
85 85
左端
left
（定数）
左候補
i
（変数）
比較：
NG!
右端
right
（定数）
85
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
85 85
左端
右端
比較： right
left
（定数）
NG!右候補（定数）
左候補
i
j
（変数）
（変数）
85
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
85 85
入替
左端
left
（定数）
左候補
i
（変数）
右端
right
（定数）
右候補
j
（変数）
85
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
85 85
入替
左端
left
（定数）
左候補
i
（変数）
右端
right
（定数）
右候補
j
（変数）
85
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
85 85
左端
右端
left
right
（定数）
（定数）
左候補
右候補
左候補
右候補
i
j
i j
（変数）
（変数）
（変数）
（変数）
85
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
85 85
左端
left
（定数）
右候補
左候補
j
i
（変数）
（変数）
右端
right
（定数）
iとjが逆転：
ここが分かれ目！
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
85 85
左端
left
（定数）
右端左端
j
i
↓ ↓
right left
右端
right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
85 85
左端
left
（定数）
右端左端
j
i
↓ ↓
right left
この区間は
ソート完了
右端
right
（定数）
呼び出し元に戻る
この区間は
ソート完了
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
4件のデータ
85 85 86 90
左端
left
（定数）
右端
j
↓
right
左端
i
↓
left
右端
right
（定数）
この区間をクイックソート
（再帰呼出）
↓
ソート完了！
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
4件のデータ
85 85 86 90
左端
left
（定数）
右端
j
↓
right
左端
i
↓
left
右端
right
（定数）
この区間をクイックソート
（再帰呼出）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
86 90
左端
left
（定数）
右端
right
（定数）
この区間をクイックソート
（再帰呼出）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
86 90
左端真中
left
（定数）
右端
right
（定数）
86
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
86 90
左端
left
（定数）
左候補
i
（変数）
比較：
NG!
右端
right
（定数）
86
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
86 90
左端
left
（定数）
左候補
i
（変数）
右端
比較： right
（定数）
OK!右候補
j
（変数）
86
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
86 90
左端
右端
比較： right
left
（定数）
OK! （定数）
左候補
右候補
i j
（変数）
（変数）
86
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
86 90
右候補
j
（変数）
左端
右端
比較： right
left
（定数）
（定数）
OK!左候補
左候補
右候補
i j
i
（変数）
（変数）
（変数）
86
基準
x
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2件のデータ
86 90
右候補
j
（変数）
左端
left
（定数）
leftとjが逆転：
ソート完了！
右端
right
（定数）
左候補
i
（変数）
iとrightが一致：
ソート完了！
呼び出し元に戻る
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
4件のデータ
85 85 86 90
左端
left
（定数）
右端
j
↓
right
左端
i
↓
left
右端
right
（定数）
この区間をクイックソート
（再帰呼出）
↓
ソート完了！
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
呼び出し元に戻る
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 85 86 90 92
左端
left
（定数）
この区間をクイックソート
（再帰呼出）
↓
ソート完了！
右端
j
↓
right
右端
right
（定数）
左端
i
↓
left
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5件のデータ
85 85 86 90 92
左端
left
（定数）
右端
j
↓
right
呼び出し元に戻る
右端
right
（定数）
左端
i
↓
left
iとrightが一致：
ソート完了！
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8件のデータ
63 65 70 85 85 86 90 92
左端
left
（定数）
右端
j
↓
right
左端
i
↓
left
右端
right
（定数）
この区間をクイックソート
（再帰呼出）
↓
ソート完了！
呼び出し元に戻る→mainへ
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
n件のデータ
未整列
基準
n回の比較,1～n/2回の入替
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
n件のデータ
未整列
基準
基準より小さい要素
n回の比較,1～n/2回の入替
基準より大きい要素
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
n件のデータ
未整列
基準
基準より小さい要素
再帰
呼出
n回の比較,1～n/2回の入替
基準より大きい要素
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
n件のデータ
未整列
基準
基準より小さい要素
再帰
呼出
再帰
呼出
n回の比較,1～n/2回の入替
基準より大きい要素
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
n件のデータ
未整列
基準
基準より小さい要素
再帰
呼出
再帰
呼出
再帰
呼出
n回の比較,1～n/2回の入替
基準より大きい要素
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
n件のデータ
未整列
基準
基準より小さい要素
再帰
呼出
再帰
呼出
再帰
呼出
再帰
呼出
n回の比較,1～n/2回の入替
基準より大きい要素
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
n件のデータ
未整列
基準
基準より小さい要素
再帰
呼出
再帰
呼出
再帰
呼出
再帰
呼出
n回の比較,1～n/2回の入替
基準より大きい要素
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
n件のデータ
未整列
基準
基準より小さい要素
再帰
呼出
再帰
呼出
再帰
呼出
再帰
呼出
再帰
呼出
n回の比較,1～n/2回の入替
基準より大きい要素
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
n件のデータ
未整列
基準
基準より小さい要素
再帰
呼出
再帰
呼出
再帰
呼出
再帰
呼出
再帰
呼出
再帰
呼出
n回の比較,1～n/2回の入替
基準より大きい要素
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
n件のデータ
未整列
基準
基準より小さい要素
基準より大きい要素
再帰
呼出
再帰
呼出
再帰
呼出
再帰
呼出
再帰
呼出
再帰
呼出
n回の比較,1～n/2回の入替
再帰
呼出
クイックソート
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
n件のデータ
未整列
基準
n回の比較,1～n/2回の入替
基準より小さい要素
基準より大きい要素
再帰
呼出
再帰
呼出
log2 n
再帰
呼出
再帰
呼出
再帰
呼出
再帰
呼出
再帰
呼出
再帰
呼出
再帰
呼出
再帰
呼出
再帰
呼出
再帰
呼出
再帰
呼出
O(n x log n)の比較・入替
再帰
呼出
データ件数
O( 1 )
O(log n)
O(n)
O(n x log n)
1,000
1,000,000
1,000,000,000
1
1
1
10
20
30
1,000
1,000,000
1,000,000,000
10,000
20,000,000
30,000,000,000
2
O(n )
1,000,000
O(2n)
10300
1,000,000,000,000 1,000,000,000,000,000,000
10300,000
10300,000,000
1回あたり1ms ( = 10-3 sec )で計算できる場合
データ件数
1,000
O( 1 )
O(log n)
O(n)
O(n x log n)
2
O(n )
O(2n)
1,000,000
1,000,000,000
1 msec
1msec
1msec
10 msec
20 msec
30 msec
1 sec
1,000 sec
10 sec
2x104 sec
(5.5h)
1,000 sec
10297sec
10290 年
宇宙の歴史10280 回
109 sec
(30年)
10299,997 sec
1,000,000 sec
(11日)
3x107sec
(1年)
1015 sec
(3千万年)
10299,999,997 sec
1回あたり0.1ns ( = 10-10 sec )で計算できる場合： 1,000万倍速い計算機
データ件数
1,000
O( 1 )
10-10 sec
O(log n)
10-9 sec
O(n)
10-7 sec
1,000,000
1,000,000,000
10-10 sec
10-10 sec
2x10-9 sec
3x10-9 sec
10-4 sec
10-1 sec
3 sec
O(n x log n)
10-6 sec
2x10-3 sec
2
O(n )
10-4 sec
100 sec
108 sec
(3年)
10299,990 sec
10299,999,990 sec
O(2n)
10290 sec
10282 年
宇宙の歴史10272 回

Download Report