User:TakuyaMurata/Barcelo's method

From Wikipedia, the free encyclopedia

The following post was moved from talk:Quicksort -- Taku

I discovered a while ago that swapping the elements was inefficient. There were too many writes to temporal variables to be good.

I used other method instead of swapping. This method has two restrictions, though: - The pivot chosen must be the first or the last position of the sequence. - The method may surpass the limits of the sequence in some cases, if not prevented.

However, both restrictions can be satisfied always, so the algorithm is still general.

The idea is the following. As you have to keep the pivot in a register for the comparisons, you may use the pivot's position on the array as if it was a 'blank space', that could be overwritten without caring about its value. Everytime you move an element from one side to the blank space, it's previous position becomes blank.

I will try to show it graphically:

1. We have:

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

2. We chose 5 as the pivot, leaving a 'blank space':

  5*, 2, 7, 1, 8, 4, 6

3. We compare from the other side until we find an element lower than the pivot, the 4:

  5*, 2, 7, 1, 8, 4, 6

4. We move the 4 to the blank space, overwriting it, and the previous position becomes blank:

  4, 2, 7, 1, 8, 4*, 6

5. Then, we search on the other direction, starting from the element following the last blank, the 2:

  4, 2, 7, 1, 8, 4*, 6

6. We move the 7 to the blank space, then we will continue searching on the other direction:

  4, 2, 7*, 1, 8, 7, 6

7. We compare 8, higher. Move to 1, which is lower, so we move 1 to the blank space, continuing from the other direction:

  4, 2, 1, 1*, 8, 7, 6

8. The two indexes are equal, so we wrote back the pivot value on that position and finish:

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

Things that could be wrong: - If you want to choose a pivot from other position, just swap the element on that position with the first/last position - The method surpass the sequence's limit. Example:

1. We have:

  5, 1, 2

2. We take 5 as pivot:

  5*, 1, 2

3. We move 2 to the blank space:

  2, 1, 2

4. We go through all the elements from 1 looking for an element >=5, which there is none.

  2, 1, 2 ... !! -->

Error!!

There are three ways to avoid this: 1. We compare everytime if both indexes are equal (inefficient) 2. We write the pivot's value on the first blank space on the right(left)

  2, 1, 5
  That could not work with other comparison functions

3. We make sure there's at least one element lower than the pivot at the left, and one element higher at the right. For example, using the following method, which also is an improvement to quicksort:

  - We take the first, second, and last elements on the sequence. We compare them and put the lowest on the first position, the highest on the last position, and the other on the second position.
  - We take the element on the second position as the pivot, and start going across the sequence from the second from last position, to the first.

This is taking a median from the elements first, second, and last.

Phew! That was long! This method has less variable assignations and comparisons than the swap function, and my calculations on arrays of integers show it's about 5% faster. It should be more efficient with heavier elements, though.

I hope the C code will be clearer than the explanation.

I haven't found this on any web, so unless proven wrong, I think I discovered it. Just add the text Carlos Hoyos Barcelo (2005) discovered a small improvement removing the swap function...