Need help with (an attempt of) a quicksort algorithm in c++

I've tried a bunch of different ways to write this, but mostly i get stuck in an endless loop. This version of the code just doesn't sort it at all and i don't know what the problem is.

void quickSort(int unsorted[], int left, int right) {
      int i = left, j = right;
      int pivot = (left + right) / 2;

      while (i == pivot || j == pivot) {
          if (unsorted[i] >= unsorted[pivot] && unsorted[pivot] >= unsorted[j])
              swap(unsorted[i], unsorted[j]);

          if (i < pivot)
              i++;
          if (j > pivot)
              j--;
      };

      if (left < j && unsorted[left] != unsorted[j])
          right = pivot, quickSort(unsorted, left, right);
      if (i < right && unsorted[right] != unsorted[i])
          left = pivot +1, quickSort(unsorted, left, right);

}

unsorted is an array filled with 10开发者_C百科0 random values from 0 to 200.

I'm sorry for the slow update. And about the code, i re-wrote most of it. This is what it looks like now:

void quickSort(int unsorted[], int left, int right) 
{
    int i = left, 
        j = right,
        count = 0;
    int pivot = (left + right) / 2;

    do
    {
          while (unsorted[i] < unsorted[pivot])
              i++;
          while (unsorted[j] > unsorted[pivot])
              j--;

          if (unsorted[i] >= unsorted[j] && i <= j)
          {
              swap(unsorted[i], unsorted[j]);
              i++;
              j--;
              count++;
          }
          if (i == pivot && unsorted[pivot] < unsorted[j] && count == 0)
          {
              swap(unsorted[i], unsorted[j]);
              i++;
              j--;
              count++;
          }
          if (j == pivot && unsorted[pivot] < unsorted[i] && count == 0)
          {
              swap(unsorted[i], unsorted[j]);
              i++;
              j--;
              count++;
          }

          if (i == j && unsorted[i] > unsorted[pivot] && count == 0)
          {
              swap(unsorted[i], unsorted[pivot]);
              i++;
              j--;
              count++;
          }
          if (i == j && unsorted[i] < unsorted[pivot] && count == 0)
          {
              swap(unsorted[i], unsorted[pivot]);
              i++;
              j--;
          }

          count = 0;

    } while (i < j);

    if (left < j)
        quickSort(unsorted, left, j);
    if (i < right)
        quickSort(unsorted, i, right);

}

i've been trying this code over and over again with 10 random values and it works most of the time. There are some cases it doesn't work and i'm trying to figure out when.

An example of when it doesn't work are when the values are: 160, 151, 159, 112, 7, 121, 105, 48, 186.

Solved it. Removed a lot of the code, made it a lot more simple, but atleast it works. Don't even know if u can call it a quicksearch anymore, but here is the final version:

void quickSort(int unsorted[], int left, int right) 
{
    int i = left, 
        j = right;
    int pivot = right;

    do
    {
        while (unsorted[i] < unsorted[pivot])
            i++;
        while (unsorted[j] > unsorted[pivot])
            j--;

        if (unsorted[i] >= unsorted[j] && i <= j)
        {
            swap(unsorted[i], unsorted[j]);
            i++;
            j--;
        }
    } while (i < j);

    if (left < j)
        quickSort(unsorted, left, j);
    if (i < right)
        quickSort(unsorted, i, right);
}

You didn't test your function on an array of length 1.

Get that to work, then try an array of length 2.

Once that's working, there's a good chance it'll work when you give it an array of length 3.

EDIT:

Kudos for including a reproducible example.

This code fails before recursion. The first step is to choose a pivot element and move some elements around until the pivot element is not less than any to the left of it and not more than any to the right of it. Your code loses track of which element it considers the pivot element; it swaps out the pivot element, but seems to think that the same location is still the pivot. Try working the algorithm this far with pencil and paper, and you'll see what I mean.

This check seems strange to me

while (i == pivot || j == pivot)

Shouldn't it be at least

while (i != pivot && j != pivot)

p.s. I think this won't be the only problem, but for a start...

Without seeing swap, my first hunch would be that your swap takes its arguments by value. I.e. it swaps two copies, instead of the arguments themselves.

Oh dear. I'm sorry Joe, but things aren't looking so good for your code. It requires many computovascular surgeries and even then I'm not so sure that it will make it. Let's write a prescription and I'll let you wield the scalpel:

1. If left >= right, return. Don't mess with 1-element arrays.
2. Swap your pivot element with your leftmost element (rightmost is fine too, but I have to pick one). At the end, you will swap it into the the correct spot between your partitions. You can do this by swapping the leftmost element (containing your pivot) with the rightmost element of the leftmost partition as given in the next step.

3. Now we need to partition. Let's do the simplest partition that we can think of. Here's one that I suggest when you're just starting with the quicksort: [ < pivot | >= pivot | unsorted ]. That's the invariant we want at every step. At the beginning, everything will be in the unsorted partition. At the end, there will be nothing in the unsorted partition. How can we do this?

   1. Loop across from left+1 to right in the array.
   2. If the element is less than the pivot, we add it to the [ < pivot ] partition with the correct swap (I leave this to you - you'll want to keep track of the boundary between the left two partitions). If it isn't, we move on.
4. After you put the pivot in place, your array should look like [ < pivot | pivot | >= pivot ]. Quicksort the leftmost and rightmost partitions and things should really be looking up for this code.

Try fancier things like [ < pivot | unsorted | >= pivot ] partitioning (which is faster if done correctly) after you get this working. Your current implementation I think is trying to do this sort of partitioning, but unless i or j points to an element equal to the pivot, there won't be any swapping going on. This sort of partitioning is trickier and I suggest that we give your code a pulse before entering it in any races.

This will, hopefully, get your code into shape, but it this will only be a pretty basic quicksort. You should look into Bentley-McIlroy partitioning and pivot choosing methods to make it more advanced.