|
Title: Quicksort algorithm tutorial Post by: QuestionBot on October 08, 2009, 12:15:54 AM Article: Quicksort algorithm tutorial (http://www.algolist.net/Algorithms/Sorting/Quicksort)
Question (James Ten Eyck): Your java algorithm for Quicksort does not seem to work. At the end of the first partition, on sorting the following numbers, you have an incorrection partition: 1 1 5 5 1 4 8 The first 5 becomes left, and the 4 becomes right. After swapping you have: 1 1 4 5 1 5 8 The first 5 (fourth index) is now left, and the right-most 1 is now right. Those get swapped, and i increases and j decreases. 1 1 4 1 5 5 8 now 1 is right, and 5 is left (4th and 5th elements, respectively). Returning right leaves 1 as the partition. That does not work because 4 is to the left of the partition but is greater than 1. Am I missing something here? Partners: Cell Phone Accessories (http://www.elitextreme.com) Title: Re: Quicksort algorithm tutorial Post by: Denis on October 08, 2009, 12:20:04 AM I checked the code. After the first partition (pivot = 5) source array becomes:
1 1 4 1 5 5 8 and partition function returns 4. It's ok, because then algorithm sorts 0..3 and 4..6 subarrays, which leads to the correct result. Partners: HTC HD2 Accessories (http://www.onlyhd2.com/) Title: Re: Quicksort algorithm tutorial Post by: jtphenom on October 08, 2009, 08:21:14 AM I thought that, with quicksort, the array index that is returned should be an index to a number that is already sorted and does not need to be sorted in the recursive calls to quicksort. You're saying that, after the first partition, 0-3 and 4-6 are each sublists, but I learned that quicksort makes it so, when 4 is returned, your partions are 0-3 and 5-6.
In any case when I go through the algorithm, I'm getting a different result. Can you show me the steps, please? I'm very confused. Title: Re: Quicksort algorithm tutorial Post by: Denis on October 08, 2009, 08:37:53 AM The returned value is an index of the first element of the right part. Let's see it on example:
Source array: 1 1 5 5 1 4 8 Pivot value: 5 After first call to partition(...): 1 1 4 1 5 5 8 partition(...) returns: 4 4 means, that arr[0..3] < 5 <= arr[4..6] Therefore, if we sort both left (0..3) and right (4..6) parts separately, then the whole array will become sorted. Tell, if it is clear or you need more explanations. Partners: Free Laptops (http://www.freelaptop4all.com) |