Quick Sort Method in C

[CTheBaptist]

Hey, so I had to implement a quick sort method I found online into my existing code. Got it compiled and for some of the values it does sort but not all. I was wondering why does it not sort in descending order for this?

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) 
{
        int seed = 4;                    

        int i;
        int size = 10;                   

        srand(seed % 4);                 
        
        int *int_array = (int*)malloc(sizeof(int)*size);  


        printf( "Original:\n" );
        for (i = 0; i < size; i++)
        {
            int_array[i] = rand() % 100;                  
            printf( "%d\n", int_array[i] );    
        }

        // This is the method which has to be integrated
        int pivot = int_array[size / 2];
 
  	    int j;
  	    for (i = 0, j = size - 1; ; i++, j--) {
    		while (int_array[i] < pivot) i++;
   	 	    while (int_array[j] > pivot) j--;
 
    		if (i >= j) break;
 
    		int temp = int_array[i];
   	 	    int_array[i]     = int_array[j];
    		int_array[j]     = temp;
  	    }

        printf( "After this masterpiece:\n" );
        for (i = 0; i < size; i++)
        {
            printf( "%d\n", int_array[i] );              
        }

        int failed = 0;
        for (i = 0; i < size; i++)
        {
                if (int_array[i] < int_array[i+1])      
                {
                        failed = 1;
                        break;
                }
        }
        
        printf("------------------\n");
        printf("------------------\n");
        if (failed == 1)
        {
                printf("FAILED SORTING\n");
        } else {
                printf("SUCCESSFUL SORTING\n");
        }
        printf("------------------\n");
        printf("------------------\n");

        free(int_array);

        return 0;
}

[lastchance]

YOUR code this manifestly isn't. It's a half-baked and inept modification of the code here:
http://www.cplusplus.com/forum/beginner/245018/#msg1084369
That code was for an ascending sort and was done with bubble sort.

No idea what sort method you are attempting, but it's a long way from "quicksort".

[CTheBaptist]

Oh I know you did it, whoever posted it posted the question from the assignment. The quick sort method is the part I'm just looking at, not the rest, but I saw that someone had it working without having the need to import it. Sorry if I was trying to look like I was taking credit, I just wanted to see why my quicksort isn't working as expected.

Quick sort from here: https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#C

[dhayden]

Quicksort is a recursive algorithm. That means it needs to be in it's own function. Start by moving lines 23-36 to their own function. Then figure out what the arguments to that function should be. On possibility is the array, the lower index the upper index. It sorts the array values between the given indices.

Then figure out the base case of the recursion. I always like to start with the base case because it's just too darned easy to forget it. I also always code a recursive function with this basic structure:

if (base case) {
   // do the base case
} else {
   // do the recursive case
}

Finally, figure out what the recursive case is and how you should call the function recursively.

If you run into trouble, add temporary code to print the function arguments when you enter the function. This will help you see if your recursion is doing what you expect.

[keskiverto]

If you had "integrated" the quicksort that you did link to,
then the lines 23-36 of your program would read:
quicksort( int_array, size );


Ideally, you would go for:

#include <iostream>
#include <chrono>
#include <random>
#include <vector>
#include <algorithm>

int main ()
{
  using std::cout;
  unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
  std::mt19937 g1( seed1 ); // inadequate, but will do for now
  std::uniform_int_distribution<int> distribution( 0, 99 );

  std::vector<int> foo( 10 );
  cout << "Original:\n";
  for ( auto & x : foo ) {
    x = distribution( g1 );
    cout << x << '\n';
  }

  std::sort( foo.begin(), foo.end(),
             [](int l, int r){return l > r;} ); // this is the most important
  // concept for descending

  cout << "After this masterpiece:\n";
  for ( auto x : foo ) cout << x << '\n';
}

[Thomas1965]

Here's the quicksort properly explained.
https://www.youtube.com/watch?v=SLauY6PpjW4&index=21&list=PLOuZYwbmgZWXvkghUyMLdI90IwxbNCiWK

[lastchance]

Regardless of which sorting algorithm you use, it would make sense to put it in a separate function. In the case of quicksort, that is actually vital. It is a recursive function, so you missed the two most crucial lines when copying it into "that" piece of code.

Apart from that, you can pretty well incorporate the piece of code that you linked to with two things that @Keskiverto has given you:
- the way it is invoked from main();
- the fact that if you want to sort descending rather than ascending you will have to reverse less-than/greater-than in the two lines where it compares the array element with the pivot.