>> [MÜZİK OYUN]
Doug LLOYD: Seçim sıralama is an Tahmin edebileceğiniz gibi, algoritma,
elemanlarının bir kümesini sıralar.
Ve algoritma hatırlama Bir adım-adım seti
Bir görevi tamamlamak için talimatları.
>> Seçimi sıralamak Temel fikir, bu
En küçük sıralanmamış elemanı bulmak ve sıralı listenin sonuna ekleyin.
Etkili bu ne inşa olduğunu Bir sıralanmış liste, bir defada bir unsur.
Pseudocode aşağı Breaking Bu algoritma devlet olabilir
aşağıdaki gibi, bu kadar tekrarlayın Hiçbir sıralanmamış unsurlar kalır.
Unsorted aracılığıyla arama Veri küçük değeri bulmak için,
daha sonra küçük değeri takas ayıklanmamış kısmının ilk elemanı.
>> Bu, bu görselleştirmek için yardımcı olabilir o yüzden bu bir göz atalım.
Yani bu, ben iddia, bir olduğunu sıralanmamış dizi ve ben ettik
Tüm belirten bunu gösterilir elementlerin, kırmızı renkli
Henüz sıralanır değil.
Bu, tüm bir Dizinin unsorted parçası.
>> Yani adımlarda gidelim Seçim sıralama bu diziyi sıralamak için.
Yani yine, biz olacak tekrarı konum Hiçbir sıralanmamış unsurlar kalmayıncaya kadar.
Biz aracılığıyla olacak aramayı sensin Veri küçük değeri bulmak için,
ve daha sonra bu değeri takas ayıklanmamış kısmının ilk elemanı.
>> Şu anda, yine tüm Dizi sıralanmamış bir parçasıdır.
Kırmızı unsurlar sıralanmamış bulunmaktadır.
Bu yüzden arama ve Biz en küçük değeri bulmak.
Biz, başından başla Biz sonuna kadar gidin
en küçük değer biridir bulabilirsiniz.
Yani o kısmı biri.
Ve sonra bölüm iki ile bu değeri takas ayıklanmamış kısmının ilk elemanı,
ya da ilk kırmızı unsur.
>> Bu durumda olacağını Beş, bu yüzden biz bir ve beş takas.
Bunu yaptığımızda, biz görsel biz ettik görüyoruz
küçük değerli eleman taşındı dizinin başından için.
Etkili o elemanı sıralama.
>> Ve böylece biz gerçekten teyit edebilir ve devlet tek olduğu, sıralanır.
Ve böylece biz sıralanmış kısmını işaret edeceğiz Bizim dizinin, mavi boyama yoluyla.
>> Şimdi biz sadece tekrar işlemi yineleyin.
Biz unsorted kısmından arama Dizi en küçük elemanı bulmak için.
Bu durumda, iki.
>> Biz ilk o takas sıralanmamış parçanın elemanı.
Bu durumda iki de olur ayıklanmamış kısmının ilk elemanı.
Bu yüzden kendisi ile iki takas, hangi gerçekten sadece iki yaprak
o ve o tür nereye.
Devam edersek, biz arama En küçük eleman bulmak için.
Üç bulunuyor.
Biz ilk ile takas beş elemanı.
Ve şimdi üç sıralanır.
>> Biz yine arama ve biz En küçük eleman dört bulmak.
Biz ilk elemanı ile takas sıralanmamış parçası ve şimdi dört sıralanır.
>> Biz beş olduğunu bulmak En küçük eleman.
Biz ilk ile takas sıralanmamış parçanın elemanı.
Ve şimdi beş sıralanır.
>> Ve sonra son olarak, bizim sıralanmamış bir parçası oluşur
Sadece tek bir eleman, bu yüzden arama
ve altı olduğunu bulmak En küçük ve aslında, sadece unsur.
Ve sonra biz sıralanır söyleyebiliriz.
Ve şimdi bizim dizi açık ettik Tamamen sıralanmamış engel
kırmızı, tamamen dizildi mavi, seçim sıralama kullanarak.
>> Yani en kötü durum senaryosu burada ne var?
Peki mutlak kötü olarak dava, biz bakmak zorundayız
dizinin elemanları tüm En küçük ayrımı yapılmamış diğer eleman bulmak,
ve biz tekrarlamak zorunda bu işlem, n kere.
Dizinin her elemanı için bir kez biz sadece, çünkü bu algoritmada,
zaman sıralama tek unsur.
>> En iyi senaryo nedir?
Peki, doğru aynı değil mi?
Biz aslında hala adım adım var Dizinin her elemanı
amacıyla, olduğunu onaylamak için Aslında, küçük elemanı.
>> Yani en kötü durum çalışma zamanı, biz bir süreç n defa tekrarlamak zorunda,
n elemanlarının her biri için bir kez.
Ve en iyi senaryo, Aynı yapmak zorundayız.
>> Yani geri düşünme bizim hesaplama karmaşıklığı araç,
Ne düşünüyorsunuz kötü Seçim sıralama için durum zamanı?
Sizce en iyi Seçim sıralama için durum zamanı?
>> N karesi arasında Big O tahmin mı, Big Omega n karesi?
Sen haklı olurdunuz.
Bu, aslında, En kötü durum ve en iyi durum çalıştırmak
Seçim sıralama zamanları.
>> Ben Doug Lloyd değilim.
Bu CS50 olduğunu.