Реализация быстрой сортировки, не могу найти ошибку

Question

Я хочу реализовать этот алгоритм быстрой сортировки с какой-то другой стратегией разворота, но в нем есть логическая ошибка. Не могли бы вы помочь мне найти его?

#include <iostream.h>
#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
int arr[100],i,pivot,left,right,sum=0,a,n=10;

int partition();
void quickSort(int* ,int ,int );



void main()
{
    clrscr();
    int i,n=20;
    for(i=0;i<=n;i++)
    {
      arr[i]=rand()%100;
    }

    for(i=0;i<=n;i++)
    {
      cout<<"\t"<<arr[i];
    }

    quickSort(arr,n,i);

    for(i=1;i<n;i++)
    {
      cout<<"\n"<<arr[i];
    }

    getch();
}

int partition()
{
  // int i;
  // int sum=0;
  // int pivot;
  // stable_sort(arr,arr+3);
    for(i=0;i<5;i++)
    {
       cout<<"\nsorted k elements\t"<<arr[i];
       // sum=sum+arr[i];
    }
    // cout<<sum;
    //cout<<"median is "<<sum/3;
    pivot=arr[(i)/2];
    cout<<"pivotis value at position "<<pivot ;
    return pivot;
}

void quickSort(int arr[],int left,int right) 
{
      partition();
      right=n,left=0;
      int i = right, j =left;

      int tmp;
      int p=pivot;
      cout<<" m array of p"<<p;
      while (i <= j) {
        while (arr[i] < p)
          i++;
        while (arr[j] > p)
          j--;
        if (i <= j) {
          tmp = arr[i];
          arr[i] = arr[j];
          arr[j] = tmp;
          i++;
          j--;
        }
    }
    if (left < j)
    {
       quickSort(arr, left, j);
    }
    if (i < right)
    {
       quickSort(arr, i, right);
    }
}

Answer 1

Ваше сводное значение всегда будет значением arr[(i)/2], равным arr[2], независимо от того, какую часть массива вы сортируете в данный момент. Передайте значения left и right в partition, чтобы он знал, какие значения следует учитывать для текущего вызова, в quickSort.

Кроме того, значения left и right, которые вы передаете для начального вызова quickSort, соответственно равны 20 и 21, что, безусловно, не то, что вы предполагали. У вас есть массив длины 100, и вы инициализировали первые 21 элемент, поэтому вы, вероятно, хотите передать 0 и 21 для этих параметров.

Но первое, что вам, вероятно, следует сделать, если вы хотите проверить быструю сортировку с другой сводной стратегией, это заставить ее работать сначала с типичным Поворотная стратегия, подобная той, что продемонстрирована в вашем учебнике. Начните с работающей реализации, и только затем , если вы начнете экспериментировать с вариациями. Вы должны быть в состоянии найти работающую реализацию в своем учебнике или в своих заметках.

Answer 2

Я не нашел места, где вы сравниваете значения из массива.

Полагаю, вам следует проверить это место:

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

Вероятно, это должно быть:

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