İçindekiler[Saklamak][Göstermek]
Bilgisayar bilimi, algoritmaların ve veri yapılarının karmaşıklığını anlamakla ilgilidir.
Sıralanması gereken bir öğe listeniz var, ancak daha karmaşık bir sıralama algoritması kullanmak için zamanınız veya kaynağınız yok.
Ekleme sıralama, en basit sıralama algoritmalarından biridir, ancak büyük listeler için yavaş olabilir.
Kolay uygulama ve anlama, bu yöntemi programcılar arasında favori haline getirdi. Küçük listeler için veya hızlı bir çözüme ihtiyacınız olduğunda mükemmeldir.
Bu blog yazısında, eklemeli sıralamanın zaman karmaşıklığına bakacağız. Bu algoritma dizileri sıralamak için kullanılır ve O(n) çalışma süresine sahiptir.2). Bu, dizinin boyutuyla birlikte zaman karmaşıklığının arttığı anlamına gelir.
Ancak, bu algoritma genellikle hızlı sıralama gibi diğer sıralama algoritmalarından daha hızlı olabilir.
Eklemeli sıralamanın nasıl çalıştığına daha yakından bakalım!
Ekleme Sıralama Algoritması Nedir?
Her seferinde bir öğe, eklemeli sıralama, sıklıkla liste olarak adlandırılan sıralanabilir bir dizi oluşturur.
Örneğin, sıralama, programın yorumlanması için belirteçlerin sırasının önemli olduğu derleyiciler gibi karmaşık bilgisayar programlarında uygulanır.
Ekleme Sıralaması Nasıl Çalışır?
Bir diziyi sıralamak için eklemeli sıralama kullandığımızda, algoritma listedeki en küçük öğeyi bulup doğru konuma ekleyerek başlar.
Ardından bir sonraki en küçük öğeyi bulur ve onu doğru konuma yerleştirir, vb.
Algoritma, listede dolaşarak, her öğeyi kendisinden önce gelenle karşılaştırarak çalışır.
Öğeler yanlış sıradaysa, algoritma bunları değiştirir. Ardından listenin sıralanıp sıralanmadığını kontrol eder ve sıralanmışsa algoritma sona erer.
Uygulamada, eklemeli sıralama genellikle birkaç satır kod kullanılarak uygulanır ve bu da onu küçük dizileri sıralamak için popüler bir seçim haline getirir. Ancak bu algoritmayı kullanırken zaman karmaşıklığı göz önünde bulundurulmalıdır.
Örnek:
Burada, araya eklemeli sıralamanın nasıl çalıştığına dair bir örnek verilmiştir. Aşağıdaki diziyi kullanacağız:
1, 2, 3, 4, 5, 6
Algoritma, listedeki 1 olan en küçük öğeyi bularak başlar. Ardından onu doğru konuma, ilk konuma yerleştirir. Daha sonra bir sonraki en küçük öğe olan 2'yi bulur. Onu ikinci konum olan doğru konuma yerleştirir.
Daha sonra bir sonraki en küçük öğe olan 3'ü bulur. Onu üçüncü konum olan doğru konuma yerleştirir.
Daha sonra 4 olan bir sonraki en küçük öğeyi bulur. Onu dördüncü konum olan doğru konuma yerleştirir ve bu şekilde devam eder. Liste şimdi sıralandı!
Algoritmanın listeyi sıralamak için altı karşılaştırma ve takas aldığını örnekten görebiliriz. Bunun nedeni n almasıdır.2 n öğelik bir listeyi sıralamak için karşılaştırmalar ve takaslar. Bu durumda, n=6.
Ekleme Sıralama Zamanı Karmaşıklığı Nasıl İyileştirilir?
Ekleme sıralamanın çalışma zamanı O(n) iken2), hızlı sıralama gibi daha iyi bir sıralama algoritması kullanılarak geliştirilebilir.
Quicksort'un O(n log n) çalışma zamanı vardır ve bu, O(n)'den çok daha hızlıdır.2).
Ancak, bazı durumlarda araya ekleme sıralama hızlı sıralamadan daha hızlı olabilir.
Örneğin, liste zaten sıralıysa, araya girerek sıralama hızlı sıralamadan daha kısa sürer.
Uygulamada, eklemeli sıralama genellikle birkaç satır kod kullanılarak uygulanır ve bu da onu küçük dizileri sıralamak için popüler bir seçim haline getirir.
Ancak bu algoritmayı kullanırken zaman karmaşıklığı göz önünde bulundurulmalıdır.
Zaman Karmaşıklıkları
En Kötü Durum Karmaşıklığı O(n2):
Dizinin boyutu ile zaman karmaşıklığı artar. n sürer2 n öğelik bir listeyi sıralamak için karşılaştırmalar ve takaslar.
Örneğin, 1000 boyutlu bir dizimiz varsa, algoritma diziyi sıralamak için 1,000,000 karşılaştırma ve takas alacaktır.
En İyi Vaka Karmaşıklığı O(n):
Zaman karmaşıklığı, giriş dizisinin boyutuyla aynıdır. i
t, n öğeden oluşan bir listeyi sıralamak için n karşılaştırma ve takas alır. Örneğin, 5 boyutunda bir dizi düşünün. Algoritma, diziyi sıralamak için beş karşılaştırma ve takas alacaktır.
Ortalama Vaka Karmaşıklığı O(n2):
Zaman karmaşıklığı, bu durumda en kötü ve en iyi durum karmaşıklıkları arasındadır.
n sürer2 n öğelik bir listeyi sıralamak için karşılaştırmalar ve takaslar.
Bu nedenle, eklemeli sıralama, kararlı bir sıralama algoritmasıdır.
Ekleme Sıralaması Neden Kararlı?
Girdi dizisindeki eşit öğelerin sırasını koruduğu için eklemeli sıralama sabittir.
Bu, veri alma veya finansal analiz gibi birçok uygulama için önemlidir. Örneğin, iki sayı listemiz varsa ve bunları karşılaştırmak istiyorsak, öğelerin sırasının korunduğundan emin olmamız gerekir.
Listeler sıralanmamışsa, onları doğru bir şekilde karşılaştırmayacağız.
Yorum bırak