Quicksort in an array C++

Question

I am trying to partition an array using a quicksort algorithm shown in the code. I believe the problem is in the while loop. Can you see/explain what I'm doing wrong and what I should do to fix it? Thanks!

Edited because I posted an earlier version of the code.

#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;

int intArray[10];
int sizeArray= 10;

int main(){

srand(time(0));
    for(int i = 0; i < sizeArray; i++){
      //random numbers from 1 to 10:
      intArray[i] = rand() % 100 + 1;
   }

   for(int i = 0; i < sizeArray; i++){
      cout << intArray[i] << " ";
   }

int *pivot = &intArray[0];
int *first = &intArray[1];
int *last = &intArray[9];


cout<<"pivot "<<*pivot <<endl;


while(first<last)
{
    while(*first<*pivot)
    {
        first++;

    }
    while(*last>*pivot)
    {
        last--;
    }
    if(*first>*last)
    {
        int aSwap = 0;
        aSwap = *first;
        *first = *last;
        *last = aSwap;

    }

    if((first-1) > last)
        break;


}

        int bSwap=0;
        bSwap = *first;
        *first= *pivot;
        *pivot = bSwap;


    cout<<"After partition"<<endl;
   for(int i = 0; i < sizeArray; i++){
      cout << intArray[i] << " ";
   }


}

Answer 1

I'll give you one immediate peice of advice re:

while(*first<*pivot)

If your pivot at array[0] is the largest value in the array, you're going to run off the end of the array and keep going, resulting in undefined behaviour.

The termination condition for that loop should include detecting if the first pointer has reached the last one.

Ditto for the loop that decrements last.

And, of course, once the pointers meet, there's no need to do a swap.

---

And your edit comparing the first against last values is actually worse. You're supposed to be looking for two values that you will swap across from where the pivot wiill eventually go.

I suggest reverting the code and simply adding the limiting check I suggested. Here is the correct code for doing the partition swapping operation, from some code I wrote not that long ago:

// Simplest form of pivot selection.

pvt = 0;
lft = 1;
rgt = 9;

// Continue until new pivot point found.

while (lft < rgt) {
    // find value on left greater than pivot value.

    while ((lft < rgt) && (array[lft] <= array[0]))
        lft++;

    // Then, assuming found, find value on right less than pivot value.

    if (lft < rgt) {
        while ((lft < rgt) && (array[rgt] >= array[0]))
            rgt--;

        // Swap them if found.

        if (lft < rgt)
            SWAP (array[lft], array[rgt]);
    }
}

// Back up to find proper swap point for pivot value, then swap.

while ((lft > 0) && (array[lft] >= array[0]))
    lft--;

if (lft != 0)
    SWAP (array[lft], array[0]);

// Now everything left of pivot is less than pivot value, everything
// right is greater/equal. Go and sort the two sections.

Answer 2

You are making your life too complicated.

GCC 4.7.3: g++ -Wall -Wextra main.cpp

#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;

int intArray[10];
int sizeArray= 10;

int main() {
  srand(time(0));
  for (int i = 0; i < sizeArray; ++i) {
    //random numbers from 1 to 10:
    intArray[i] = rand() % 100 + 1; }

  for(int i = 0; i < sizeArray; ++i){
    cout << intArray[i] << " "; }

  int* pivot = &intArray[0];

  cout << "pivot " << *pivot << endl;

  for (int i = 0; i < sizeArray; ++i) {
    if (intArray[i] < *pivot) {
      std::swap(intArray[i], *(pivot + 1)); // move the pivot ahead one
      std::swap(*pivot, *(pivot + 1)); // move the value into the hole
      ++pivot; }}

  cout<<"After partition"<<endl;
  for (int i = 0; i < sizeArray; i++){
    cout << intArray[i] << " "; }

  return 0; }