Ошибка реализации Quicksort

Question

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

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

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

2. Переменная 'k' в функции разбиения является элементом поворота.

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

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

#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, п, а) и быстрой сортировки (0, п-1, а). Ничего не сработало.

Answer 1

Существует проблема с вашей обычной раздела, см комментарии:

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