İ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(n2)'dir.
Örnek
- Sıralanacak dizinin üzerinden bir kere geçilir ve yükselen (sıralı) sayılar alınır.
- Sıralı olan alt dizi ilk yinelemenin ardından boş olan sıralanmış dizinin üstüne
konur.
- Ana dizinin üzerinden yeniden geçilir ve kendi içinde sıralı yeni bir alt dizi çıkarılır.
- Artık sıralanmış dizi boş olmadığından yeni çıkarılan alt dizi sıralanmış diziyle
birleştirilir.
- Alt dizi ve ana dizi boşalana kadar 3 ve 4üncü adımlar yinelenir.
|
Sıralanmamış dizi |
Alt dizi |
Sıralanmış dizi |
|
3 1 5 4 2 |
|
|
|
1 4 2 |
3 5 |
|
|
1 4 2 |
|
3 5 |
|
2 |
1 4 |
3 5 |
|
2 |
|
1 3 4 5 |
|
|
2 |
1 3 4 5 |
|
|
|
1 2 3 4 5 |
