sorting - クイックソートの実装

Question

#include<stdio.h>
#include<iostream.h>
#include<conio.h>

void quicks(int *arr,int x,int pivot,int lo,int hi);
void swap1(int *x,int *y);
int main()
{
int *arr = new int[7];
arr[0] = 23;
arr[1] = 3;
arr[2] = -23;
arr[3] = 45;
arr[4] = 12;
arr[5] = 76;
arr[6] = -65;
quicks(arr,7,0,1,6);
for(int i = 0;i<7;i++)
    std::cout << arr[i] <<"\t";
getch();
return 0;
 }
 void quicks(int *arr,int x,int pivot,int lo,int hi)
 {
int i = lo,j = hi;
if(pivot < x-1)
{
while(i <= hi)
{
    if(arr[i] <= arr[pivot])
        i++;
    else
        break;
}
while(j >= lo)
{
    if(arr[j] >= arr[pivot])
        j--;
    else    
        break;
}
if( i > j)
{
    swap1(&arr[j],&arr[pivot]);
    lo = pivot+1;
    hi = x - 1;
    quicks(arr,x,pivot,lo,hi);
}
else if(i == j)
{
    pivot = pivot + 1;
    lo = pivot+1;
    hi = x - 1;
    quicks(arr,x,pivot,lo,hi);
}
else if(i < j)
{
    swap1(&arr[j],&arr[i]);
    lo = i + 1;
    hi = j - 1;
    quicks(arr,x,pivot,lo,hi);
}
}
else
{
    printf("\nDONE\n");
}
}

void swap1(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}

こんにちは、私はクイックソートを実装するプログラムを書きました.しかし、プログラムは無限ループに入ります.Quicks関数では、iとjをインクリメントおよびデクリメントするためのwhileループが問題です.誰かがこれの何が問題なのか教えてもらえますか?クイックソートの実装。

Answer 1

入力とアルゴリズムを使用して簡単な予行演習を行うと、しばらくすると無限サイクルに陥ることに気付くでしょう。

からループを開始していますquicks(arr,7,0,1,6);。代わりに、low を「右端」の要素、つまり 0 に設定してみてください。これは、アルゴリズムが実際に欠陥があるように見え、high の位置がまったく変化せず、i がずっと high に移動しているため、問題を確実に解決するものではありません。非常に単純なタスクを複雑にしようとしています。

iからloに移動しpivotます。jからhiまでpivot。_ pivotが適切な場所にあることがわかったら、 1 つ前にpivot進みlo、プロセスを繰り返します。

この画像を見て、必要なアルゴリズムを理解してください。