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

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--; 
    }