Thread: Questions on basic Quick Sort

  1. #1
    Registered User
    Join Date
    Nov 2003
    Posts
    5

    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.

  2. #2
    essence of digital xddxogm3's Avatar
    Join Date
    Sep 2003
    Posts
    589
    are you attempting to sort a singular array or another form of data structure?
    "Hence to fight and conquer in all your battles is not supreme excellence;
    supreme excellence consists in breaking the enemy's resistance without fighting."
    Art of War Sun Tzu

  3. #3
    Registered User
    Join Date
    Nov 2003
    Posts
    5

    Reply to Quick Sort problems

    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!

  4. #4
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    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
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >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.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Quick sort VS Merge Sort
    By sachitha in forum Tech Board
    Replies: 7
    Last Post: 09-03-2004, 11:57 PM
  2. basic questions on C#
    By black in forum C# Programming
    Replies: 3
    Last Post: 12-09-2003, 09:23 AM
  3. First post: few basic questions:
    By 1Fly4i in forum C++ Programming
    Replies: 3
    Last Post: 05-06-2002, 06:30 AM
  4. 2 quick questions
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 11-29-2001, 12:32 AM
  5. A few quick questions...
    By cpp4ever in forum C++ Programming
    Replies: 3
    Last Post: 10-21-2001, 09:28 AM