大原本  問64  クイックソート

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】
まきさん  
(No.1)
クイックソートのプログラム問題です。
(1)(2)の動きはpivotと比較した時の動きなのですが
i←l-1 (1)、j←r+1 (2)となるのでしょうか?
分かる方ご教授お願い致します。


整数型:partition(整数型の配列:a,整数型 l,整数型 r)/l=左端 r=右端
整数型:i,j,pivot
flag←true
i←l-1 (1)
j←r+1 (2)
pivot←a[l]
do
 do
  i←i+1
  while(a[i]> pivot)(3)
 do
  j←j-1
  while(a[i]< pivot)(4)
  
 if(i<j)
 a[i]とa[j]を交換

else
 flg←false
 endif

 while(flg=true)
  return j
2024.05.08 17:09
jjon-comさん 
FE ゴールドマイスター
(No.2)
(3)誤  while (a[i] > pivot)
(3)正  while (a[i] < pivot)

(4)誤  while (a[i] < pivot)
(4)正  while (a[j] > pivot)

です。これを訂正した上で回答します。

--------
i←L-1 (1)
j←R+1 (2)
pivot←a[L]
do
  do
    i←i+1 (1b)
  while (a[i] < pivot)(3)正
  do
    j←j-1 (2b)
  while (a[j] > pivot)(4)正

(1)で配列の左端(L)のさらに1つ左隣(L-1)を指しておくことで,
その後(1b)を実行したときに正しく配列の左端(L)を指すようになります。

(2)で配列の右端(R)のさらに1つ右隣(R+1)を指しておくことで,
その後(2b)を実行したときに正しく配列の左端(R)を指すようになります。

--------
この
基本情報技術者[科目B]アルゴリズムとプログラミング トレーニング問題集 第2版 (大原出版)
という書籍は,
アルゴリズムの問題がたくさん掲載されているので重宝がられているようですが,
雑なコーディングが散見されます。

このアルゴリズムが本番の科目B試験で出題されるのなら,
後判断のwhileではなく前判断のwhileを用いて,
次のようにアルゴリズムの意味を素直にコードに落とし込んだ出題をすることでしょう。

i←L
j←R
pivot←a[L]
do
  while (a[i] < pivot)
    i←i+1
  endwhile
  while (a[j] > pivot)
    j←j-1
  endwhile
2024.05.09 14:15
まきさん  
(No.3)
>jjon-comさん
いつもお世話になっております。
解説ありがとうございました。
後判定するから
(1)l-1  (2)r+1となることが分かりました
(3)(4)のご指摘ありがとうございます。
ピボット以下か以上で分かれることが分かっていませんでした。
☆なお、しない場合は上記の通りで間違えありません。
2024.05.09 20:13

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの投稿はできません。

その他のスレッド


Pagetop