quick sort program

This is a discussion on quick sort program within the C Programming forums, part of the General Programming Boards category; hey friends!!!! Quicksort algorithm is simple but its implementation is really confusing. I have tried to write a program for ...

  1. #1
    Registered User
    Join Date
    Jan 2010
    Location
    on some of the worst place on earth
    Posts
    105

    quick sort program

    hey friends!!!! Quicksort algorithm is simple but its implementation is really confusing. I have tried to write a program for quick sort with some help of textbook but the program has some logical error and am not able to find it out.
    Can you help it out.The code is:
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    void printlist(int *x,int n);
    void quicksort(int *x,int lower,int upper);
    void swap(int *a,int *b);
    int main()
    {
    	int *arr,n,i,resp;
    	printf("\nHOW MANY ELEMENTS?\t");
    	scanf("%d",&n);
    	arr=(int*)malloc(n*sizeof(int));
    	printf("\n\nWOULD YOU LIKE TO GENERATE NUMBERS RANDOMLY OR YOURSELF?\n");
    	printf("PRESS 1 FOR RANDOM NUMBERS\n      2	FOR INPUTTING NUMBERS\n");
    	gen:
    	scanf("%d",&resp);
    	switch(resp)
    	{
    		case 1:
    			printf("\nOK THEN. NOW GENERATING RANDOM NUMBERS.....\n");
    			for(i=0;i<n;i++)
    			{
    				arr[i]=rand()/100;
    				//printf("\nELEMENT NO. %d:\t%d ",i+1,arr[i]);
    			}
    			break;
    		case 2:
    			printf("\nPLEASE ENTER THE ELEMENTS:\n");
    			for(i=0;i<n;i++)
    			{
    				printf("\nELEMENT NO. %d: ",i+1);
    				scanf("%d",&arr[i]);
    			}
    			break;
    		default:
    			printf("\nERROR-UNEXPECTED INPUT");
    			goto gen;
    			break;
    	}
    	printf("\n\nTHE LIST BEFORE SORTING IS(UNSORTED LIST):\n");
    	printlist(arr,n);
    	quicksort(arr,0,n-1);
    	printf("\n\nTHE LIST AFTER SORTING IS(SORTED LIST):\n");
    	printlist(arr,n);
    	return 0;
    }
    
    void printlist(int *x,int n)
    {
    	int i;
    	for(i=0;i<n;i++)
    	{
    		printf("%d  ",x[i]);
    	}
    }
    void quicksort(int *x,int lower,int upper)
    {
    	int lo,hi,i,pivot;
    	pivot=x[lower];
    	lo=lower+1;
    	hi=upper;
    	while(lo<=hi)
    	{
    		while(x[lo]<pivot)
    			lo++;
    		while(x[hi]>pivot)
    			hi--;
    		if(lo<hi)
    			swap(&x[lo],&x[hi]);
    	}
    	swap(&x[lower],&x[hi]);
    	quicksort(x,lower,hi-1);
    	quicksort(x,hi+1,upper);
    	return;
    }
    void swap(int *a,int *b)
    {
    	int temp;
    	temp=*a;
    	*a=*b;
    	*b=temp;
    }
    Can u find out any fault in the code???

  2. #2
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Not sure if you're qsort'ng the array index or the contents?
    Code:
    if(lo<hi)
             swap(&x[lo],&x[hi]);

  3. #3
    Registered User
    Join Date
    Jan 2010
    Location
    on some of the worst place on earth
    Posts
    105
    Quote Originally Posted by itCbitC View Post
    Not sure if you're qsort'ng the array index or the contents?
    Code:
    if(lo<hi)
             swap(&x[lo],&x[hi]);
    But that doesn't seems to be the part of the problem. I tried it out but no effect....

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by rakeshkool27 View Post
    But that doesn't seems to be the part of the problem. I tried it out but no effect....
    What did you change it to?

  5. #5
    Registered User
    Join Date
    Jan 2010
    Location
    on some of the worst place on earth
    Posts
    105
    Quote Originally Posted by tabstop View Post
    What did you change it to?
    I changed to x[lo]<x[hi].

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by rakeshkool27 View Post
    I changed to x[lo]<x[hi].
    What you had the first time is correct -- lo points to the first high element in the low half, and hi points to the last low element in the high half, and as long as lo hasn't passed hi (i.e., if lo < hi) you want to swap.

    Also at some point you need to do a "hey I'm out of data" check -- running your code led to a segfault when the recursive call reached lower = 0, upper = -2389.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Change the hi in red, to lo. I'd also add the //added statement.

    I put a big question mark on that last call to swap(), before the recursive calls, because you didn't actually move the pivot, so you don't need to replace it.

    Also, when you call swap, I would use just the same parameters you are using for quicksort() - the name of the array(which is an address), and two INDECES. NOT addresses, or values, but indeces!


    Code:
    //Your code:
    void quicksort(int *x,int lower,int upper)
    {
    	int lo,hi,i,pivot;
           if(lower==upper)  //Added
             return;
    	pivot=x[lower];
    	lo=lower+1;
    	hi=upper;
    	while(lo<=hi)
    	{
    		while(x[lo]<pivot)
    			lo++;
    		while(x[hi]>pivot)
    			hi--;
    		if(lo<hi)
    			swap(x, lo,hi);
    	}
    	//?????   =====>>>  swap(x, lower, hi);  //Why?
    	if(lower < hi) quicksort(x,lower,hi-1);  
    	if(lo < upper) quicksort(x,hi+1,upper);  
    	return;
    }
    
    //88888888888888888888
    //Quicksort 
    void quicksort(int A[], int lo, int hi) {
      int i, j, pivot, temp;
    
      if(lo == hi) return; 
      i=lo; 
      j=hi;
      pivot= A[(lo+hi)/2]; 
    
      /* Split the array into two parts */
      do {    
        while (A[i] < pivot) i++; 
        while (A[j] > pivot) j--;
        if (i<=j) {
          swap(A, i, j);   //this line works fine.
    
          /* 
            temp= A[i];
            A[i]= A[j];
            A[j]=temp;
             ^^^^^ This is what your swap function should be doing 
          */
          i++;
          j--;
        }
      } while (i<=j);
        
      if (lo < j) quicksort(A, lo, j);
      if (i < hi) quicksort(A, i, hi);
    }
    The idea behind Quicksort is simple, but it is "brittle" - very easy to break. I applaud your version of it, however. I've seen some real doozie's lately - barely recognize them as Quicksort, at all.
    Last edited by Adak; 05-21-2010 at 06:00 AM.

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    It can help if you break it up into separate steps:
    • Checking for an array that is too small to need to do anything with
    • Picking a pivot point
    • Partitioning according to the pivot (which has swapping as a sub-task)
    • Performing the recursive calls

    Each one of these points can be written on its own and tested in isloation. You can get each bit correct and then start putting them together.
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 09-16-2009, 06:00 AM
  2. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  3. Using variables in system()
    By Afro in forum C Programming
    Replies: 8
    Last Post: 07-03-2007, 12:27 PM
  4. Quick sort
    By Saiyanman in forum C Programming
    Replies: 4
    Last Post: 07-30-2002, 10:16 PM
  5. quick termination of program
    By jobolikescake in forum C Programming
    Replies: 7
    Last Post: 01-20-2002, 09:59 PM

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