2

私はプログラミングにかなり慣れておらず、しばらくの間ソートアルゴリズムを学んでいます。以下のCでクイックソートを実装しました。ピボットを選択するために3つのパーティションの中央値を使用します。コードの問題は、実行するたびに、並べ替えられた配列の中央値/中間値であるはずの要素が並べ替えられていないことです。つまり、別の場所で発生します。コードは次のとおりです。

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

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

int median3(int a[], int left, int right)//Uses median of three partitioning technique
{
    int center = (left + right)/2;
    if (a[center] < a[left]) 
        swap(&a[left],&a[center]);
    if (a[right] < a[left])
        swap(&a[left],&a[right]);
    if (a[right]< a[center])
        swap(&a[center],&a[right]);

    swap(&a[center], &a[right - 1]);//since the largest is already in the right.
    return a[right - 1];
}

void quicksort(int a[], int left, int right)
{
  if (left < right) {
    int pivot = median3(a,left,right);
    int i = left;
    int j = right - 1;
    for ( ; ;) {
        while(a[++i]<pivot) {} 
        while(pivot<a[--j]) {} 
        if ( i < j)
            swap(&a[i],&a[j]);
        else
            break ;
    }
    swap(&a[i],& a[right -1]);
    quicksort(a,left,i-1);
    quicksort(a,i+1,right);
  }
    return ;
}

int main(int argc, char* argv[])
{
    int i;
    int a[] = {8,1,4,9,6,3,5,2,7,0};
    quicksort(a,0,9);
    for ( i = 0 ; i < 10 ; i++)
        printf("%d\n",a[i]);
    return 0;
}
4

1 に答える 1

1

エッジケースに注意してください。ここでleft == right - 1：

void quicksort(int a[], int left, int right)
{
  if (left < right) {
    int pivot = median3(a,left,right);
    if (left == right - 1) return;  // only two elements, already sorted by median3()
    int i = left;
    int j = right - 1;

http://ideone.com/X5Ydx

于 2012-05-22T09:33:10.467 に答える