Sıralama, bir dizinin elemanlarının aranabilirliğini arttırmak için belirli bir sıraya göre düzenlendiği temel bir işlemdir. Basit bir deyişle, veriler kolayca aranabilecek şekilde sıralanır.
Karşılaştırma Tablosu
| Karşılaştırma için temel | Ekleme Sıralaması | Seçim Sıralama |
|---|---|---|
| Temel | Veriler mevcut bir sıralanmış dosyaya eklenerek sıralanır. | Veriler ardışık elemanları seçilerek ve yerleştirilmiş konuma yerleştirilerek sıralanır. |
| Doğa | Kararlı | kararsız |
| İzlenecek süreç | Elementler önceden yerleştirilirken, yerleştirileceği yer aranır. | Öğeler aranırken, yer önceden bilinir. |
| Hemen veri | Ekleme sıralama, anında veriyle başa çıkabilen canlı sıralama tekniğidir. | Anında verilerle ilgilenemez, başlangıçta mevcut olması gerekir. |
| En iyi durum karmaşıklığı | O (n) | 0 (n 2 ) |
Ekleme Sıralamasının Tanımı
Ekleme sıralama, varolan düzenlenmiş dosyaya bir değer kümesi ekleyerek çalışır. Her seferinde tek bir eleman ekleyerek sıralanmış diziyi oluşturur. Bu işlem dizinin tamamı bir düzende sıralanıncaya kadar devam eder. Ekleme düzeninin arkasındaki ana kavram, her bir öğeyi nihai listedeki uygun yerine yerleştirmektir. Ekleme sıralama yöntemi etkili bir miktarda bellek tasarrufu sağlar.
Ekleme türünün çalışması
- Birinin sıralanan verileri ve diğerlerinin sıralanmamış verilerde depolandığı iki dizi dizisini kullanır.
- Sıralama algoritması, sıralanmamış kümede öğeler bulunana kadar çalışır.
- Dizideki 'n' sayı öğelerinin olduğunu varsayalım. Başlangıçta, dizin kümesinde 0 (LB = 0) olan öğe var. Kalan elemanlar listenin sıralanmamış bölümündedir.
- Sıralanmamış kısmın ilk elemanı dizi indeksi 1'e sahiptir (LB = 0 ise).
- Her yinelemeden sonra, sıralanmamış bölümün ilk elemanını seçer ve onu sıralanmış kümedeki uygun yere yerleştirir.
Ekleme türünün avantajları
- Küçük veri kümeleriyle kullanıldığında kolayca uygulanır ve çok verimlidir.
- Ekleme sıralama ek bellek alanı gereksinimi daha az (yani, O (1)).
- Yeni elemanlar alındığında liste sıralanabildiği için canlı sıralama tekniği olarak kabul edilir.
- Diğer sıralama algoritmalarından daha hızlıdır.
Örnek :
Seçim Sıralama Tanımı
Seçim sıralaması, minimum değer numarasını arayarak ve sırasına göre (artan veya azalan) ilk veya son konuma yerleştirerek sıralama yapar. Minimum anahtarın aranması ve uygun pozisyonda yerleştirilmesi işlemi, tüm elemanlar doğru pozisyona gelene kadar devam eder.
Seçim Sıralama Çalışması
- Bellekte N öğeleri olan bir ARR dizisi olduğunu varsayalım.
- İlk geçişte, en küçük anahtar konumu ile birlikte aranır, ardından ARR [POS], ARR [0] ile değiştirilir. Bu nedenle, ARR [0] sıralanır.
- İkinci geçişte, yine en küçük değerin konumu N-1 elemanlarının alt dizisinde belirlenir. ARR [POS] 'ı ARR [1] ile değiştirin.
- Geçiş N-1'de, N elementi sayısını sıralamak için aynı işlem yapılır.
Örnek :
Ekleme Sıralama ve Seçim Sıralama Arasındaki Temel Farklılıklar
- Ekleme sıralama genellikle ekleme işlemini gerçekleştirir. Aksine, seçim sıralama gerekli öğelerin seçimini ve konumlandırmasını gerçekleştirir.
- Seçim dizisinin kararlı bir algoritma olmadığı durumlarda ekleme diziliminin sabit olduğu söylenir.
- Ekleme sıralama algoritmasında, elemanlar önceden bilinir. Buna karşılık, seçim sıralama önceden konumu içerir.
- Ekleme sıralama, gelen öğelerin listede hemen sıralandığı, ancak sıralama seçiminin anında verilerle iyi çalışamadığı canlı bir sıralama tekniğidir.
- Ekleme sıralama en iyi durumda O (n) çalışma süresine sahiptir. Karşıt olarak, en iyi durum çalışma zamanı seçim sıralama karmaşıklığı O (n2) 'dir.
Ekleme türünün karmaşıklığı
Ekleme sıralama en iyi durumda karmaşıklığı, O (n) kez, yani dizi önceden sıralandığında. Aynı şekilde, dizi ters sırayla sıralandığında, sıralanmamış dizinin ilk elemanı sıralanan kümedeki her bir elemanla karşılaştırılmalıdır. Bu nedenle, en kötü durumda, Ekleme sıralama çalışma süresi ikinci derecedendir, yani O (n2) . Ortalama bir durumda aynı zamanda minimum (k-1) / 2 karşılaştırması yapmak zorundadır. Bu nedenle, ortalama bir durum ayrıca ikinci dereceden çalışma süresine sahiptir (n2).
Seçim Sıralamasının Karmaşıklığı
Seçim çalışması olarak, sıralama, dizideki öğelerin orijinal sırasına bağlı olmadığından, en iyi durum ile en iyi durum seçim karmaşıklığı arasında çok fazla bir fark yoktur.
Seçim sırası minimum değer öğesini seçer, seçim sürecinde tüm 'n' öğeleri taranır; bu nedenle ilk geçişte n-1 karşılaştırması yapılmıştır. Ardından, elemanlar birbirleriyle değiştirilir. Benzer şekilde, ikinci geçişte, en küçük ikinci elemanı bulmak için, kalan n-1 elemanlarının taranmasını istiyoruz ve tüm dizi sıralanana kadar işlem devam ediyor.
Bu nedenle, seçim sıralama çalışma süresi karmaşıklığı O (n2) 'dir .
= (n-1) + (n-2) + ……… .. + 2 + 1
= n (n-1) / 2 = 0 (n2)
Sonuç
Her iki sıralama algoritması arasında, ekleme sıralaması hızlı, verimli ve kararlıdır; seçim sıralaması ise yalnızca küçük öğeler kümesine dahil olduğunda veya liste kısmen önceden sıralandığında verimli bir şekilde çalışır. Seçim sırasına göre yapılan karşılaştırma sayısı, yapılan hareketlerden daha fazladır, oysa ekleme sıralamasında bir elemanın kaç kez hareket ettirildiği veya değiştirildiği, yapılan karşılaştırmalardan daha büyüktür.
