İplik sıralaması

İplik sıralaması (İngilizcesi: Strand sort) bilgisayar bilimlerinde kullanılan bir sıralama algoritmasıdır. Sıralanacak olan dizinin, sıralanmış alt dizilerinin oluşturularak bu alt dizilerin birleştirilmesi yoluyla sonucun oluşturulması mantığına dayanır. Algoritmanın her bir aşamasında ana dizinin üzerinden geçilir ve bu diziden zaten sıralanmış olan bir dizi eleman çıkarılır. Çıkarılan bu eleman dizileri daha sonra birleştirilir.
Algoritmanın adı, sıralanacak dizinin içinden çıkan kendi içinde sıralanmış alt dizilerin ipliklere benzetilmesinden gelmektedir. İplik sıralaması algoritması, ana diziden ipleri çıkarırken ve oluşan sıralı ipleri birleştirirken karşılaştırma kullandığı için bir karşılaştırma sıralamasıdır.
İplik sıralaması algoritmasının karmaşıklığı ortalamada O(n log n)'dir. Sıralanacak dizinin zaten sıralı olduğu en iyi durumda algoritmanın karmaşıklığı O(n), sıralanacak dizinin tersten sıralı olduğu en kötü durumda ise algoritmanın karmaşıklığı O(n²)'dir.

Sözde Kodu

İplik sıralamasının yalın bir sözde kodu aşağıda verilmiştir:
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

C# ile uygulama

Aşağıdaki program iplik sıralamasının C# kullanılarak oluşturulmuş bir uygulamasıdır:

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

Java ile uygulama

Aşağıdaki program iplik sıralamasının Java kullanılarak oluşturulmuş bir uygulamasıdır:
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;}