Ошибка реализации быстрой сортировки

Я пытался реализовать быструю сортировку. Но управление, кажется, никогда не выходит из функции быстрой сортировки. Любая помощь приветствуется.

Несколько указателей:

  1. Я использую первый элемент в качестве оси. Я знаю, что существуют гораздо лучшие и эффективные методы для выбора опоры, но речь не об этом.

2. Переменная ‘k’ в функции секционирования является элементом pivot.

Насколько я знаю, проблема в функции раздела, так как я пытался отлаживать ее несколько раз.

Кроме того, это не домашнее задание. Я пытался реализовать алгоритм после того, как выучил его сам.

#include<iostream>
using namespace std;

void swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}

void readarray( int a[],int n)
{
cout<<"Enter elements for the array\n";
for(int i=0;i<n;i++)
cin>>a[i];
}

void printarray(int a[],int n)
{
cout<<"Elements are as follows\n";
for(int i=0;i<n;i++)
cout<<a[i]<<" ";

cout<<endl;
}int partition(int low,int high,int a[])
{
int i,j,k;
i=low;
j=high;
k=low;

while(i<=j)
{
while(a[i]<a[k])
i++;

while(a[j]>=a[k])
j--;if(i<=j)
{
swap(a[i],a[j]);
i++;
j--;
}
}

if(i>j)
swap(a[k],a[j]);

return j;
}

void quicksort(int low,int high,int a[])
{
int k;
if(low<high)
{
k=partition(low,high,a);
quicksort(low,k-1,a);
quicksort(k+1,high,a);
}
}

int main()
{
int a[20];
int n;
cout<<"Enter the size of the array\n";
cin>>n;
readarray(a,n);
cout<<"Before sorting\n";
printarray(a,n);

quicksort(0,n,a);

cout<<"After sorting contents are\n";

printarray(a,n);

return 0;
}

В основной функции я попытался использовать как быструю сортировку (0, n, a), так и быструю сортировку (0, n-1, a). Ни один не работал.

0

Решение

Существует проблема с вашей процедурой раздела, см. Комментарии:

int partition( int low, int high,int a[]) {
int i, j, k;
i = low;
j = high;
k = low;

while ( i < j )
{
while( a[i] <= a[k] ) // Move i while item < kth element
i++;
while( a[j] > a[k] ) // Move j while item > kth element
j--;
if ( i < j )
swap(&a[i],&a[j]); //Pass address of elements
}

swap(&a[low],&a[j]); // j is final position for the kth element (viz.the pivot )

return j;
}

Вызовите процедуру быстрой сортировки, используя:

quicksort(0,n-1,a);

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]