1

クイックソートのメカニズムを理解しようとしていますが、今のところ理解できません。ウィキペディアによると、手順は次のとおりです。

1.リストからピボットと呼ばれる要素を選択します。

2.ピボットよりも小さい値を持つすべての要素がピボットの前に来るようにリストを並べ替え、ピボットよりも大きい値を持つすべての要素がピボットの後に来るようにします（等しい値はどちらの方向にも行くことができます）。この分割後、ピボットは最終的な位置になります。これをパーティション操作と呼びます。

3.上記の手順を、値が小さい要素のサブリストに再帰的に適用し、値が大きい要素のサブリストに個別に適用します。

そしてこれはコードです：

 int partition(int arr[], int left, int right)
    {
          int i = left, j = right;
          int tmp;
          int pivot = arr[(left + right) / 2];

          while (i <= j) {

                while (arr[i] < pivot)
                      i++;
                while (arr[j] > pivot)
                      j--;
                if (i <= j) {
                      tmp = arr[i];
                      arr[i] = arr[j];
                      arr[j] = tmp;
                      i++;
                      j--;
                }
          }
          return i;
    }
     void quickSort(int arr[], int left, int right) {
          int index = partition(arr, left, right);
          if (left < index - 1)
                quickSort(arr, left, index - 1);
          if (index < right)
                quickSort(arr, index, right);
    }

1つを除いて、すべてがどういうわけか私には明らかです。なぜパーティション関数が返さiれ、戻らないのjですか？

4

1 に答える 1

0

このプログラム（および出力）はここにあります。見てください、

#include <iostream>
using namespace std;

const int INPUT_SIZE = 10;

// A simple print function
void print(int *input)
{
    for ( int i = 0; i < INPUT_SIZE; i++ )
        cout << input[i] << " ";
    cout << endl;
}

// The partition function
int partition(int* input, int p, int r)
{
    int pivot = input[r];

    while ( p < r )
    {
        while ( input[p] < pivot )
            p++;

        while ( input[r] > pivot )
            r--;

        if ( input[p] == input[r] )
            p++;
        else if ( p < r )
        {
            int tmp = input[p];
            input[p] = input[r];
            input[r] = tmp;
        }
    }

    return r;
}

// The quicksort recursive function
void quicksort(int* input, int p, int r)
{
    if ( p < r )
    {
        int j = partition(input, p, r);        
        quicksort(input, p, j-1);
        quicksort(input, j+1, r);
    }
}

int main()
{
    int input[INPUT_SIZE] = {500, 700, 800, 100, 300, 200, 900, 400, 1000, 600};
    cout << "Input: ";
    print(input);
    quicksort(input, 0, 9);
    cout << "Output: ";
    print(input);
    return 0;
}

OUTPUT:-
Input: 500 700 800 100 300 200 900 400 1000 600
Output: 100 200 300 400 500 600 700 800 900 1000
于 2013-04-11T05:02:15.283 に答える