Questions on basic Quick Sort

Hello,

I am reading about basic quick sort and I have questions to ask about how it works.

First of all, the book says that there are 3 parts to quick sort. A head and tail pointer and a partition value. So, what is a partition value?

Secondly, the book uses the leftmost element of the array as the partition element. I presume the leftmost element is the head pointer. So, is it a must or recommended that the head pointer is used as the partition element?

Thirdly, does the head and tail pointers move towards each other at the same time? Or does the tail pointer move leftwards first, then the head pointer move rightwards?

Fourth, when does swapping of elements occur? And when partitioning is complete, there will be subarrays. So,will the quick sort process be done on each of these subarrays?

By the way, the book I am reading is ' C/C++ Annonated Archives' published by Osbourne.

Thanks for the reply.

are you attempting to sort a singular array or another form of data structure?

Hello,

I am planning to sort a regular array of integers.
I am not too sure about how the quick sort method arranges array elements in order.

Please reply quickly if you can...thanks!

I haven't learned many sorting algorithms, but it sounds like for quicksort you choose a value from the array, and then "partition" it, by putting any elements that are greater than that value are placed in the upper part of the array and any less are placed in the lower part...Then you recursively break it into smaller and smaller parts. I haven't been able to implement it myself yet, but there's quite a bit on google. I'll post this afternoon if I can figure it out

>So, what is a partition value?
The partition value tells the algorithm where to break the array up for further partitioning. For example, if the partition of the following array is 6:

Code:

---

9,8,7,6,5,4,3,2,1

---

Then the algorithm will act on two separate partitions independently based on that location, the left hand partition is

Code:

---

9,8,7

---

and the right hand partition is

Code:

---

5,4,3,2,1

---

Each of these halves are split in a similar manner until only two items are left. At this point a simple test and swap is performed to sort those two items. By breaking the array down into trivial sorting problems, the entire array can be sorted easily and efficiently.

>So, is it a must or recommended that the head pointer is used as the partition element?
Actually, it isn't recommended as this is an iffy solution. What you want to do to achieve optimum performance is partition the array at right about the midpoint. This way each half is the same size, so you don't end up with partitions that look like this:

Code:

---

left: 9

---

Code:

---

right: 8,7,6,5,4,3,2,1

---

Two good ways of finding a partition value are randomization (probabilistic algorithms are unlikely to reach the worst case), and a partitioning scheme called median-of-three. Basically what this does is take three values from the array, then use the median value of those three as the partition value.

>does the head and tail pointers move towards each other at the same time?
Difficult to explain, do a google search for quicksort demos and find a Java applet that shows it to your understanding. That saves me the effort of describing a demo run. :)

>when does swapping of elements occur?
During partitioning.

>So,will the quick sort process be done on each of these subarrays?
Yes, quicksort is typically called recursively on each half of the partition, then another partition is performed on each of those halves, and so on until there's nothing left to recurse on.