calgorithmgridview-sorting

quicksort program not working?


This is supposed to be a an implementation of the quicksort algorithm. But when I run it it keeps going forever without displaying anything. I have tried to find the problem but am too tired now. Please help.

#include <stdio.h>

void quicksort(int arr[], int pivotIndex,int right);
int partition(int a[],int left,int right);

int main()
{
   int arr[5] = {5, 4,2, 3, 6};    
   int left = 0;
   int right = 4;

   quicksort(arr, left, right);

   for (int i = 0; i < 5; i++)
   {
       printf("%d ", arr[i]);
   }
   return 0;    
}

void quicksort(int arr[], int left,int right)
{
    if (left < right)
    {
        int pivotNewIndex = partition(arr, left, right);
        quicksort(arr, left, pivotNewIndex - 1);
        quicksort(arr, pivotNewIndex + 1, right);
    }
}

int partition(int a[],int left,int right)
{

    int i = left;
    int j = right;
    int pivotIndex = left;
    int temp;

    while (i < j)
    {
        while (a[pivotIndex] <=a[j])
        {
            j--;
        }
        if (a[pivotIndex] > a[j])
        {
            temp = a[pivotIndex];
            a[pivotIndex] = a[j];
            a[j] = temp;
            pivotIndex = j;
        }

        while (a[pivotIndex] <= a[j])
        {
            i++;
        }
        if (a[pivotIndex] < a[j])
        {
            temp = a[pivotIndex];
            a[pivotIndex] = a[j];
            a[j] = temp;
            pivotIndex = i;
        }        
    }
    return pivotIndex;
}

Solution

  • Probably (i don't test)

    should be

    while (i<j && a[pivotIndex] <=a[j])
    {
        j--;
    }
    if (a[pivotIndex] > a[j])
    {
        temp = a[pivotIndex];
        a[pivotIndex] = a[j];
        a[j] = temp;
        pivotIndex = j;
    }
    
    while (i<j && a[pivotIndex] >= a[i])
    {
        i++;
    }
    if (a[pivotIndex] < a[i])
    {
        temp = a[pivotIndex];
        a[pivotIndex] = a[i];
        a[i] = temp;
        pivotIndex = i;
    }