アルゴリズム：クイックソートについて

Question

画像ですみません

テキストを購入しクイックソートを学んでいるのですが、下記画像の疑似コードでわからないところがあります。

副プログラムArrangeについて

仕組みや全体像はわかるのですが、Arrangeの中身について、L≦Rの次の行ですぐにLRを入れ替えています。

A[3,5,8,4,0,6,9,1,2,7]
が与えられていたとして、一巡目では
Arrange(A[],0,9,5,Ret)
が読み込まれると思うのですが、このままではA[0]=3とA[9]=7を入れ替えねばなりません。

しかし設問では
１回目　A[3,5,8,4,0,6,9,1,2,7]　Min=0 Max=9
２回目　A[3,2,1,4,0,6,9,8,5,7]　Min=0 Max=4
３回目　空欄問題
となっています。

3と7はどの段階で入れ替えを免れたのでしょうか。
教えていただけると助かります。　

※閲覧に対し回答が得られないため知恵袋にも投稿しております
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q11259032066?post=1

Comments

[1T2R3M4]

https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q13259030753

以下ご対応ください。
https://teratail.com/help#posted-otherservice

Answer 1

質問への追記を求めるのも面倒なので、エスパーして教科書の実装を完成させた上で回答します。

3と7はどの段階で入れ替えを免れたのでしょうか。

1回目に通る Arrange では想像されている通り、一度 A[0] と A[9] を交換しています。しかし、A[0] が Pivot よりも小さくなければ A[0] を再び A[R] と交換しようとしています。同様に A[9] が Pivot よりも大きくなければ A[9] を A[L] と再び交換しようとしています。

つまり、Arrange の while ループの1回目では、3 と 7 を交換しますが、その直後、2回目のループで 3 と 7 を元に戻しています。

その結果、まるで 3 と 7 の交換がなかったように QuickSort の1回目が終了しています。説明はこれでよいでしょうか。

#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0

void debug(int A[], int Min, int Max) {
  int i;
  for (i = 0; i < 10; ++i) {
    if (i > 0) printf(", ");
    printf("%d", A[i]);
  }
  puts("");
}

void Arrange(int A[], int Min, int Max, int Pivot, int *Ret) {
  int L, R, Tmp;

  L = Min;
  R = Max;
  while (L <= R) {
    Tmp = A[L];
    A[L] = A[R];
    A[R] = Tmp;
    while (A[L] < Pivot) {
      L += 1;
    }
    while (A[R] >= Pivot) {
      R -= 1;
    }
  }
  *Ret = L;
}

void FindPivot(int A[], int Min, int Max, int *Ret) {
  int Pivot, K, Found;
  Pivot = A[Min];
  K = Min + 1;
  *Ret = -1;
  Found = false;

  while (K <= Max && !Found) {
    if (A[K] == Pivot) {
      K += 1;
    }
    else {
      Found = true;

      if (A[K] > Pivot) {
        *Ret = K;
      }
      else {
        *Ret = Min;
      }
    }
  }
}

void QuickSort(int A[], int Min, int Max) {
  int Pivot, J, K, L;
  debug(A, Min, Max);

  FindPivot(A, Min, Max, &J);
  if (J > -1) {
    Pivot = A[J];
    Arrange(A, Min, Max, Pivot, &K);
    L = K - 1;
    QuickSort(A, Min, L);
    QuickSort(A, K, Max);
  }
}

int main() {
  int A[10] = {3,5,8,4,0,6,9,1,2,7};
  QuickSort(A, 0, 9);
  return 0;
}

Comments

[Jorrvaskr_prg]

アルゴリズムの参考書なので実装などは無いのです。このページ前後は設問のみです。
L<Pivot等を無視して二週目に入りもとに戻る、という思考に至りませんでした。
その上でトレースしたところ設問解説通りに進行することができました。
ありがとうございました。

[arcxor]

> アルゴリズムの参考書なので実装などは無いのです

そのアルゴリズムが隠されているわ、四角・三角区間の説明は無いわで回答が非常に困難でした。

[Jorrvaskr_prg]

これは煽りでもなんでもなく無知故の疑問なのですが、
アルゴリズムはクイックソートであり特に新たに作られたものではないことと、四角三角は基本情報技術者試験で覚えさせられる擬似コードの記号なので、プログラマーの方々であれば共通認識または既知の情報だと思い特に記載しなかったのですが、そうではないのでしょうか。

[arcxor]

これは興味深い観点ですね。

基本情報技術者試験（情報処理技術者試験の一部である）は日本の国家資格の一つであり、技術者試験としては広く知られたものではあります。しかし、基本情報技術者を受けているプログラマは一部なので知らない人は知らないですし、結局は疑似コードというのは独自言語です。何の脈絡もなく擬似コードを見せられては、その構文の意味するところを理解するのは通常は難しいと思います。記法の説明（あるいは何の疑似コードであるかの明示）なしでは通用しないと思った方が良いと思います。

クイックソートのアルゴリズムについては、例えばピボットの選び方などは様々な流儀があります。特定のピボットの選び方についてアルゴリズムがマスクされていて、そのアルゴリズムの内容を問われても答えるのは難しいのではないかと思います（だからこそエスパーして動作するプログラムを書く必要があった）。

こんなところでしょうか。

[Jorrvaskr_prg]

初心者として学んでいると、業界では普通・基本なので絶対覚えるようにと植え込まれている故の不躾でした。

arcxor様のエスパー力に脱帽です。
ありがとうございました。