Help with name of sorting algorithm

[LwvfGNh0]

Hi all,

A question has arisen on an old exam paper used for revision which asks about a type of sorting that I cannot find the name of anywhere. Hopefully somebody here can help, please?

b. Produce an algorithm which will sort an array so that the largest items are on the ends and the smallest in the middle.
For example: [2,6,5,9,12] might become [12,6,2,5,9]

Thanks in advanced!

[keskiverto]

The most obvious thing is to first do a regular sort and then rearrange values.

[jonnin]

you can 'rotate' the array after a normal sort...

12345
-> 51234
keep 5 and 4, now operate on the middle:
123
-> 312
giving 53124 which is "a" correct result.


(technically, you operate on 123, keep 3 and 2, then operate on the 1, which is a base case, there are 2 base cases, one for even sized array, one for odd). You can do it recursively, or not, its really just a couple of swap statements and a front/back index/pointer tracking.

for your array that is (c is 12)

2,5,6,9,c
->
c 2 5 6 9
256
-> 625
----> c 6 2 5 9 //same answer you got.

[JLBorges]

Selection sort (variant):

// selection sort (requires mutable bidirectional iterator)
template< typename ITERATOR > void winding_sort( ITERATOR begin, ITERATOR end )
{
    if( std::distance(begin,end) > 1 )
    {
        std::iter_swap( begin, std::max_element( begin, end ) ) ;
        auto last = end ;
        std::iter_swap( --last, std::max_element( ++begin, end ) ) ;
        winding_sort( begin, last ) ;
    }
}

template< typename SEQUENCE > void winding_sort( SEQUENCE& seq )
{ winding_sort( std::begin(seq), std::end(seq) ) ; }

http://coliru.stacked-crooked.com/a/2e7b60ad5ee069a3

[Duthomhas]

I like the name 'winding', but the sort you are looking at is a variant of a 'cocktail sort', as in 'cocktail shaker'.

The underlying algorithm is not fixed: it is usually either a bubble sort or a selection sort, but can be anything that is convenient to make bi-directional.

Hope this helps.