Suggestions on how to better write a quicksort function?

This is a discussion on Suggestions on how to better write a quicksort function? within the C Programming forums, part of the General Programming Boards category; Hi! I'm a first semester computer science student, and i'm working on an extra credit assignment for my C++ class ...

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    2

    Suggestions on how to better write a quicksort function?

    Hi! I'm a first semester computer science student, and i'm working on an extra credit assignment for my C++ class (although the code below is in C, it should be portable to C++). The assignment is to write a quicksort function using in-place sorting. I already have a working function below, however, I'd like to make it more efficient, if possible.

    At first, I considered using an internal stack rather than recursion, however I'm not sure if that would be the best way to go about it, considering I would have to allocate twice the memory occupied by the array itself in order to create enough stack space for a worst-case scenarion, not to mention that would require stdlib.h, and I'm trying to avoid using libraries if possible. However, I am concerned that, using recursion, this function could possibly overload the execution stack and collapse the universe into a singularity.

    Anyway, I'm open to criticism, be it constructive or purely vitriolic. Thanks!

    Code:
    void __qs_sw(int* a, int* b)
    {
    	int s = *a;
    	*a = *b;
    	*b = s;
    }
    
    // quicksort(int* arr, unsigned nm)
    // int* arr:	the pointer to the beginning of your array
    // int nm:	the number of members in your array
    //
    // example:
    // int arr[] = { 33, -33, 2124, 99, -1000, 40, 27, 99, 30 };
    // quicksort(arr, sizeof(arr) / sizeof(int));
    extern void quicksort(int* arr, unsigned nm)
    {
    	int lp=1, rp = nm - 1;					// initialize the pointers at the left and right sides of the array
    	while (lp < rp)						// loop until the pointers collide
    		if (arr[lp] > arr[0] && arr[rp] < arr[0])	// if the left side is greater and the right side is lesser,
    			__qs_sw(&arr[lp++], &arr[rp--]);	// swap the values
    		else if (arr[lp] <= arr[0])			// otherwise, if the left side is greater
    			lp++;					// increment the left pointer
    		else						// otherwise, if the right side is lesser
    			rp--;					// decrement the right side pointer
    	if (arr[lp] > arr[0])					// now, compare the last value the left pointer is sitting on to the pivot
    		lp--;						// if it's greater than the pivot, decrement lp (which is now the target to swap the pivot into) 
    	__qs_sw(&arr[lp], &arr[0]);				// now, swap the pivot into its new target home
    	if (lp > 1)						// if we have more than one left-side member,
    		quicksort(arr, lp);				// sort the left-side sub-array
    	if (nm - lp > 2)					// if we have more than one right-side member,
    		quicksort(&arr[lp + 1], nm - lp - 1);		// sort the right-side sub-array
    }

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    using the name __qs_sw is not great, as names starting with __ are reserved for the compiler/library implementation. Instead of using a reserved name, use static to ensure it isn't exported.

    Technically, rp and lp aren't pointers, they're indices. For efficiency, you may actually want to make them pointers.

    extern on a function definition is meaningless. the nm should be size_t instead of unsigned.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    Your partitioning loop is non-optimal in terms of the number of comparisons. The first if-statment tests arr[lp] > arr[0] but given that the result of that individual test isn't remembered, you are forcing yourself to test the same thing again in arr[lp] <= arr[0].
    The usual way to do it is to have two while loops inside the partitioning loop. One of them advances lp while it points to an item less than the splitter, and the other one decrements rp while it is not less than the splitter.

    The other slightly more advanced way of optimising it is to only recurse one the smaller portion after the partitioning, and loop on the other portion instead. This also protects it against maliciously crafted input which would otherwise cause stack overflow.

    Why pass in nm as unsigned but then assign it to a signed int? Don't mix them unless you have to.
    Note that if you change rp to unsigned you'll have to do a little work to make sure it doesn't explode for sorting zero items.
    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: 8
    Last Post: 10-29-2008, 06:33 AM
  2. Undefined Reference Compiling Error
    By AlakaAlaki in forum C++ Programming
    Replies: 1
    Last Post: 06-27-2008, 11:45 AM
  3. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 06:39 AM
  4. Creating a student grade book-how?
    By Hopelessly confused in forum C Programming
    Replies: 5
    Last Post: 10-03-2002, 08:43 PM
  5. Interface Question
    By smog890 in forum C Programming
    Replies: 11
    Last Post: 06-03-2002, 05:06 PM

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