Module: (Python) İkinci dereceden sıralamalar


Problem

3 /7


Ekleme sıralaması

Theory Click to read/hide

Sıralama ekle

Ekleme sıralama (Ekleme sıralama) —  ;girdi dizisinin öğelerinin birer birer arandığı ve her yeni gelen öğenin daha önce sıralanan öğeler arasında uygun yere yerleştirildiği sıralama algoritması.


Sıralamayı ekle – çok basit ama verimsiz bir algoritmadır ve yine de genel olarak daha verimli birçok başka algoritma geliştirildikten sonra bile onu alakalı kılan birkaç özel avantaja sahiptir.

Araya eklemeli sıralamada, sıralamadan önce tüm dizinin ön planda olması gerekmez. Algoritma, sıralama sırasında her seferinde bir öğe alabilir. Bu sıralama sırasında daha fazla öğe eklememiz gerekirse çok kullanışlıdır. Algoritma, yeni öğeyi "yeniden çalıştırmadan" doğru yere yerleştirecek tüm diziyi sıralama.

Ekleme sıralaması, küçük (~10 öğeli) veri kümelerindeki verimliliği nedeniyle pratikte kullanılabilir.

Sorun şu ki: dizinin zaten sıralanmış bir kısmı var ve sırayı korurken dizinin geri kalan öğelerini sıralanan kısma eklemek istiyorsunuz. Bunu yapmak için, algoritmanın her adımında, giriş verisi öğelerinden birini seçeriz ve onu, tüm girdi veri seti sıralanana kadar dizinin zaten sıralanmış bölümünde istenen konuma yerleştiririz. Girdi dizisinden bir sonraki öğeyi seçme yöntemi isteğe bağlıdır, ancak genellikle (ve kararlı bir sıralama algoritması elde etmek için), öğeler girdi dizisindeki görünüm sırasına göre eklenir.

Bu algoritmanın algoritmik uygulaması
// Boş öğe zaten sıralanmış bir dizi olarak kabul edilir.
// Bu nedenle, döngü 1'den başlar
I=1 İLE N-1 İÇİN DÖNGÜ ADIM 1
   X=A[I]
   J=ben
   WHEN J>0 AND A[J-1]>X //eklenecek yer aranıyor
     DEĞİŞİM A[J],A[J-1]
     J=J-1
   Güle güle
   A[J]=X
 SONRAKİ ben
Hesaplama karmaşıklığı: \(\displaystyle O(n^{2})\).

Problem

Diziyi "inserts" yöntemini kullanarak azalan sırada sıralamak gerekir.

Giriş 
İlk satır, 1000'i aşmayan bir doğal sayı N içerir – dizi boyutu. İkinci satır sayıları N ayarlar – dizi öğeleri (mutlak değeri 1000'i geçmeyen tamsayılar).

Künye 
Ortaya çıkan dizinin çıktısını alın.
 
Örnek

# Girdi Çıktı
1 5
5 4 3 2 1
1 2 3 4 5