-3

In quick sort,the execution gets stuck after 2, 9 Can someone please tell what is the issue here In quick sort,the execution gets stuck after 2, 9 Can someone please tell what is the issue here In quick sort,the execution gets stuck after 2, 9 Can someone please tell what is the issue here In quick sort,the execution gets stuck after 2, 9 Can someone please tell what is the issue here

#include <stdio.h>
#include <stdlib.h>

int partition (int a[],int start,int end)
{
int i=start;
int j=end;
int temp;
int pivot = a[end];
  while( i< j)
  {
    if(a[i] < pivot && a[j] > pivot)
    {
       i++;
       j--;
       continue;
    }
    else if (a[j] < pivot && a[i] > pivot)
    {
      temp = a[j];
      a[j] = a[i];
      a[i] = temp;
      i++;
      j--;
      continue;
    }
    else if(a[j] < pivot)
    {
      i++;
      continue;
    }
    if(a[i] > pivot )
    {
      j--;
      continue;
    }

  }
  a[end] = a[i];
  a[i] = pivot;
  return i;

}
void quicksort(int a[], int s,int e)
{
int k;
printf("entered quicksort- s and e are %d %d\n ",s ,e );
if(s<e){
k = partition(a,s,e);
quicksort(a,s,k-1);
quicksort(a,k+1,e);}
}

int main()
{
int n = 10,i;
int a[10] = {45,78,23,90,80,10,35,37,54,22};
quicksort(a,0,9);
for (i=0; i< n;i++)
{
printf("array is %d ",a[i]);

}
return 0;
}
``````

output is
 entered quicksort- s and e are 0 9
 entered quicksort- s and e are 0 0
 entered quicksort- s and e are 2 9

the execution gets stuck here
GH P
  • 37
  • 1
  • 5
  • 2
    *Debug* your code. It is literally what debuggers are made for (hence the name). If you do so you will find it is possible for all *four* of your preconditions in your partition algorithm to be *false*, and in so being, *no* adjustment to `i` or `j` takes place. Therefore, they do not change, therefore, `i < j` remains true, the same conditions are evaluated (again) to false (again), and the loop becomes infinite. This appears to be an attempt at Hoare's partition algorithm. I suggest you review it in detail. – WhozCraig May 01 '22 at 17:55
  • 1
    Have you tried running your code line by line in a debugger while monitoring the values of all variables, in order to determine at which point your program stops behaving as intended? If you did not try this, then you may want to read this: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/12149471) You may also want to read this: [How to debug small programs?](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) – Andreas Wenzel May 01 '22 at 17:57
  • 1
    For one thing, ‘j’ needs to start at ‘end-1’. – 500 - Internal Server Error May 01 '22 at 18:47

1 Answers1

0

The problem seems to be with the first if statement in partition, where you increment i/decrement j together rather than on their own.

I changed your partition function to something much simpler and it seems to work

int                                                                                                                           
partition(int a[], int start, int end)                                                                                        
{                                                                                                                             
    int pivot = a[(start + end) / 2];                                                                                         
                                                                                                                              
    int i = start;                                                                                                            
    int j = end;                                                                                                              
                                                                                                                              
    while(1)                                                                                                                  
    {                                                                                                                         
        while(a[i] < pivot) i += 1;                                                                                           
        while(a[j] > pivot) j -= 1;                                                                                           
                                                                                                                              
        if(i >= j) return j;                                                                                                  
                                                                                                                              
        int tmp = a[i];                                                                                                       
        a[i] = a[j];                                                                                                          
        a[j] = tmp;                                                                                                           
    }                                                                                                                         
}

For reference: https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

Michael Shaw
  • 71
  • 4