Strand sort

Strand sort je řadicí algoritmus, jenž má asymptotickou složitost v lepším případě O(n) a v horším O(n2).

Zdrojový kód

Pseudokód procedure strandSort( A : list of sortable items ) defined as: while length( A ) > 0 clear sublist sublist[ 0 ] := A[ 0 ] remove A[ 0 ] for each i in 0 to length( A ) do: if A[ i ] > sublist[ last ] then append A[ i ] to sublist remove A[ i ] end if end for merge sublist into results end while return results end procedure

V jazyce C /// param nums - input - array of values to be sorted /// param size - input - number of elements in the array void counting_sort(int *nums, int size) { // search for the minimum and maximum values in the input int i, min = nums, max = min; for(i = 1; i < size; ++i)

if (nums[i] < min) min = nums[i]; else if (nums[i] > max) max = nums[i];

// create a counting array, counts, with a member for // each possible discrete value in the input. // initialize all counts to 0. int distinct_element_count = max - min + 1; int* counts = new int[distinct_element_count]; for(i=0; i<distinct_element_count; ++i) counts[i] = 0;

// accumulate the counts - the result is that counts will hold // the offset into the sorted array for the value associated with that index for(i=0; i<size; ++i) ++counts[ nums[i] - min ];

// store the elements in the array int j=0; for(i=min; i<=max; i++) for(int z=0; z<counts[i-min]; z++) nums[j++] = i;

delete[] counts; }

V jazyce C# public static LinkedList<int> sort(LinkedList<int> array) { LinkedList<int> results = new LinkedList<int>(); LinkedList<int> sublist = new LinkedList<int>(); while (array.Count != 0)

sublist.Clear(); sublist.AddLast(array.First.Value); array.RemoveFirst(); LinkedListNode<int> i = array.First; while (i != null)

if(i.Value >= sublist.Last.Value)

sublist.AddLast(i.Value); LinkedListNode<int> temp = i; i = i.Next; array.Remove(temp);

else

i = i.Next;

i = results.First; while (sublist.Count != 0)

if (i == null)

results.AddLast(sublist.First.Value); sublist.RemoveFirst();

else if (sublist.First.Value < i.Value)

results.AddBefore(i, sublist.First.Value); sublist.RemoveFirst();

else

i = i.Next;

return results; }

V jazyce Java public static <E extends Comparable<? super E>> List<E> sort(Collection<E> coll) { List<E> results = new LinkedList<E>();

while (!coll.isEmpty())

LinkedList<E> sublist = new LinkedList<E>(); Iterator<E> i = coll.iterator(); sublist.addLast(i.next()); i.remove(); while (i.hasNext())

E val = i.next(); if (val.compareTo(sublist.getLast()) >= 0)

sublist.addLast(val); i.remove();

if (!results.isEmpty())

int pos = 0; while (!sublist.isEmpty())

if (sublist.getFirst().compareTo(results.get(pos)) < 0) results.add(pos++, sublist.removeFirst()); else if (pos < results.size()) pos++; else break;

results.addAll(sublist);

return results; }

Kategorie:Řadicí algoritmy