0

クイックソートに問題があります。一部の値では機能しますが、他の値では機能しません。たとえば、最初の値が最後の値よりも小さい場合、機能しません。何が悪いのかわかりません。これはコードです：

#include <stdio.h>
#include <time.h>

#define lenght_max 1000000
int x;
int tablica[lenght_max];
int q;

int Partition(left, right) {

    int tmp;
    int i;
    int j;

    i = -1;
    j = 0;

    x = tablica[right];
    i = left - 1;

    for(j = left; j < right; j++){
      if(tablica[j] <= x) {
        i++;
        tmp = tablica[i];
        tablica[i] = tablica[j];
        tablica[j] = tmp;
      }
    }

    return i + 1;
}

void Quicksort(left, right) {    
    if(left < right){ 
      q = Partition(left, right);
      Quicksort(left , q - 1);
      Quicksort(q + 1, right);
    }
}

int main(void) {

  int i;
  int temporary;
  int left;
  int right;

  printf("Witaj uzytkowniku. To jest program preferujacy sortowanie szybkie - quicksort.\n");
  printf("Podaj, ile liczb chcialbys posortowac: ");
  scanf("%i", &temporary);

  printf("Podaj liczby do sortowania: \n");

  for(i = 0; i < temporary; i++)
    scanf("%d", &tablica[i]);

    left = 0;
    right = temporary - 1;
    x = temporary / 2;

  Quicksort(left, right);

  printf("\nPROCES:\n");

  for(i = 0; i < temporary; i++)
    printf("%d\n", tablica[i]);

  return 0;
}
4

1 に答える 1

1

私が問題を見落としていなければ、 の最後のピボットよりも大きい最初の要素でピボットを交換するのを忘れていたようですPartition。修正は次のように簡単に追加できます。

    tmp            = tablica[i+1];
    tablica[i+1]   = tablica[right];
    tablica[right] = tmp;

return i + 1;内のステートメントの前Partition。

于 2012-10-28T19:14:04.787 に答える