2

これは、クイック ソート アルゴリズムを使用して配列をソートしようとするプログラムです。出力が正しくないことを除いて、すべて問題ないようです。

(n=5、次に n=10 でプログラムを試してみてください。前者では正しく動作しますが、後者では正しく動作しません。)

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

int partition(int arr[], int left, int right)   {
    int i = left, j = right;
    int temp;

    //Choosing the middle element as the pivot
    //int pivot=arr[left];
    int pivot = arr[(left+right)/2];

    while (i <= j) {
        while (arr[i] < pivot) {i++;}
        while (arr[j] > pivot) {j--;}

        if (i <= j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }

    return i;
}

void quick_sort(int arr[], int p, int r)   {
    if (p<r)   {
       int q=partition(arr, p, r);
       quick_sort(arr, p, q-1);
       quick_sort(arr, q+1, r);
    }
}

int main()  {
    int values[100], n, i;

    //clrscr();

    printf("Enter no. of elements ");
    scanf("%d", &n);

    if (n>100) {
        printf("Invalid input. Exiting now");
        //getch();
        return 0;
    }

    for (i=0; i<100; i++) values[i]=0;

    printf("Enter the numbers\n");
    for (i=0; i<n; i++) scanf("%d", &values[i]);

    printf("The numbers you entered are\n");
    for (i=0; i<n; i++) printf("%d ", values[i]);

    printf("\n");

    quick_sort(values, 0, n-1);

    printf("Numbers after sorting are\n");
    printf("(The output might not be the expected one (Be careful).\n");
    for (i=0; i<n; i++) printf("%d ", values[i]);

    //std::cin.get();

    return 0;
}
4

2 に答える 2

2

2 つの問題があります。まず、比較i <= jが間違っています。の場合i == j、要素をそれ自体と交換しないでください。i < jこれは、両方の場所でに変更する必要があります。次に、スワップ後に配列インデックスiと配列インデックスを移動しないでください。jそれが最後のスワップである場合、これiは実際のピボットを超えてプッシュされ、エラーが発生します。

int partition(int arr[], int left, int right)   {
    int i = left, j = right;
    int temp;

    //Choosing the middle element as the pivot
    //int pivot=arr[left];
    int pivot = arr[(left+right)/2];

    while (i < j) {
        while (arr[i] < pivot) {i++;}
        while (arr[j] > pivot) {j--;}

        if (i < j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    return i;
}
于 2013-03-10T12:50:19.787 に答える
-1

algorithm.hの std ソートを使用することをお勧めし ます。

http://www.cplusplus.com/reference/algorithm/sort/

于 2013-03-10T15:18:49.267 に答える