Quick Sort

This is a discussion on Quick Sort within the C Programming forums, part of the General Programming Boards category; 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 ...

  1. #1
    Registered User
    Join Date
    Dec 2005
    Posts
    25

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

  2. #2
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    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()'

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by ramayana View Post
    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...
    Last edited by iMalc; 06-17-2007 at 02:15 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    ~viaxd() viaxd's Avatar
    Join Date
    Aug 2003
    Posts
    246
    :wq

  5. #5
    Registered User
    Join Date
    Dec 2005
    Posts
    25
    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 .

  6. #6
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    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()...)

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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?
    Last edited by Adak; 06-17-2007 at 04:43 AM.

  8. #8
    Registered User
    Join Date
    Dec 2005
    Posts
    25
    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

  9. #9
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,682
    Use the debugger to trace stuff especially recusion stack. What compiler are using?Let me guess are u working on turbo C compiler.

    ssharish2005

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recursive quick sort - stack overflow
    By Micko in forum C Programming
    Replies: 9
    Last Post: 01-01-2005, 05:51 PM
  2. Help On A Quick Sort Program
    By nick4 in forum C++ Programming
    Replies: 11
    Last Post: 12-06-2004, 10:51 AM
  3. Questions on basic Quick Sort
    By Weng in forum C++ Programming
    Replies: 4
    Last Post: 12-16-2003, 10:06 AM
  4. Quick Sort Help
    By NavyBlue in forum C Programming
    Replies: 1
    Last Post: 03-02-2003, 10:34 PM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21