Prev: Question about Hugh Woodin's original proof of projective determinacy.
Next: New Anti-Cantor Attack
From: Martin M. + I am right:if I am not tell me:or I am right on 29 May 2010 22:00
[[in-place]] partition algorithm and can achieve the complete sort
using <math>O(\log n)</math> space (not counting the input) use on
average (for the [[call stack]]):

'''function''' partition(array, left, right, pivotIndex)
pivotValue := array[pivotIndex]
swap array[pivotIndex] and array[right] ''// Move pivot to end''
storeIndex := left
'''for''' i ''' from ''' left '''to''' right - 1 ''// left ≤ i <
right'' <!-- This comment is a must. Pseudo-code is ambiguous
otherwise -->
'''if''' array[i] ≤ pivotValue
swap array[i] and array[storeIndex]
storeIndex := storeIndex + 1
swap array[storeIndex] and array[right] ''// Move pivot to its
final place''
'''return''' storeIndex

partitions the portion of the array between indexes ''left'' and
''right'', inclusively, by moving all elements less than or equal to
<code>array[pivotIndex]</code> to the beginning of the subarray,
leaving all the greater elements following them. In the process it
also finds the final position for the pivot element, which it returns.
It temporarily moves the pivot element to the end of the subarray, so
it doesn't get in the way. Because it only uses exchanges, the final
list has the same elements as the original list. Notice that an
element may be exchanged multiple times before reaching its final
place. It should also be noted that in case of pivot duplicates in the
input array, they can be spread across left subarray, possibly in
random order. This doesn't represent a partitioning failure, as
further sorting will reposition and finally "glue" them together.

writing quicksort itself is easy:

'''procedure''' quicksort(array, left, right)
'''if''' right > left
select a pivot index ''//(e.g. pivotIndex := left+(right-
left)/2)''
pivotNewIndex := partition(array, left, right, pivotIndex)
quicksort(array, left, pivotNewIndex - 1)
quicksort(array, pivotNewIndex + 1, right)
From: mjc on 30 May 2010 18:35
On May 29, 7:00 pm, "Martin M. + I am right:if I am not tell me:or I
am right" <marty.musa...(a)gmail.com> wrote:
>  [[in-place]] partition algorithm and can achieve the complete sort
> using <math>O(\log n)</math> space (not counting the input) use on
> average (for the [[call stack]]):
>
>    '''function''' partition(array, left, right, pivotIndex)
>       pivotValue := array[pivotIndex]
>       swap array[pivotIndex] and array[right] ''// Move pivot to end''
>       storeIndex := left
>       '''for''' i ''' from ''' left '''to''' right - 1 ''// left ≤ i <
> right'' <!-- This comment is a must. Pseudo-code is ambiguous
> otherwise -->
>           '''if''' array[i] ≤ pivotValue
>               swap array[i] and array[storeIndex]
>               storeIndex := storeIndex + 1
>       swap array[storeIndex] and array[right] ''// Move pivot to its
> final place''
>       '''return''' storeIndex
>
> partitions the portion of the array between indexes ''left'' and
> ''right'', inclusively, by moving all elements less than or equal to
> <code>array[pivotIndex]</code> to the beginning of the subarray,
> leaving all the greater elements following them. In the process it
> also finds the final position for the pivot element, which it returns.
> It temporarily moves the pivot element to the end of the subarray, so
> it doesn't get in the way. Because it only uses exchanges, the final
> list has the same elements as the original list. Notice that an
> element may be exchanged multiple times before reaching its final
> place. It should also be noted that in case of pivot duplicates in the
> input array, they can be spread across left subarray, possibly in
> random order. This doesn't represent a partitioning failure, as
> further sorting will reposition and finally "glue" them together.
>
> writing quicksort itself is easy:
>
>   '''procedure''' quicksort(array, left, right)
>       '''if''' right > left
>           select a pivot index ''//(e.g. pivotIndex := left+(right-
> left)/2)''
>           pivotNewIndex := partition(array, left, right, pivotIndex)
>           quicksort(array, left, pivotNewIndex - 1)
>           quicksort(array, pivotNewIndex + 1, right)

So what are you trying to say?

Quicksort has been analyzed quite a lot (Knuth vol 3 is a fun place to
start). It is usually quite fast (n log n) but, with bad choices of
pivots or craftily constructed inputs can take n^2.

I have an emotional attachment to Heapsort, myself, but then, I am
also responding to this message, and I fired my therapist many years
ago.

Martin Cohen
From: MichaelW on 30 May 2010 19:31
On May 30, 12:00 pm, "Martin M. + I am right:if I am not tell me:or I
am right" <marty.musa...(a)gmail.com> wrote:
>  [[in-place]] partition algorithm and can achieve the complete sort
> using <math>O(\log n)</math> space (not counting the input) use on
> average (for the [[call stack]]):
>
>    '''function''' partition(array, left, right, pivotIndex)
>       pivotValue := array[pivotIndex]
>       swap array[pivotIndex] and array[right] ''// Move pivot to end''
>       storeIndex := left
>       '''for''' i ''' from ''' left '''to''' right - 1 ''// left ≤ i <
> right'' <!-- This comment is a must. Pseudo-code is ambiguous
> otherwise -->
>           '''if''' array[i] ≤ pivotValue
>               swap array[i] and array[storeIndex]
>               storeIndex := storeIndex + 1
>       swap array[storeIndex] and array[right] ''// Move pivot to its
> final place''
>       '''return''' storeIndex
>
> partitions the portion of the array between indexes ''left'' and
> ''right'', inclusively, by moving all elements less than or equal to
> <code>array[pivotIndex]</code> to the beginning of the subarray,
> leaving all the greater elements following them. In the process it
> also finds the final position for the pivot element, which it returns.
> It temporarily moves the pivot element to the end of the subarray, so
> it doesn't get in the way. Because it only uses exchanges, the final
> list has the same elements as the original list. Notice that an
> element may be exchanged multiple times before reaching its final
> place. It should also be noted that in case of pivot duplicates in the
> input array, they can be spread across left subarray, possibly in
> random order. This doesn't represent a partitioning failure, as
> further sorting will reposition and finally "glue" them together.
>
> writing quicksort itself is easy:
>
>   '''procedure''' quicksort(array, left, right)
>       '''if''' right > left
>           select a pivot index ''//(e.g. pivotIndex := left+(right-
> left)/2)''
>           pivotNewIndex := partition(array, left, right, pivotIndex)
>           quicksort(array, left, pivotNewIndex - 1)
>           quicksort(array, pivotNewIndex + 1, right)

Cut and paste from the wiki article on quicksort. The conclusion to be
drawn is that you have nothing meaningful to say.
 | 
Pages: 1
Prev: Question about Hugh Woodin's original proof of projective determinacy.
Next: New Anti-Cantor Attack