Thread: QuickSort — C Implementation (Non-Recursive)

  1. #1
    Registered User
    Join Date
    Nov 2018
    Posts
    21

    QuickSort — C Implementation (Non-Recursive)

    Hi, I was anticipating if someone could give me some constructive feedback on the code below (not something like "don't use pointers" or "always use braces with loops or conditions", more like, "there is problem in the algorithm", or "this could be a better approach/algorithm", or "error in the code"). No offense to anyone. I'm here to learn. Thanks.

    Code:
    #include <stdio.h>
    
    void swap(int* a, int* b)
    {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    
    
    void reversearray(int* arr, int size)
    {
    	for (int i = 0; i < size / 2; i++) swap(arr + i, arr + ((size - 1) - i));
    }
    
    int partitionarray(int* arr, int start, int end)
    {
        int pivot = arr[end];
        int pIndex = start;
        for (int i = start; i < end; i++)
        {
            if (arr[i] <= pivot) swap(&arr[i], &arr[pIndex++]);
        }
        swap(&arr[pIndex], &arr[end]);
        return pIndex;
    }
    
    
    
    
    void quicksort(int* arr, int start, int end,  _Bool reverse)
    {
        if (start < end)
        {
            int pIndex = start;
            while (pIndex < end) pIndex = partitionarray(arr, start, pIndex + 1);
            if (reverse) reversearray(arr, end + 1);
        }
    }
    
    
    int main()
    {
        int arr[] = { 8, 5, 9, 0, 6, 4, 3, 7, 1, 2 };
    	int size = sizeof(arr) / sizeof(arr[0]);
    	quicksort(arr, 0, size - 1, 1);
    	for (int i = 0; i < size; i++) printf("%d ", arr[i]);
    	return 0;
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,160
    I'd say get rid of the reverse parameter: you already rightly wrote a function to reverse that can be called right after a call to the quicksort function, so let your functions do one thing and do it well rather than clutter their interfaces.

    I'm curious if you're actually doing quicksort though: conceptually quicksort is supposed to have recursive calls into both partitions, but it's possible to eliminate one call as it is tail recursion, and then it should be possible to eliminate the other with an explicit stack. However, you do no recursion, yet you don't use an explicit stack. Furthermore it looks like you don't start with the whole array when doing the first iteration of partitioning? It looks almost as if you're doing a variant of bubble sort instead.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by laserlight View Post
    Furthermore it looks like you don't start with the whole array when doing the first iteration of partitioning? It looks almost as if you're doing a variant of bubble sort instead.
    Just suggesting nothing else
    As he doesn't use the whole array, I suggest him instead of using bubble sort which is dramatically increasing the burst time of the code, he can use "binary search recursively/iterative" for finding the pivot o(logn) and then by for loop he can run on the array according to the pivot which will take o(n), in total o(nlogn) instead of bublesort which takes o(n^2).

  4. #4
    Registered User
    Join Date
    Nov 2018
    Posts
    21
    Thank you! Well, I wanted to try something like python's sorted(iterable[, key][, reverse]) without the key parameter.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,160
    Quote Originally Posted by RyanC
    he can use "binary search recursively/iterative" for finding the pivot o(logn)
    Please stop making ridiculous suggestions. For starters, binary search only works on a sorted sequence.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Nov 2018
    Posts
    21
    Thanks @laserlight. It didn't start with the whole array, and now it seems like it is replicating a bubble-sort. Could you give an example how can I use explicit stack to make this actual qucksort without recursion?

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,160
    Quote Originally Posted by flash13 View Post
    Thanks @laserlight. It didn't start with the whole array, and now it seems like it is replicating a bubble-sort. Could you give an example how can I use explicit stack to make this actual qucksort without recursion?
    I've never seen it done myself. I'd suggest starting with something simpler, maybe a depth-first search of a binary tree where you use iteration with an explicit stack instead of recursion. Or, you come up with a working implementation of quicksort, turn the tail recursion into iteration, check that that works, and only then introduce an explicit stack for the non-tail recursion to be turned into iteration.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Nov 2018
    Posts
    21
    well, thanks for useful feedback. Will try that.

  9. #9
    Registered User
    Join Date
    Apr 2013
    Posts
    1,646
    It's probably simpler to implement a non-recursive quicksort using a queue. Example pseudo code with Lomuto partition scheme:

    Can we use a queue in quicksort in C? - Quora
    Last edited by rcgldr; 01-01-2019 at 10:31 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Changing implementation for quicksort algorithm?
    By garmbrust in forum C++ Programming
    Replies: 5
    Last Post: 11-15-2015, 12:55 AM
  2. is my C++ quicksort implementation correct?
    By nik in forum C++ Programming
    Replies: 4
    Last Post: 04-05-2011, 12:21 PM
  3. non-recursive quicksort is too slow?
    By RichSelian in forum C Programming
    Replies: 4
    Last Post: 03-25-2011, 01:14 PM
  4. Make Recursive function 'Tail-Recursive'
    By dp2452 in forum C Programming
    Replies: 7
    Last Post: 12-04-2009, 10:13 AM
  5. Non Recursive Quicksort..
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 03-14-2002, 10:22 AM

Tags for this Thread