こんにちは、フルスタックエンジニアのryuです。
今回の記事は、基本情報技術者試験過去問解説です。クイックソートの処理方法についての問題を解説します。クイックソートとは、プログラムのアルゴリズムの1つで、データを整列するためのものです。今回の記事では、クイックソートについて解説します。
クイックソートの処理方法を説明したものはどれか
今回の記事では、以下の問題について解説します。
クイックソートの処理方法を説明したものはどれか。
ア:既に整列済みのデータ列の正しい位置に，データを追加する操作を繰り返していく方法である。
イ:データ中の最小値を求め，次にそれを除いた部分の中から最小値を求める。この操作を繰り返していく方法である。
ウ:適当な基準値を選び，それより小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。
エ:隣り合ったデータの比較と入替えを繰り返すことによって，小さな値のデータを次第に端のほうに移していく方法である。
答えは、『ウ』の「適当な基準値を選び，それより小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。」です。
今回はクイックソートについて詳しく解説します。
クイックソートとは？
ここからは、クイックソートについて解説します。
クイックソートとは分割して並び替えるアルゴリズム
クイックソートとは、データを分割して並び替えるアルゴリズムです。名前の通り高速で並び替えることができます。
クイックソートは、ある基準値を決め、それよりも大きいグループと小さいグループに分けます。さらにそれらのグループでも基準値を決めて分割していき、データを並べ替えるアルゴリズムです。
クイックソートの動きについてはこちらの動画が分かりやすいです。百聞は一見に如かず。流れを見てみましょう。
クイックソートを実装してみる
クイックソートを実際にプログラミングしてみましょう。pythonで実装すると以下のようになります。
まずは、クイックソートの関数を作成します。
def quick_sort(arr):
left = []
right = []
if len(arr) <= 1:
return arr
# データの状態に左右されないためにrandom.choice()を用いることもある。
# ref = random.choice(arr)
ref = arr[0]
ref_count = 0
for ele in arr:
if ele < ref:
left.append(ele)
elif ele > ref:
right.append(ele)
else:
ref_count += 1
left = quick_sort(left)
right = quick_sort(right)
return left + [ref] * ref_count + right関数の作成が完了したら、配列を用意して、関数を実行してみましょう。
#適当な数字を入れる
arr = [8,10,9,1,34,4,3,7,5,1]
sort = quick_sort(arr)
print(sort)
#[1, 1, 3, 4, 5, 7, 8, 9, 10, 34]と表示される参考:ソートアルゴリズムと Python での実装 – Qiita
実装してみると、どのような動きをしているのか分るので試してみましょう！GoogleColaboratoryを使うとブラウザで実行することができます。以下のリンクからどうぞ。
Colaboratory へようこそ – Colaboratory (google.com)
アルゴリズムについては、こちらの参考書を読むと理解が深まります。
過去問解説まとめ
今回の記事では、以下の問題について解説しました。
クイックソートの処理方法を説明したものはどれか。
ア:既に整列済みのデータ列の正しい位置に，データを追加する操作を繰り返していく方法である。
イ:データ中の最小値を求め，次にそれを除いた部分の中から最小値を求める。この操作を繰り返していく方法である。
ウ:適当な基準値を選び，それより小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。
エ:隣り合ったデータの比較と入替えを繰り返すことによって，小さな値のデータを次第に端のほうに移していく方法である。
答えは、『ウ』です。その他の選択肢については、以下の通り。
- ア→基本挿入法の説明
- イ→基本選択法の説明
- エ→バブルソート(基本交換法)の説明
以上で解説を終わります。当ブログでは、このようなネットワークに関する内容や基本情報技術者試験の過去問解説をしているので興味のある方は引き続きご覧ください。
