Правильное разбиение массива QuickSort

Я новичок в C, и я пытался закодировать программу Quicksort, которая может принимать случайно сгенерированный массив действительных чисел и его размер в качестве аргумента, а затем сортирует элементы в порядке возрастания. Не могу сообразить, что прописать в поле размера массива при первом рекурсивном вызове функции QuickSort, которая предназначена для представления подмассива A[0...q-1]. Насколько я могу судить, остальная часть кода в порядке, потому что при подключении к программе-драйверу, которая генерирует случайные числа, программа возвращает элементы, хотя и в неправильном порядке. Я ценю любую помощь/предложения.

int Partition(float *,int);

int QuickSort(float *A,int n)
{
  int q;

  if(n>1){
    q = Partition(A,n);
    QuickSort(&A[],q); //Trying to figure out what to put in here.
    QuickSort(&A[q+1],(n-1)-q); //This recursion sends the subarray A[q+1...n-1] to QuickSort, I think it works fine.
  }
}

int Partition(float *A,int n){
  int i,j;
  float x;

  x = A[n-1];
  i=0;
  for(j=0;j<=n-2;j++){
    if(A[j] <= x){
      A[i]=A[j];
      i = i+1;
    }
  }
  A[i]=A[n-1];
  return i;
}

c arrays recursion quicksort sub-array
person Stavo    schedule 23.10.2016    source источник
comment
Используйте 0 в качестве отсутствующего индекса.   -  person Jonathan Leffler    schedule 23.10.2016
comment
Хм, это ближе, подмассивы отсортированы правильно, но весь массив не отсортирован. Таким образом, это выглядит так: A[0] = 0,197551 A[1] = 0,277775 A[2] = 0,277775 A[3] = 0,277775 A[4] = 0,553970 A[5] = 0,197551 A[6] = 0,277775 A[7]. ] = 0,277775 А[8] = 0,553970 А[9] = 0,553970   -  person Stavo    schedule 23.10.2016
comment
Если вы добавите базовую функцию печати массива, вы сможете вызывать ее в ключевых местах, например, в Partition() при входе и при выходе. И если вы сделаете это, вы обнаружите, что ваш код разбиения полностью портит ваш массив — содержимое до и после не совпадает. Например, я получил P1 (5): [0] = 0.197551 [1] = 0.277775 [2] = 0.277775 [3] = 0.277775 [4] = 0.197551 —— P2 (5): [0] = 0.197551 [1] = 0.197551 [2] = 0.277775 [3] = 0.277775 [4] = 0.197551, где значение нижнего индекса [1] изменилось с 0,277775 до 0,197551. Вам нужно менять местами элементы, а не просто перемещать их.   -  person Jonathan Leffler    schedule 24.10.2016

Ответы (1)


arrow_upward
1
arrow_downward

Ваша проблема только в том, что вы, кажется, путаете:

A[i]=something;

с заменой A[i] и something. Добавьте вспомогательный tmp или напишите функцию подкачки:

#include<stdio.h>
int Partition(float *,int);

void QuickSort(float *A,int n) {
  int q;

  if(n>1){
    q = Partition(A,n);
    QuickSort(A,q); //Trying to figure out what to put in here.
    QuickSort(A+q+1,(n-q-1)); //This recursion sends the subarray A[q+1...n-1] to QuickSort, I think it works fine.
  }
}

int Partition(float *A,int n){
  int i,j;
  float x;
  float tmp;
  x = A[n-1];
  i=0;
  for(j=0;j<=n-2;j++){
    if(A[j] <= x){
      tmp = A[i];
      A[i]=A[j];
      A[j]=tmp;
      i = i+1;
    }
  }
  tmp = A[i];
  A[i]=A[n-1];
  A[n-1]=tmp;
  return i;
}

int main() {
    float A[] = {3, 4, -5, 10, 21, -9, -1, 7, 8, 10};
    QuickSort(A,10);
    for(int i = 0; i < 10; i ++)
        printf("%f ",A[i]);
    return 0;
}
person kabanus    schedule 23.10.2016