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] << " ";
   }


}

It's homework. I have to do a quicksort without any of the included quicksort stuff. But thanks! — Neko
– Neko, Commented Apr 7, 2014 at 2:01

paxdiablo · Accepted Answer · 2014-04-07 02:19:52Z

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.

edited Apr 7, 2014 at 2:19

answered Apr 7, 2014 at 1:51

paxdiablo

888k243 gold badges1.6k silver badges2k bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Neko Over a year ago

I think I fixed that problem. I had accidentally posted an earlier version of the code. #stupidme

paxdiablo Over a year ago

@Neko, that's even worse. You're supposed to compare with the pivot value as your original code was. It's just you also need that extra limiting check.

Neko Over a year ago

I changed the line you quoted above with this: while(first<last) I left the pivot value vs first check in there. I believe that is what it should be. If not, could you explain in greater detail? Thanks!

paxdiablo Over a year ago

@Neko, have injected the code from some quicksort stuff I did quite recently. Suggest you look at that.

Adam Burry · Accepted Answer · 2014-04-07 02:31:20Z

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; }

Collectives™ on Stack Overflow

Quicksort in an array C++

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related