Quick Sort

This program is supposed to impelement quicksort but it is not working

Code:

---


include<stdio.h>
#include<conio.h>
#include<process.h>
void quicksort(int a[] ,int low,int high);
int partition(int a[] , int low,int high);
//quick sort
void main()
 {
 int a[10], n ,i;
 clrscr();
 printf("enter the total no. of elements \n");
 scanf("%d",&n);
 printf("enter the elements of the array \n");
  for(i=0;i<n;i++){
  scanf("%d",&a[i]);}
  quicksort(a,0,n-1);
  printf("sorted array is \n");
  for(i=0;i<n;i++)
    printf("%d",a[i]);
    getch();
  }
 void quicksort(int a[] ,int low,int high)
  {
  int mid ;
    if (low<high)
    {
    mid=partition(a,low,high);
    quicksort(a,low,mid-1);// partioned elemnt in its final position at mid
    quicksort(a,mid+1,high);
      }
  }
  partition(int a[], int low,int high)
  {
  int temp,i,pivot,j;
  i=low;
  j=high;
  pivot=a[i];
    while (i<=j)
    {
      while(a[i]<=pivot && i<=high){i=i+1;}
      while(a[j]>pivot){j=j-1;}
      if(i<j){
        temp=a[i];
        a[j]=a[i];
        a[j]=temp;
        }
      temp=pivot;
      pivot=a[j];
      a[j]=temp;
      }
      return j;
}

---

Apparently neither is your spacebar, learn how to indent. Your going to have to be more specific, try and debug it (either with a debugger or put printf()'s everywhere).

Also consult the FAQ, especially about your use of 'void main()'

Quote:

---

Originally Posted by ramayana

This program is supposed to impelement quicksort but it is not working

---

Wow really? Why not?

Well someone had to ask a question on this thread... That's what they're for...

http://www.google.com/search?hl=en&q....c&btnG=Search

Sorry for the indentation this is the best I could manage , about the main() this is the way I do and I don't think it comes in the way of the program . I have tried tracing the program but the endless recursion makes it very difficult .
The quicksort program given works perfectly and apart from different variable names I couldnt find any differences .

I hope you know that getch() isn't portable, and it's best to avoid conio.h :) perhaps use something portable, see the FAQ (ie getchar()...)

The selection of the pivot should allow it to be chosen from somewhere near the middle of the array or sub array, but here it's just being set to a[low] (a[i]), and then there's this:

Code:

---

pivot=a[i];
    while (i<=j)
    {
      while(a[i]<=pivot && i<=high){i=i+1;}
      while(a[j]>pivot){j=j-1;}

---

Which would bring the low upward, except the pivot is already just been assigned to the lowest array subscript's value. So all it can do is bring the high value down. Later, the pivot is being assigned to the a[j].

Also, in proportional fonts (normal, in Windows and Linux, both), i and j look a great deal alike. Both have a mostly single vertical bar, with a dot above it. I don't see an obvious error with that, but do re-check it.

Quicksort is a very "brittle" algorithm; easy to muck up, badly. Where did you get this version, anyway?

Code:

---

temp=pivot;
      pivot=a[j];
      a[j]=temp;

---

if changed to

Code:

---


temp=a[low];
a[low]=a[j];
a[j]=temp;

---

The program works fine . And I still don't know why ..Tracing the program becomes all most impossible . Could someone tell me how , when many recursions are being made one can effectively keep track of what is going on?.

The quicksort has been implemented by me , after I'd learned( or thought I'd learned) how the algorithm works from a algorithm text book

Use the debugger to trace stuff especially recusion stack. What compiler are using?Let me guess are u working on turbo C compiler.

ssharish2005

It's one of the great algorithms around, imo. Read up on it at Wikipedia, and visit one of the several sights that show it slowed down, and on screen. Great stuff!