Sıralama Algoritmaları |
10-29-2012 | #16 |
Prof. Dr. Sinsi
|
Sıralama Algoritmalarıİ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 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 Uygulama Örnekleri 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 (arrayCount != 0) { sublistClear(); sublistAddLast(arrayFirstValue); arrayRemoveFirst(); LinkedListNode<int> i = arrayFirst; while (i != null) { if(iValue >= sublistLastValue) { sublistAddLast(iValue); LinkedListNode<int> temp = i; i = iNext; arrayRemove(temp); } else { i = iNext; } } i = resultsFirst; while (sublistCount != 0) { if (i == null) { resultsAddLast(sublistFirstValue); sublistRemoveFirst(); } else if (sublistFirstValue < iValue) { resultsAddBefore(i, sublistFirstValue); sublistRemoveFirst(); } else { i = iNext; } } } 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 (!collisEmpty()) { LinkedList<E> sublist = new LinkedList<E>(); Iterator<E> i = colliterator(); sublistaddLast(inext()); while (ihasNext()) { E val = inext(); if (valcompareTo(sublistgetLast()) >= 0) { sublistaddLast(val); iremove(); } } if (!resultsisEmpty()) { ListIterator<E> li = resultslistIterator(); E current = linext(); while (!sublistisEmpty()) { if (sublistgetFirst()compareTo(current) < 0) liadd(sublistremoveFirst()); else if (lihasNext()) current = linext(); else break; } } resultsaddAll(sublist); } return results; } |
Sıralama Algoritmaları |
10-29-2012 | #17 |
Prof. Dr. Sinsi
|
Sıralama Algoritmalarıİçgözlemle sıralama İçgözlemle sıralama 1997 yılında David Musser tarafından tasarlanmış bir sıralama algoritmasıdır Algoritma verilen bir diziyi sıralamaya hızlı sıralama algoritmasıyla başlar ancak özyineleme derinliği önceden belirlenen bir değeri aştığında yığın sıralamasına döner İki algoritmanın iyi yönlerini birleştiren içgözlemle sıralama algoritmasının karmaşıklığı en kötü durumda O(n log n)'dir Olağan veri yükleri üzerinde kullanıldığında başarımı hızlı sıralamanın başarımına yakındır Kullandığı iki algoritma karşılaştırma ile sıraladığından içgözlemle sıralama da karşılaştırma ile sıralayan bir algoritma olarak sınıflandırılır |
Sıralama Algoritmaları |
10-29-2012 | #18 |
Prof. Dr. Sinsi
|
Sıralama Algoritmalarıİçgözlemle sıralama İçgözlemle sıralama 1997 yılında David Musser tarafından tasarlanmış bir sıralama algoritmasıdır Algoritma verilen bir diziyi sıralamaya hızlı sıralama algoritmasıyla başlar ancak özyineleme derinliği önceden belirlenen bir değeri aştığında yığın sıralamasına döner İki algoritmanın iyi yönlerini birleştiren içgözlemle sıralama algoritmasının karmaşıklığı en kötü durumda O(n log n)'dir Olağan veri yükleri üzerinde kullanıldığında başarımı hızlı sıralamanın başarımına yakındır Kullandığı iki algoritma karşılaştırma ile sıraladığından içgözlemle sıralama da karşılaştırma ile sıralayan bir algoritma olarak sınıflandırılır |
|