question about Quick Sort

Hello all.

I'm sure you all are familiar with the quick sort algoritem, but I'm still gonna post it in short:

Code:

---

IF left < right THEN
  BEGIN
      pivot := partition (list, left, right);
      Quicksort (list, left, pivot-1);
      Quicksort (list, pivot + 1, right);
END

---

In the partition function, the norm is to usually pick the first number in the array as the pivot, right? But if you choose the last one as the pivot, the loop can become endless. How does that happen?

Thanks in advance

Did this become a pascal board? Why wasn't I informed?

Quote:

---

Originally posted by master5001
Did this become a pascal board? Why wasn't I informed?

---

Man it's just psedo code, why does it matter if it's in pascal, c or whatever? It's not the point of the question either... but just for you:

Code:

---

  if ( left > right )
    {
    pivot = partition( list, left, right );
    quicksort( list, left, pivot-1 );
    quicksort( list, pivot+1, right );
    }
  }

---

Errr... one of my quicksort algorithms uses the last number in each subarray as the pivot, and it works just fine, no endless loops. Post your partition code so we can have a look.

Ok, the (psedo) code is as followed:

Code:

---

Partition(A,p,r)
{
    x=A[p];
    i=p-1;
    j=r+1;
    while TRUE{
          do repeat j=j-1
          until A[j]<=x;

          do repeat i=i+1
          until A[i]>=x;
 
          if i<j
              swap(A[i],A[j]);
          else
            return j;
        }
}

---

I am told that if A[r] (the last item) is selected as the pivot it could result in an endless loop, but I realy don't see how...

Actually, the way you have it written, shouldn't it get an infinite loop everytime your pivot has a duplicate? If you try to find the pivot on something like:

Code:

---

7 6 4 9 8 2 7

---

will run indefinately regardless of whether the pivot is at the beginning or the end. I don't have time to check it, but I think one of those <= or >= needs to lose the "or equal". Check to see what happens with my above numbers depending on which "=" you take off and which end you use as the pivot, and you'll probably find your answer. Sorry, don't know the answer off the top of my head, my quicksorts are done a little differently so I had to figure out how yours worked first :D

Quote:

---

Originally posted by liberty4all
Man it's just psedo code, why does it matter if it's in pascal, c or whatever? It's not the point of the question either...

---

You didn't need to re-write the code. If I didn't give you a hard time then someone else would have. Actually, now that I think about it if you really want a skilled programmer's help then you should post code written in some other language. A well rounded programmer is at least familiar with all popular languages.

Quote:

---

Originally posted by PJYelton
Actually, the way you have it written, shouldn't it get an infinite loop everytime your pivot has a duplicate? If you try to find the pivot on something like:

Code:

---

7 6 4 9 8 2 7

---

will run indefinately regardless of whether the pivot is at the beginning or the end.

---

I tried your input and it worked fine, after running partition once the array looked like this:

Code:

---

7 6 4 2 8 9 7

---

Four numbers smaller or equal to 7 and three numbers bigger or equal to 7. I didn't write the code I posted before, that's the code I was given and I'm supposed to figure out how by selecting the pivot as the last item it can lead to an infinite loop.

Okay, I see where the error is now, your quicksort algorithm had an error, it should be this:

Code:

---

  if ( left > right )
    {
    pivot = partition( list, left, right );
    quicksort( list, left, pivot);
    quicksort( list, pivot+1, right );
    }
  }

---

You only do +1 and -1 with quicksort algorithms that place the pivot in between the two partitions. That being said, do this algorithm on something small like array={4,5} and you'll see that the quicksort loops infininetly if you choose 5 as the pivot, since 5 keeps getting swapped with itself, returning a partition of size 2 and a partition of size 0, thus starting over again. If you want to do the last number of the pivot, you need to change the quicksort to:

Code:

---

  if ( left > right )
    {
    pivot = partition( list, left, right );
    quicksort( list, left, pivot-1);
    quicksort( list, pivot, right );
    }
  }

---