アルゴリズムとデータ構造 補足資料 8-1
「クイックソート qsort.c 」
横浜国立大学 理工学部 数物・電子情報系学科 富井尚志
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 90 85 70 86 92 63 85
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 90 85 70 86 92 63 85
左端 lef
（定数）
右端 right
（定数）
真中
左端～右端の「区間」について、真中にある要素のキー（値）を基準にする。
・真中のキーよりも小さい要素は「左側」に移動。
・真中のキーよりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 90 85 70 86 92 63 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）を基準にする。
・真中のキーよりも小さい要素は「左側」に移動。
・真中のキーよりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
左候補 i
（変数）
「左側」の入替候補を探す
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 90 85 70 86 92 63 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
左候補 i
（変数）
基準より 比較：
小さい OK!
「左側」の入替候補を探す
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 90 85 70 86 92 63 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
左候補 i
（変数）
基準より 比較：
大きい NG!
「左側」の入替候補発見！
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 90 85 70 86 92 63 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
左候補 i
（変数）
右候補 j
（変数）
「右側」の入替候補を探す
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 90 85 70 86 92 63 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
左候補 i
（変数）
右候補 j
（変数）
基準より 比較：
大きい OK!
「右側」の入替候補を探す
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 90 85 70 86 92 63 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
左候補 i
（変数）
右候補 j
（変数）
基準より 比較：
小さい NG!
「右側」の入替候補発見！
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 90 85 70 86 92 63 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
左候補 i
（変数）
右候補 j
（変数）
「左側」の入替候補 「右側」の入替候補
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 90 85 70 86 92 63 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
左候補 i
（変数）
右候補 j
（変数）
「左側」の入替候補 「右側」の入替候補
入替
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 85 70 86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
左候補 i
（変数）
右候補 j
（変数）
「左側」の入替候補 「右側」の入替候補
90 入替 63
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 85 70 86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
左候補 i
（変数）
右候補 j
（変数）
入替
90
63
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 85 70 86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
左候補 i
（変数）
右候補 j
（変数）
90 63
左候補 i
（変数）
右候補 j
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 85 70 86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
90 63
左候補 i
（変数）
「左側」の入替候補を探す
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 85 70 86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
90 63
左候補 i
（変数）
「左側」の入替候補発見！
比較：
NG!
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 85 70 86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
90 63
左候補 i
（変数）
「右側」の入替候補を探す
右候補 j
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 85 70 86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
90 63
左候補 i
（変数）
比較：
OK!
「右側」の入替候補を探す
右候補 j
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 85 70 86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
90 63
左候補 i
（変数）
比較：
OK!
「右側」の入替候補を探す
右候補 j
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 85 70 86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
90 63
左候補 i
（変数）
比較：
NG!
「右側」の入替候補発見！
右候補 j
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 85 70 86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
90 63
左候補 i
（変数）
「右側」の入替候補
右候補 j
（変数）
「左側」の入替候補
入替
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
90 63
左候補 i
（変数）
「右側」の入替候補
右候補 j
（変数）
「左側」の入替候補
入替
70
85
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
90 63
左候補 i
（変数）
右候補 j
（変数）
入替
70 85
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
基準 x
（定数）
90 63
左候補 i
（変数）
右候補 j
（変数）
70 85
左候補 i
（変数）
右候補 j
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 63 70 85
左候補 i
（変数）
右候補 j
（変数）
i と j が逆転：
ここが分かれ目！
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 63 70 85
左端 i
↓ lef 右端
j
↓ right
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 63 70 85
左端 i
↓ lef 右端
j
↓ right
この区間をクイックソート
（再帰呼出）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3 件のデータ クイックソート
65
左端 lef
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
63 70
右端 j
↓ right
この区間をクイックソート
（再帰呼出）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3 件のデータ クイックソート
65
左端 lef
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
63 70
右端 right
（定数）
真中
63
基準 x
（定数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3 件のデータ クイックソート
65
左端 lef
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
63 70
右端 right
（定数）
63
基準 x
（定数）
左候補 i
（変数）
比較：
NG!
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3 件のデータ クイックソート
65
左端 lef
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
63 70
右端 right
（定数）
63
基準 x
（定数）
左候補 i
（変数）
比較：
OK!
右候補j
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3 件のデータ クイックソート
65
左端 lef
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
63 70
右端 right
（定数）
63
基準 x
（定数）
左候補 i
（変数）
比較：
NG!
右候補j
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3 件のデータ クイックソート
65
左端 lef
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
63 70
右端 right
（定数）
63
基準 x
（定数）
左候補 i
（変数）
右候補 j
（変数）
入替
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3 件のデータ クイックソート
65
左端 lef
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
63 70
右端 right
（定数）
63
基準 x
（定数）
左候補 i
（変数）
右候補 j
（変数）
入替
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3 件のデータ クイックソート
65
左端 lef
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
63 70
右端 right
（定数）
63
基準 x
（定数）
左候補 i
（変数）
右候補 j
（変数）
左候補 i
（変数）
右候補 j
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3 件のデータ クイックソート
65
左端 lef
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
63 70
右端 right
（定数）
63
基準 x
（定数）
左候補 i
（変数）
右候補 j
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3 件のデータ クイックソート
65
左端 lef
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
63 70
右端 right 左候補 （定数）
i
（変数）
右候補 j
（変数）
i と j が逆転：
ここが分かれ目！
左端 i
↓ lef 右端
j
↓ right
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3 件のデータ クイックソート
65
左端 lef
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
63 70
右端 right
（定数）
この区間は
ソート完了 この区間をクイックソート
（再帰呼出）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2 件のデータ クイックソート
65
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
右端 right
（定数）
左端 lef
（定数）
真中
65
基準 x
（定数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2 件のデータ クイックソート
65
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
右端 right
（定数）
左端 lef
（定数）
65
基準 x
（定数）
左候補 i
（変数）
比較：
NG!
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2 件のデータ クイックソート
65
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
右端 right
（定数）
左端 lef
（定数）
65
基準 x
（定数）
左候補 i
（変数）
比較：
OK!
右候補j
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2 件のデータ クイックソート
65
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
右端 right
（定数）
左端 lef
（定数）
65
基準 x
（定数）
左候補 i
（変数）
比較：
NG!
右候補 j
（変数）
右候補 j
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2 件のデータ クイックソート
65
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
右端 right
（定数）
左端 lef
（定数）左候補 i
（変数）
同じ場所を 指しているの
入替不要 で
右候補 j
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2 件のデータ クイックソート
65
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
右端 right
（定数）
左端 lef
（定数）左候補 i
（変数）
同じ場所を 指しているの
入替不要 で
左候補 i
（変数）
右候補 j
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2 件のデータ クイックソート
65
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
右端 right
（定数）
左端 lef
（定数） 左候補 i
（変数）
右候補 j
（変数）
lef と j が逆転：
ソート完了！ i と right が一致：
ソート完了！
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
2 件のデータ クイックソート
65
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
70
右端 right
（定数）
左端 lef
（定数） 左候補 i
（変数）
右候補 j
（変数）
lef と j が逆転：
ソート完了！ i と right が一致：
ソート完了！
呼び出し元に戻る
左端 i
↓ lef 右端
j
↓ right
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
3 件のデータ クイックソート
65
左端 lef
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
63 70
右端 right
（定数）
この区間をクイックソート
（再帰呼出）
ソート完了！ ↓ 呼び出し元に戻る
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 63 70 85
左端 i
↓ lef 右端
j
↓ right
この区間をクイックソート
（再帰呼出）
ソート完了！ ↓
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
8 件のデータ クイックソート
65 86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 63 70 85
左端 i
↓ lef 右端
j
↓ right
この区間をクイックソート
（再帰呼出）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5 件のデータ クイックソート
86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 85
この区間をクイックソート
（再帰呼出）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5 件のデータ クイックソート
86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 85
真中
92
基準 x
（定数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5 件のデータ クイックソート
86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 85
92
基準 x
（定数）
左候補 i
（変数）
比較：
OK!
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5 件のデータ クイックソート
86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 85
92
基準 x
（定数）
左候補 i
（変数）
比較：
OK!
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5 件のデータ クイックソート
86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 85
92
基準 x
（定数）
左候補 i
（変数）
比較：
NG!
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5 件のデータ クイックソート
86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 85
92
基準 x
（定数）
左候補 i
（変数）
比較：
NG!
右候補j
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5 件のデータ クイックソート
86 92 85
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 85
92
基準 x
（定数）
左候補 i
（変数）
右候補 j
（変数）
入替
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5 件のデータ クイックソート
86
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 85
92
基準 x
（定数）
左候補 i
（変数）
右候補 j
（変数）
92 85
入替
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5 件のデータ クイックソート
86
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 85
92
基準 x
（定数）
左候補 i
（変数）
右候補 j
（変数）
92 85
左候補 i
（変数）
右候補 j
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5 件のデータ クイックソート
86
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 85
92
基準 x
（定数）
92 85
左候補 i
（変数）
右候補 j
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5 件のデータ クイックソート
86
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 85
92
基準 x
（定数）
92 85
左候補 i
（変数）
比較 ：
OK!
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5 件のデータ クイックソート
86
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 85
92
基準 x
（定数）
92 85
左候補 i
（変数）
比較 ：
NG!
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5 件のデータ クイックソート
86
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 85
92
基準 x
（定数）
92 85
比較 ： NG!
右候補 j
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5 件のデータ クイックソート
86
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 85
92
基準 x
（定数）
92 85
右候補 j
（変数）
左候補 i
（変数）
解の方針：基準よりも小さいエリアと大きいエリアに分割する。
それぞれのエリアについて、同じ処理を行う（再帰呼び出し）。
5 件のデータ クイックソート
86
左端 lef
（定数）
右端 right
（定数）
左端～右端の「区間」について、真中にある要素のキー（値）をとりあえず基準にする。
・基準よりも小さい要素は「左側」に移動。
・基準よりも大きい要素は「右側」に移動。
→左右が逆になっている組み合わせを「入れ替える」！
90 85
92
基準 x
（定数）
92 85
右候補 j
（変数）
左候補 i
（変数）
