Help with Quicksort

This is a discussion on Help with Quicksort within the C Programming forums, part of the General Programming Boards category; I've been having a lot of trouble with this lately, and I was hoping someone could give me a clue ...

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    3

    Help with Quicksort

    I've been having a lot of trouble with this lately, and I was hoping someone could give me a clue as to what to do. Mostly because the smallest in the array is displayed last, rather than first.

    Code:
    #include <stdio.h>
    #include "simpio.h"
    #define size 10
    void GetArray();
    void quicksort (int array[size], int arraybegin, int end);
    int rotate (int array[size], int arraybegin, int end);
    void displayarray (int array [size]);
    void swap (int array [size], int first, int second);
    
    main()
    {
    	printf("What is your array? Enter 10 numbers please.\n");
    	GetArray();
    }
    
    void GetArray()
    {
    int array[size];
    int i;
    for (i=0; i<size; i++)
    {
    	array[i]=GetInteger();
    }
    quicksort(array, 0, size-1);
    displayarray(array);
    }
    
    
    void quicksort(int array[], int arraybegin, int end)
    {
    	int count;
    	if (arraybegin<end)
    	{
    		count=rotate(array, arraybegin, end);
    		quicksort(array, arraybegin, count-1);
    		quicksort(array, count+1, end);
    	}
    }
    
    int rotate(int array[size], int arraybegin, int end)
    {
        int piv, poscount, negcount, j;
    	j=0;
    	piv=array[arraybegin];
    	poscount=arraybegin;
    	negcount=end;
    	j=size;
    	while(poscount<=negcount)
    	{
    		for(poscount=arraybegin;array[poscount]<=piv&&poscount<=size;poscount++);
    		for(negcount=end;array[negcount]>piv;negcount--);
    		
    	}
    	swap(array, poscount, negcount);
    	return (negcount);
    }
    
    void swap (int array [size], int high, int low)
    {
    	int change;
    	change=array[high];
    	array[high]=array[low];
    	array[low]=change;	
    }
    
    
    void displayarray(int array [size])
    {
    	int i;
    	printf("The sorted array is:");
    	for(i=0;i<size;i++)
    	{
    		printf("&#37;d, ",array[i]);
    	}}
    Last edited by Fect; 11-28-2007 at 09:32 PM.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,264
    'rotate' is not a good name for that function. 'Partition' would be a better choice.

    Do you mean to be saying that the only problem is that you want the data sorted in the reverse order to what it is now?
    No wait, from looking at it I can tell that it definitely doesn't sort properly yet. You need to perform a swap inside the while loop. Can't quicksort without that.
    It would help if you gave a clearer description of the problem.

    Those for-loops are horribly unreadable. I mean sure I can understand them, but... YUCK!
    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"

  3. #3
    Registered User
    Join Date
    Nov 2007
    Posts
    3
    The for loops function the same as while loops that do the same thing.

    However, even with the swap function inside the main while loop, I input an array like [0,2,1,3,4,5,6,7,8,9] and I get an output of [2,1,3,4,5,6,7,8,9,0].

    I know it has to do with the rotate function (partition), but I'm stumped.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,264
    Quote Originally Posted by Fect View Post
    The for loops function the same as while loops that do the same thing.

    However, even with the swap function inside the main while loop, I input an array like [0,2,1,3,4,5,6,7,8,9] and I get an output of [2,1,3,4,5,6,7,8,9,0].

    I know it has to do with the rotate function (partition), but I'm stumped.
    I'm fully aware that every type of loop construct can be rewritten using a different loop construct. I understand them, but your code is just senseless obfuscation. At least put some spaces in there.

    I know the problem is with your 'rotate' function. It is doing the job of a function normally called 'partition'. However it is impossible for it to be doing what it needs to do when it only ever performs a single swap. There has to be a swap in a loop somewhere because it needs to perform up to n/2 swaps for a call with n items.
    That's the 'clue' you've been asking for. Now you need to go back to whatever description of the algorithm you have, and identify what you are missing and how to add it to what you have so far.
    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"

  5. #5
    Registered User
    Join Date
    Nov 2007
    Posts
    3
    Thank you.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Scalability problems with Quicksort
    By hbejkosa in forum C++ Programming
    Replies: 3
    Last Post: 12-26-2008, 10:26 PM
  2. Question 39: Quicksort vs Linear Search
    By Kleid-0 in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 04-17-2005, 11:03 AM
  3. Using quicksort and radix sort for an anagram program
    By RazielX in forum C Programming
    Replies: 2
    Last Post: 05-03-2004, 09:33 AM
  4. quicksort problem
    By spinner in forum C Programming
    Replies: 9
    Last Post: 05-04-2003, 02:02 PM
  5. Quicksort
    By Nutshell in forum C Programming
    Replies: 1
    Last Post: 01-15-2002, 08:42 AM

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