Strand sort

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

Pseudokód[editovat | editovat zdroj]

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[editovat | editovat zdroj]

  /// 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#[editovat | editovat zdroj]

 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[editovat | editovat zdroj]

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());
    while (i.hasNext())
    {
      E val = i.next();
      if (val.compareTo(sublist.getLast()) >= 0)
      {
        sublist.addLast(val);
        i.remove();
      }
    }
 
    if (!results.isEmpty())
    {
      ListIterator<E> li = results.listIterator();
      E current = li.next();
      while (!sublist.isEmpty())
      {
        if (sublist.getFirst().compareTo(current) < 0)
          li.add(sublist.removeFirst());
        else if (li.hasNext())
          current = li.next();
        else
          break;
      }
    }
    results.addAll(sublist);
  }
  return results;
}