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[0], 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; }
Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty. |