Ekleme sıralama - Insertion sort

Ekleme sıralama
Ekleme sort.gif
Ekleme sıralama animasyonu
Sınıf sıralama algoritması
Veri yapısı Dizi
En kötü durum performansı karşılaştırmalar ve takaslar
En iyi durum performansı karşılaştırmalar, takaslar
Ortalama performans karşılaştırmalar ve takaslar
En kötü durum alanı karmaşıklığı toplam, yardımcı

Ekleme sıralama , son sıralı diziyi (veya listeyi) her seferinde bir öğe oluşturan basit bir sıralama algoritmasıdır . Büyük listelerde hızlı sıralama , yığın sıralama veya birleştirme sıralama gibi daha gelişmiş algoritmalardan çok daha az verimlidir . Bununla birlikte, eklemeli sıralama çeşitli avantajlar sağlar:

  • Basit uygulama: Jon Bentley , üç satırlı bir C versiyonu ve beş satırlı optimize edilmiş bir versiyon gösterir
  • Diğer ikinci dereceden sıralama algoritmaları gibi (oldukça) küçük veri kümeleri için verimli
  • Pratikte , seçim sıralama veya kabarcık sıralama gibi diğer birçok basit ikinci dereceden (yani, O ( n 2 )) algoritmalardan daha verimlidir.
  • Adaptif , yani daha önce esas olarak sıralanır veri setleri için verimli: zaman karmaşıklığı olan O ( kn ) girişi, her eleman daha uzun olduğunda k uzaklıkta sıralanmış konumundan yer
  • kararlı ; yani, eşit anahtarlara sahip öğelerin göreli sırasını değiştirmez
  • yerinde ; yani, yalnızca sabit miktarda O(1) ek bellek alanı gerektirir
  • çevrimiçi ; yani, bir listeyi aldığı gibi sıralayabilir

İnsanlar bir köprü elinde kartları manuel olarak sıralarken , çoğu eklemeli sıralamaya benzer bir yöntem kullanır.

algoritma

Ekleme sıralamanın grafik bir örneği. Kısmi sıralı liste (siyah) başlangıçta listedeki yalnızca ilk öğeyi içerir. Her yinelemede bir öğe (kırmızı) "henüz sipariş için kontrol edilmedi" giriş verilerinden çıkarılır ve sıralanmış listeye yerinde eklenir.

Ekleme sıralama yinelenir , her tekrarda bir girdi öğesi tüketir ve sıralanmış bir çıktı listesi oluşturur. Her yinelemede, eklemeli sıralama, girdi verisinden bir öğeyi kaldırır, sıralanmış listede ait olduğu konumu bulur ve oraya ekler. Hiçbir girdi öğesi kalmayana kadar tekrarlanır.

Sıralama, tipik olarak, diziyi yineleyerek ve arkasındaki sıralı listeyi büyüterek yerinde yapılır. Her dizi konumunda, oradaki değeri, sıralanmış listedeki en büyük değere karşı kontrol eder (bu, kontrol edilen önceki dizi konumunda onun yanında olur). Daha büyükse, öğeyi yerinde bırakır ve bir sonrakine geçer. Daha küçükse, sıralanan listede doğru konumu bulur, bir boşluk oluşturmak için tüm büyük değerleri yukarı kaydırır ve bu doğru konuma ekler.

k yinelemeden sonra elde edilen dizi , ilk k + 1 girişlerinin sıralandığı (ilk giriş atlandığından "+1") özelliğine sahiptir. Her yinelemede, girdinin kalan ilk girişi kaldırılır ve sonuca doğru konumda eklenir, böylece sonuç genişletilir:

x'in eklenmesinden önceki dizi

olur

x eklendikten sonra dizi

göre her eleman daha sonra ile x sağ kopyalanan bu karşılaştırılır olarak x .

Diziler üzerinde çalışan en yaygın eklemeli sıralama türü şu şekilde tanımlanabilir:

  1. Bir dizinin başlangıcında sıralanmış bir diziye bir değer eklemek için tasarlanmış Insert adlı bir işlev olduğunu varsayalım . Dizinin sonundan başlayarak ve yeni eleman için uygun bir pozisyon bulunana kadar her elemanı bir yer sağa kaydırarak çalışır. İşlevin, dizideki sıralanan diziden hemen sonra depolanan değerin üzerine yazma yan etkisi vardır.
  2. Bir eklemeli sıralama gerçekleştirmek için dizinin en soldaki öğesinden başlayın ve karşılaşılan her öğeyi doğru konumuna eklemek için Ekle'yi çağırın . Elemanın eklendiği sıralı dizi, daha önce incelenen indeksler kümesinde dizinin başında saklanır. Her ekleme, tek bir değerin üzerine yazar: eklenen değer.

Dizilerin sıfır tabanlı olduğu tam algoritmanın sözde kodu aşağıdaki gibidir : 

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

Dış döngü, ilki hariç tüm öğeler üzerinde çalışır, çünkü tek öğeli önek A[0:1]önemsiz bir şekilde sıralanır, bu nedenle ilk girişlerin sıralandığı değişmezii baştan doğrudur. İç döngü, öğeyi A[i]doğru yerine taşır , böylece döngüden sonra ilk i+1öğeler sıralanır. andTestteki -operatörünün kısa devre değerlendirmesi kullanması gerektiğini unutmayın , aksi takdirde test , değerlendirmeye çalıştığında bir dizi sınırları hatasıyla sonuçlanabilir (yani erişim başarısız olur). j=0A[j-1] > A[j]A[-1]

swapİşlemi yerinde x ← A[j]; A[j] ← A[j-1]; A[j-1] ← x( xgeçici bir değişken olan) olarak genişlettikten sonra A[i], konumuna tek seferde hareket eden ve iç döngü gövdesinde yalnızca bir atama gerçekleştiren biraz daha hızlı bir sürüm üretilebilir : 

i ← 1
while i < length(A)
    x ← A[i]
    j ← i - 1
    while j >= 0 and A[j] > x
        A[j+1] ← A[j]
        j ← j - 1
    end while
    A[j+1] ← x
    i ← i + 1
end while

Yeni iç döngü, öğeleri için bir noktayı temizlemek için sağa kaydırır x = A[i].

Algoritma özyinelemeli bir şekilde de uygulanabilir. Özyineleme sadece dış döngünün yerini alır, kendini çağırır ve n'nin 0'a eşit olduğu kadar ardışık olarak daha küçük n değerlerini yığında saklar , burada işlev daha sonra n'ye eşit 1 ile başlayan her özyinelemeli çağrıdan sonra kodu yürütmek için çağrı zincirini döndürür. n , işlevin her bir örneği önceki örneğe döndüğünde 1 artar. İlk çağrı insertionSortR(A, length(A)-1) olacaktır . 

function insertionSortR(array A, int n)
    if n > 0
        insertionSortR(A, n-1)
        x ← A[n]
        j ← n-1
        while j >= 0 and A[j] > x
            A[j+1] ← A[j]
            j ← j-1
        end while
        A[j+1] ← x
    end if
end function

Kodu kısaltmaz, aynı zamanda yürütme süresini de azaltmaz, ancak ek bellek tüketimini O(1)' den O(N)'ye yükseltir (en derin özyineleme düzeyinde yığın, N referansını içerir) Adizi, her biri N'den 1'e nkadar eşlik eden değişken değerine sahip .

En iyi, en kötü ve ortalama durumlar

En iyi durum girişi, zaten sıralanmış bir dizidir. Bu durumda, eklemeli sıralamanın doğrusal bir çalışma süresi vardır (yani, O( n )). Her yineleme sırasında, girdinin kalan ilk öğesi yalnızca dizinin sıralanmış alt bölümünün en sağdaki öğesiyle karşılaştırılır.

En basit en kötü durum girişi, ters sırada sıralanmış bir dizidir. Tüm en kötü durum girdileri kümesi, her öğenin kendisinden önceki öğelerin en küçüğü veya ikinci en küçük olduğu tüm dizilerden oluşur. Bu durumlarda, iç döngünün her yinelemesi, bir sonraki öğeyi eklemeden önce dizinin tüm sıralanmış alt bölümünü tarayacak ve kaydıracaktır. Bu, eklemeli sıralamaya ikinci dereceden bir çalışma süresi verir (yani, O( n 2 )).

Ortalama durum da ikinci derecedendir, bu da eklemeli sıralamayı büyük dizileri sıralamak için kullanışsız hale getirir. Bununla birlikte, ekleme sıralama çok küçük diziler sıralamak için en hızlı algoritmaların biri daha hızlı daha hızlı sıralama ; aslında, iyi hızlı sıralama uygulamaları, alt problemler olarak ortaya çıktığında da belirli bir eşikten daha küçük diziler için eklemeli sıralama kullanır; kesin eşik deneysel olarak belirlenmelidir ve makineye bağlıdır, ancak genellikle on civarındadır.

Örnek: Aşağıdaki tablo {3, 7, 4, 9, 5, 2, 6, 1} dizisini sıralama adımlarını göstermektedir. Her adımda, incelenen anahtarın altı çizilir. Önceki adımda taşınan (veya henüz dikkate alınan en büyük anahtar olduğu için yerinde bırakılan) anahtar bir yıldızla işaretlenmiştir. 

3  7  4  9  5  2  6  1
3* 7  4  9  5  2  6  1
3  7* 4  9  5  2  6  1
3  4* 7  9  5  2  6  1
3  4  7  9* 5  2  6  1
3  4  5* 7  9  2  6  1
2* 3  4  5  7  9  6  1
2  3  4  5  6* 7  9  1
1* 2  3  4  5  6  7  9

Diğer sıralama algoritmalarıyla ilişkisi

Ekleme sıralama, seçim sıralamaya çok benzer . Seçim sıralamasında olduğu gibi, k diziden geçtikten sonra , ilk k eleman sıralanmış sıradadır. Bununla birlikte, iki algoritma arasındaki temel fark, seçmeli sıralama ileriye doğru tarama yaparken, eklemeli sıralama geçerli anahtardan geriye doğru tarama yapmasıdır. Seçimdeki Bu sonuçlar tür ilk k elemanlar yapma k yerleştirme sıralama onlar sadece ilk iken, sıralanmamış giriş küçük elemanları k girişinin unsurları.

Eklemeli sıralamanın seçimli sıralamaya göre birincil avantajı, seçimli sıralamanın her zaman listenin sıralanmamış kısmındaki mutlak en küçük öğeyi bulmak için kalan tüm öğeleri taraması gerektiğidir, buna karşın eklemeli sıralama, ( k  + 1)-st olduğunda yalnızca tek bir karşılaştırma gerektirir. eleman, k -inci elemandan daha büyüktür ; bu genellikle doğru olduğunda (örneğin, giriş dizisi zaten sıralanmış veya kısmen sıralanmışsa), eklemeli sıralama, seçimli sıralamaya kıyasla belirgin şekilde daha verimlidir. Ortalama olarak (( k  + 1)-st öğe sıralamasının rastgele olduğu varsayılırsa), araya eklemeli sıralama, önceki k elemanın yarısını karşılaştırmayı ve kaydırmayı gerektirir ; ortalama.

Ekleme sıralama için en kötü durumda (giriş dizisi ters sıralandığında), ekleme sıralama, seçim sıralama kadar çok karşılaştırma gerçekleştirir. Bununla birlikte, eklemeli sıralamanın seçmeli sıralamaya göre bir dezavantajı, her yinelemede ( k  + 1)-st öğesini dizinin sıralanmış kısmına yerleştirmenin tüm öğeleri kaydırmak için birçok öğe takası gerektirmesi nedeniyle daha fazla yazma gerektirmesidir. seçim sıralamasının her yinelemesi için yalnızca tek bir takas gereklidir. Genel olarak, eklemeli sıralama diziye O( n 2 ) kez yazarken, seçmeli sıralama yalnızca O( n ) kez yazar. Bu nedenle, EEPROM veya flash bellek gibi belleğe yazmanın okumaya göre çok daha pahalı olduğu durumlarda seçimli sıralama tercih edilebilir .

Quicksort ve mergesort gibi bazı böl ve yönet algoritmaları daha büyük diziler için ekleme sıralamadan daha iyi performans gösterirken, ekleme sıralama veya seçim sıralama gibi yinelemeli olmayan sıralama algoritmaları genellikle çok küçük diziler için daha hızlıdır (tam boyut ortama ve uygulamaya göre değişir, ancak tipik olarak 7 ila 50 element arasındadır). Bu nedenle, bu algoritmaların uygulanmasında yararlı bir optimizasyon, dizi küçük bir boyuta bölündüğünde daha basit algoritmayı kullanan hibrit bir yaklaşımdır.

Varyantlar

DL Shell , algoritmada önemli iyileştirmeler yaptı; değiştirilen sürüme Shell sort adı verilir . Sıralama algoritması, her geçişte azalan bir mesafeyle ayrılan öğeleri karşılaştırır. Kabuk sıralama, O( n 3/2 ) ve O( n 4/3 ) çalışma süresi gerektiren iki basit varyantla, pratik çalışmada çalışma sürelerini belirgin şekilde iyileştirdi .

Karşılaştırmaların maliyeti, örneğin referans yoluyla veya insan etkileşimiyle (yan yana görüntülenen bir çiftten birini seçmek gibi) saklanan dize anahtarlarında olduğu gibi, takas maliyetini aşarsa, ikili eklemeli sıralama kullanmak sonuç verebilir. daha iyi performans. İkili eklemeli sıralama , yeni öğeleri eklemek için doğru konumu belirlemek için ikili bir arama kullanır ve bu nedenle en kötü durumda ⌈log 2  n ⌉ karşılaştırmaları gerçekleştirir . Dizideki her eleman arandığında ve eklendiğinde bu O( n  log  n ) olur. Algoritmanın bir bütün olarak , her ekleme için gereken takas serisi nedeniyle ortalama olarak hala çalışma süresi O( n 2 ) vardır.

Takas sayısı, birden fazla öğenin konumunu, onları taşımadan önce hesaplayarak azaltılabilir. Örneğin, iki öğenin hedef konumu, uygun konuma taşınmadan önce hesaplanırsa, rastgele veriler için takas sayısı yaklaşık %25 oranında azaltılabilir. Aşırı durumda, bu değişken birleştirme sıralamaya benzer şekilde çalışır .

İkili birleştirme sıralaması adlı bir değişken , 32 öğeden oluşan grupları sıralamak için bir ikili eklemeli sıralama kullanır , ardından birleştirme sıralaması kullanılarak bir son sıralama kullanılır . Küçük veri kümelerinde ekleme sıralama hızı ile büyük veri kümelerinde birleştirme sıralama hızını birleştirir.

Her ekleme için bir dizi takas yapmaktan kaçınmak için, girdi , listedeki konum bilindiğinde öğelerin sabit bir zamanda listeye eklenmesine veya listeden çıkarılmasına izin veren bağlantılı bir listede saklanabilir . Bununla birlikte, bağlantılı bir listeyi aramak, istenen konuma giden bağlantıları sırayla takip etmeyi gerektirir: bağlantılı bir listenin rastgele erişimi yoktur, bu nedenle ikili arama gibi daha hızlı bir yöntem kullanamaz. Bu nedenle, arama için gereken çalışma süresi O( n ) ve sıralama için gereken süre O( n 2 )'dir. Daha karmaşık bir veri yapısı (örneğin, yığın veya ikili ağaç ) kullanılıyorsa, arama ve ekleme için gereken süre önemli ölçüde azaltılabilir; yığın sıralama ve ikili ağaç sıralamanın özü budur .

2006'da Bender, Martin Farach-Colton ve Mosteiro , dizi boyunca yayılmış az sayıda kullanılmayan alan (yani "boşluklar") bırakan kitaplık sıralama veya boşluklu ekleme sıralama adı verilen yeni bir ekleme sıralama türü yayınladı . Avantajı, eklemelerin yalnızca bir boşluğa ulaşılana kadar öğeleri kaydırmaya ihtiyaç duymasıdır. Yazarlar, bu sıralama algoritmasının O( n  log  n ) zamanında yüksek olasılıkla çalıştığını göstermektedir .

Bir atlama listesi kullanılıyorsa, ekleme süresi O(log n ) değerine düşürülür  ve atlama listesi bağlantılı bir liste yapısında uygulandığından takaslara gerek yoktur. Ekleme için son çalıştırma süresi O( n  log  n ) olacaktır.

Liste eklemeli sıralama , eklemeli sıralamanın bir çeşididir. Hareket sayısını azaltır.

C'deki ekleme sıralama kodunu listeleyin

Öğeler bağlantılı bir listede saklanıyorsa, liste O(1) ek boşlukla sıralanabilir. Algoritma, başlangıçta boş (ve dolayısıyla önemsiz şekilde sıralanmış) bir listeyle başlar. Girilen öğeler birer birer listeden çıkarılır ve ardından sıralanan listede uygun yere eklenir. Giriş listesi boş olduğunda, sıralanan liste istenen sonucu verir. 

struct LIST * SortList1(struct LIST * pList) 
{
    // zero or one element in list
    if (pList == NULL || pList->pNext == NULL)
        return pList;
    // head is the first element of resulting sorted list
    struct LIST * head = NULL;
    while (pList != NULL) {
        struct LIST * current = pList;
        pList = pList->pNext;
        if (head == NULL || current->iValue < head->iValue) {
            // insert into the head of the sorted list
            // or as the first element into an empty sorted list
            current->pNext = head;
            head = current;
        } else {
            // insert current element into proper position in non-empty sorted list
            struct LIST * p = head;
            while (p != NULL) {
                if (p->pNext == NULL || // last element of the sorted list
                    current->iValue < p->pNext->iValue) // middle of the list
                {
                    // insert into middle of the sorted list or as the last element
                    current->pNext = p->pNext;
                    p->pNext = current;
                    break; // done
                }
                p = p->pNext;
            }
        }
    }
    return head;
}

Aşağıdaki algoritma, sıralanmış listeye ekleme için bir takip eden işaretçi kullanır. Daha basit bir özyinelemeli yöntem, listeyi her seferinde (birleştirme yerine) yeniden oluşturur ve O( n ) yığın alanını kullanabilir. 

struct LIST
{
  struct LIST * pNext;
  int           iValue;
};

struct LIST * SortList(struct LIST * pList)
{
  // zero or one element in list
  if (!pList || !pList->pNext)
      return pList;

  /* build up the sorted array from the empty list */
  struct LIST * pSorted = NULL;

  /* take items off the input list one by one until empty */
  while (pList != NULL) {
      /* remember the head */
      struct LIST *   pHead  = pList;
      /* trailing pointer for efficient splice */
      struct LIST ** ppTrail = &pSorted;

      /* pop head off list */
      pList = pList->pNext;

      /* splice head into sorted list at proper place */
      while (!(*ppTrail == NULL || pHead->iValue < (*ppTrail)->iValue)) { /* does head belong here? */
          /* no - continue down the list */
          ppTrail = &(*ppTrail)->pNext;
      }

      pHead->pNext = *ppTrail;
      *ppTrail = pHead;
  }

  return pSorted;
}

Referanslar

daha fazla okuma

Dış bağlantılar