[MÜZİK OYUN] 

Doug LLOYD: Yani ekleme sıralama başka bir şeydir Algoritma, biz bir dizi sıralamak için kullanabilirsiniz. Bu algoritma arkasındaki fikir senin sıralı dizi oluşturmaktır yerinde, takım elemanları değişen Eğer gitmek gibi yol, yer açmak için. Bu biraz farklıdır Seçim tür veya kabarcık sıralama, örneğin, nerede Biz yerleri ayarlama ediyoruz, nerede swapları yapıyoruz. 

Bu durumda ne aslında konum yapıyor sürgülü unsurlar üzerinde, yolumdan. Bu algoritma yapar nasıl pseudocode çalışır? Peki sadece keyfi olduğunu diyelim Dizinin ilk elemanı sıralanır. Biz bir yerde inşa ediyoruz. 

Biz olacak bir seferde bir eleman gidip konum ve onu inşa ve böylece ilk şey gördüğümüz Bir tek unsur dizidir. Ve tanımı gereği, bir eleman dizisi sıralanır. 

Sonra bu işlemi tekrarlayın edeceğiz until-- aşağıdaki işlemi tekrarlayın edeceğiz bütün elemanları kriteri kadar devam eder. Bir sonraki ayrımı yapılmamış diğer elemana bak ve Sıralanan kısmına takın, gerekli sayıda kaydırarak yolumdan elemanlarının. Umarım bu görselleştirme Eğer tam olarak ne olduğunu görmek yardımcı olacaktır Ekleme sıralama ile devam. 

Yani yine burada bulunuyor Tüm sıralanmamış dizi, elementlerin bütün kırmızı ile gösterilmiştir. Ve en takip edelim Bizim pseudocode adımlar. Yaptığımız ilk şey, biz diyoruz olduğunu dizinin ilk elemanı sıralanır. Yani biz öylece demek sensin Beş, artık sıralanmış ediyoruz. 

Sonra bir sonraki bakmak Dizinin sıralanmamış elemanı ve biz bunu eklemek istediğiniz kriteri bölümü içine, elemanları üzerinde kaydırarak. Yani iki sonraki sıralanmamış dizi elemanı. Açıkçası daha önce aittir Beş, bu yüzden biz ne yapacağız konum çeşit bir saniye kenara iki basılı tutun, üzerinde beş vardiya ve ardından iki takın Beş önce, nereye gitmeli için. Ve şimdi biz iki sıralanır söyleyebiliriz. 

Gördüğünüz gibi Yani, biz şimdiye kadar sadece ettik Dizinin iki unsur baktı. Biz bakmadım tüm dinlenmek, ama biz ettik Bu iki unsur sıralama kriteri var kaydırma mekanizması yolu. 

Bu yüzden tekrar işlemi yineleyin. Bir sonraki unsorted bak eleman, işte o. , Bir saniye kenara tutun Let üzerinde her şeyi vardiya ve bir tane koyun nereye gitmeli. 

Yine, halen, biz sadece hiç ettik bir, iki ve beş baktı. Biz geliyor başka ne bilmiyorum, ama biz bu üç unsuru sınıflandırılmaktadır ettik. 

Sonraki sıralanmamış elemanıdır Üç, bu yüzden bir kenara koyun olacak. Biz üzerinde kayma olacak ne hangi bu sefer gerekir Önceki gibi her şey değildir iki olgu, sadece beş. Ve sonra biz üç çakacağım, İki ile beş arasında. 

Altı unsorted yanındaki diziye eleman. Ve aslında altı yüzden, beşten büyüktür biz bile herhangi bir takas yapmak gerekmez. Biz sadece sağ için altı çakmak olabilir sıralanmış bölümünün sonu. 

Son olarak, dört olduğu Son sıralanmamış unsur. Yani biz bir kenara koyun edeceğiz, üzerinde kayması elementler biz üzerinde kaydırmaya gerek ait olduğu yere ve sonra dört koydu. Ve şimdi, bak biz bir çeşit ettik tüm elementlerin. Ekleme ile dikkat sıralama biz yoktu ileri ve geri dizi boyunca gitmek için. Biz sadece dizi boyunca gitti bir kez, ve biz bir şeyler değiştirdi biz zaten sipariş, karşılaşılan olacağımı yeni unsurlar yer açmak için. 

Peki kötü durumda bulunuyor Ekleme çeşit senaryo? En kötü durumda, Dizi tersten olduğunu. Sen n öğelerinin her değiştirmek zorunda n pozisyonlarına kadar her zaman biz Bir ekleme yapmak. Bu değişen bir sürü. 

En iyi durumda, Dizi mükemmel sıralanır. Ve çeşit ne gibi örnekte beş ve altı ile sadece onu tack nerede Herhangi bir vites yapmak zorunda kalmadan, biz aslında böyle yapardım. 

Bunu düşünürsek bizim Dizi, altıya kadar oldu Biz başlamak istiyorum biri ilan sıralanır. İki böylece biz sadece can birbiri ardına geliyor Bir ve iki sıralanır iyi, tamam, demek. Üç Tamam, sonra iki gelir bir ve iki ve üç sıralanır. 

Biz konum, herhangi bir swap yapma değil sadece bu keyfi hattı hareketli Biz giderken arasında sıralanır ve sıralanmamış. Gibi etkili biz örnekte olduğu gibi, biz ilerlerken, mavi unsurları dönüm. Yani en kötü durum zamanı daha sonra, ne var? Biz her vardiya varsa, Unutmayın n elemanları da N konumları, umarım bu size verir En kötü durumda olduğunu bir fikir Çalışma zamanı n Big O karesi olduğunu. 

Dizi mükemmel değilse sıralanmış, tüm yapmamız gereken her element bakmak olduğunu Bir kez, ve sonra biz bitirdik. Yani en iyi durumda, n omega var. 

Ben Doug Lloyd değilim. Bu CS50 olduğunu.