quicksort issues

[jamesfarrow]

Hi
I'm really struggling with quicksort, to put it simply my code just doesn't work at all. Sorry it compiles and runs but without the desired result and I don't know why. I am trying to 'learn' a bit of c++ so please bear in mind I am a novice at best!!

Thanks

  //
//  main.cpp
//  exercise 8.15
//
//  Created by James Farrow on 11/02/2016.
//  Copyright © 2016 James Farrow. All rights reserved.
//
// quicksort algorithm

#include <iostream>
#include <ctime>

int partition( int[], int, int);
void quickSort(int[], int, int);

int main()
{
    srand ( static_cast<unsigned int>( time ( NULL )));
    
    
    const int arraySize = 12;// const variable for arraysize
    const int arrayStart = 0;
    int randomArray[] = {13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11};//initilaise array with zero
    //int randomArray[arraySize] = { 0 };//initilaise array with zero
    
    
    //fill array with random numbers to sort
    //for (int i = 0; i < arraySize; i++) {
        //randomArray[i] = 1 + rand() % 100;
    //}
    
    //print array to screen
    for (int i = 0; i < arraySize; i++) {
        std::cout << randomArray[i] << " ";
    }
    
    
    //int pivot = 0;
    //pivot = partition(randomArray,arrayStart, arraySize);
    quickSort(randomArray, arrayStart, arraySize);
    
    //std::cout << "pivot: " << pivot << std::endl;
    std::cout << std::endl;
    
    
    //print array to screen
    for (int i = 0; i < arraySize; i++) {
        std::cout << randomArray[i] << " ";
    }
    
    
    std::cout << std::endl;

}

int partition(int array[],int start, int end)
{
    int x = array[end - 1];
    int i = -1;
    
    for (int j = start; j < end - 1 ; j++) {
        if (array[j] <= x) {
            i++;
            std::swap(array[i],array[j]);
        }
    }
    std::swap(array[i + 1], array[end - 1]);
    return i+1;
}

void quickSort(int array[], int start, int end)
{
    int q = 0;
    
    if (start < end) {
        q = partition(array, start, end);
        quickSort(array, start, q - 1);
        quickSort(array, q + 1, end - 1);
    }
}

[jamesfarrow]

bump...

[Chervil]

Suggestions: "it compiles and runs but without the desired result" is so broad that it could mean anything from a misplaced character in the code somewhere, to a broken logic calling for a complete redesign.

To find out which, you need more information.

What I would do is to consider several possible actions:

a) (perhaps) test it on a smaller array to keep things more manageable
b) get more information by running the program with a debugger and tracking the values as it runs
c) or add extra cout statements to display important values such as the parameters passed to each function and the contents of the portion of the array it is handling.
d) since the sort is dependent on function partition(), you could test that in isolation, to ensure that it is doing what you expect.

[DeathLeap]

void quickSort(int arr[], int left, int right) {

      int i = left, j = right;

      int tmp;

      int pivot = arr[(left + right) / 2];

 

      /* partition */

      while (i <= j) {

            while (arr[i] < pivot)

                  i++;

            while (arr[j] > pivot)

                  j--;

            if (i <= j) {

                  tmp = arr[i];

                  arr[i] = arr[j];

                  arr[j] = tmp;

                  i++;

                  j--;

            }

      };

 

      /* recursion */

      if (left < j)

            quickSort(arr, left, j);

      if (i < right)

            quickSort(arr, i, right);

}

[jamesfarrow]

DeathLeap sorry for being a pain in the rear, can you please explain :)

[DeathLeap]

By the way, that's not my code but I can explain what it does.

example:

{1, 12, 5, 26, 7, 14, 3, 7, 2}

this is unsorted, we choose the middle value to start sorting

we choose pivot = 7

Now, we compare:

the right and the left with 7

1 < 7, keep it.

12 > 7 and 2 < 7, swap 12 and 2.

{1, 2, 5, 26, 7, 14, 3, 7, 12}

5 is less than 7, keep it.

26 > 7 and 7 equals 7, swap 26 and 7.

{1, 2, 5, 7, 7, 14, 3, 26, 12}

and so on..

[jamesfarrow]

Thanks it makes a bit more sense!
The next problem is - this was supposed to be an exercise using pointers and arrays lol

[DeathLeap]

Google search it and im sure you will find tons of algorithms.

[Duthomhas]

I don't want to sound unkind to another member here, but nothing DeathLeap has given you is particularly helpful... (here's uncommented code that doesn't look like yours; here's an explanation that doesn't behave like yours; i give up, google it).

Chervil has given you solid advice, even if it looks harder. (It's not.)

You have two major problems in your code:

1) off-by-one errors
2) your partition function doesn't work correctly.

Do as he said, adding some cout statements and testing the partition() function by itself (on a variety of different arrays, including {1 2 3 4 5} and {5 4 3 2 1} and {1} and {}).

Then fix your quickSort() function.

Hope this helps.

[jamesfarrow]

Hi Duoas

Thanks for your help I have gone and hard think about it. I have corrected the off by one error and some others that I noticed. Cheers.

I have the following:

const int arraySize = 12
and function call is now

quickSort(randomArray, arrayStart, arraySize - 1);

So the final element is being 'addressed' correctly whereas it wasn't before. Is there a better way around this issue? Instead of putting a - 1 as I have done?

Thanks to everyone who has helped me so far - I really do appreciate your time and expertise.

Thanks again.

[Duthomhas]

In C++ functions will typically be designed so that the arguments are first-elemnt and one-past-the-last-element. However, it is not uncommon to address elements as you have done.

If you are concerned by simple ugliness, create a function to mediate it:

template <std::size_t N>
void quickSort( int (&arr)[ N ] )
{
  return quickSort( arr, 0, N-1 );
}

  quickSort(randomArray);

Hope this helps.

[jamesfarrow]

Thanks! I have created a variable called sizeOfArray and used sizeof(array)/sizeof(int) - 1.
Then used that in the function call. Not ideal but atleast it works!!
I tried to use it in the function, but xcode informed that the array in the function was only a pointer and would return that only.

I'm only learning!

Cheers for all of your help!!