Strand sort

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

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;
}