HOME»基本情報技術者試験掲示板»大原本  問64  クイックソート
投稿する

大原本  問64  クイックソート [5436]

 まきさん(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さん(No.2) 
FE ゴールドマイスター
(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
返信投稿用フォーム

お名前

顔アイコン


本文(コミュニティガイドライン⇱を順守して適切な投稿を心がけましょう)

投稿削除用のパスワード(20文字以内)

投稿プレビュー
※CBT試験では出題内容の公開が禁止されているため、直接的・間接的を問わず、出題内容や難易度を尋ねる質問は厳禁です。
※宣伝や迷惑行為を防止するため、当サイトとIPAサイト以外のURLを含む文章の投稿は禁止されています。

投稿記事削除用フォーム

投稿No. パスワード 
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop