1
00:00:00,000 --> 00:00:05,726
>> [MÜZİK OYUN]

2
00:00:05,726 --> 00:00:08,600
Doug LLOYD: Seçim sıralama is an
Tahmin edebileceğiniz gibi, algoritma,

3
00:00:08,600 --> 00:00:10,470
elemanlarının bir kümesini sıralar.

4
00:00:10,470 --> 00:00:12,470
Ve algoritma hatırlama
Bir adım-adım seti

5
00:00:12,470 --> 00:00:15,260
Bir görevi tamamlamak için talimatları.

6
00:00:15,260 --> 00:00:17,580
>> Seçimi sıralamak
Temel fikir, bu

7
00:00:17,580 --> 00:00:22,080
En küçük sıralanmamış elemanı bulmak ve
sıralı listenin sonuna ekleyin.

8
00:00:22,080 --> 00:00:26,970
Etkili bu ne inşa olduğunu
Bir sıralanmış liste, bir defada bir unsur.

9
00:00:26,970 --> 00:00:29,800
Pseudocode aşağı Breaking
Bu algoritma devlet olabilir

10
00:00:29,800 --> 00:00:34,490
aşağıdaki gibi, bu kadar tekrarlayın
Hiçbir sıralanmamış unsurlar kalır.

11
00:00:34,490 --> 00:00:38,660
Unsorted aracılığıyla arama
Veri küçük değeri bulmak için,

12
00:00:38,660 --> 00:00:44,130
daha sonra küçük değeri takas
ayıklanmamış kısmının ilk elemanı.

13
00:00:44,130 --> 00:00:47,130
>> Bu, bu görselleştirmek için yardımcı olabilir
o yüzden bu bir göz atalım.

14
00:00:47,130 --> 00:00:49,710
Yani bu, ben iddia, bir olduğunu
sıralanmamış dizi ve ben ettik

15
00:00:49,710 --> 00:00:53,040
Tüm belirten bunu gösterilir
elementlerin, kırmızı renkli

16
00:00:53,040 --> 00:00:54,420
Henüz sıralanır değil.

17
00:00:54,420 --> 00:00:57,670
Bu, tüm bir
Dizinin unsorted parçası.

18
00:00:57,670 --> 00:01:02,020
>> Yani adımlarda gidelim
Seçim sıralama bu diziyi sıralamak için.

19
00:01:02,020 --> 00:01:05,296
Yani yine, biz olacak tekrarı konum
Hiçbir sıralanmamış unsurlar kalmayıncaya kadar.

20
00:01:05,296 --> 00:01:07,920
Biz aracılığıyla olacak aramayı sensin
Veri küçük değeri bulmak için,

21
00:01:07,920 --> 00:01:11,990
ve daha sonra bu değeri takas
ayıklanmamış kısmının ilk elemanı.

22
00:01:11,990 --> 00:01:14,380
>> Şu anda, yine tüm
Dizi sıralanmamış bir parçasıdır.

23
00:01:14,380 --> 00:01:16,534
Kırmızı unsurlar sıralanmamış bulunmaktadır.

24
00:01:16,534 --> 00:01:18,700
Bu yüzden arama ve
Biz en küçük değeri bulmak.

25
00:01:18,700 --> 00:01:20,533
Biz, başından başla
Biz sonuna kadar gidin

26
00:01:20,533 --> 00:01:23,630
en küçük değer biridir bulabilirsiniz.

27
00:01:23,630 --> 00:01:24,860
Yani o kısmı biri.

28
00:01:24,860 --> 00:01:29,440
Ve sonra bölüm iki ile bu değeri takas
ayıklanmamış kısmının ilk elemanı,

29
00:01:29,440 --> 00:01:31,340
ya da ilk kırmızı unsur.

30
00:01:31,340 --> 00:01:34,980
>> Bu durumda olacağını
Beş, bu yüzden biz bir ve beş takas.

31
00:01:34,980 --> 00:01:37,320
Bunu yaptığımızda, biz
görsel biz ettik görüyoruz

32
00:01:37,320 --> 00:01:41,260
küçük değerli eleman taşındı
dizinin başından için.

33
00:01:41,260 --> 00:01:43,920
Etkili o elemanı sıralama.

34
00:01:43,920 --> 00:01:47,520
>> Ve böylece biz gerçekten teyit edebilir
ve devlet tek olduğu, sıralanır.

35
00:01:47,520 --> 00:01:52,080
Ve böylece biz sıralanmış kısmını işaret edeceğiz
Bizim dizinin, mavi boyama yoluyla.

36
00:01:52,080 --> 00:01:53,860
>> Şimdi biz sadece tekrar işlemi yineleyin.

37
00:01:53,860 --> 00:01:57,430
Biz unsorted kısmından arama
Dizi en küçük elemanı bulmak için.

38
00:01:57,430 --> 00:01:59,000
Bu durumda, iki.

39
00:01:59,000 --> 00:02:02,100
>> Biz ilk o takas
sıralanmamış parçanın elemanı.

40
00:02:02,100 --> 00:02:05,540
Bu durumda iki de olur
ayıklanmamış kısmının ilk elemanı.

41
00:02:05,540 --> 00:02:08,650
Bu yüzden kendisi ile iki takas,
hangi gerçekten sadece iki yaprak

42
00:02:08,650 --> 00:02:11,257
o ve o tür nereye.

43
00:02:11,257 --> 00:02:13,840
Devam edersek, biz arama
En küçük eleman bulmak için.

44
00:02:13,840 --> 00:02:15,030
Üç bulunuyor.

45
00:02:15,030 --> 00:02:17,650
Biz ilk ile takas
beş elemanı.

46
00:02:17,650 --> 00:02:19,450
Ve şimdi üç sıralanır.

47
00:02:19,450 --> 00:02:22,440
>> Biz yine arama ve biz
En küçük eleman dört bulmak.

48
00:02:22,440 --> 00:02:28,070
Biz ilk elemanı ile takas
sıralanmamış parçası ve şimdi dört sıralanır.

49
00:02:28,070 --> 00:02:29,910
>> Biz beş olduğunu bulmak
En küçük eleman.

50
00:02:29,910 --> 00:02:32,900
Biz ilk ile takas
sıralanmamış parçanın elemanı.

51
00:02:32,900 --> 00:02:34,740
Ve şimdi beş sıralanır.

52
00:02:34,740 --> 00:02:36,660
>> Ve sonra son olarak, bizim
sıralanmamış bir parçası oluşur

53
00:02:36,660 --> 00:02:38,576
Sadece tek bir eleman,
bu yüzden arama

54
00:02:38,576 --> 00:02:41,740
ve altı olduğunu bulmak
En küçük ve aslında, sadece unsur.

55
00:02:41,740 --> 00:02:44,906
Ve sonra biz sıralanır söyleyebiliriz.

56
00:02:44,906 --> 00:02:47,530
Ve şimdi bizim dizi açık ettik
Tamamen sıralanmamış engel

57
00:02:47,530 --> 00:02:52,660
kırmızı, tamamen dizildi
mavi, seçim sıralama kullanarak.

58
00:02:52,660 --> 00:02:54,920
>> Yani en kötü durum senaryosu burada ne var?

59
00:02:54,920 --> 00:02:57,830
Peki mutlak kötü olarak
dava, biz bakmak zorundayız

60
00:02:57,830 --> 00:03:02,170
dizinin elemanları tüm
En küçük ayrımı yapılmamış diğer eleman bulmak,

61
00:03:02,170 --> 00:03:04,750
ve biz tekrarlamak zorunda
bu işlem, n kere.

62
00:03:04,750 --> 00:03:09,090
Dizinin her elemanı için bir kez
biz sadece, çünkü bu algoritmada,

63
00:03:09,090 --> 00:03:12,180
zaman sıralama tek unsur.

64
00:03:12,180 --> 00:03:13,595
>> En iyi senaryo nedir?

65
00:03:13,595 --> 00:03:15,040
Peki, doğru aynı değil mi?

66
00:03:15,040 --> 00:03:18,440
Biz aslında hala adım adım var
Dizinin her elemanı

67
00:03:18,440 --> 00:03:22,040
amacıyla, olduğunu onaylamak için
Aslında, küçük elemanı.

68
00:03:22,040 --> 00:03:26,760
>> Yani en kötü durum çalışma zamanı, biz
bir süreç n defa tekrarlamak zorunda,

69
00:03:26,760 --> 00:03:28,960
n elemanlarının her biri için bir kez.

70
00:03:28,960 --> 00:03:31,940
Ve en iyi senaryo,
Aynı yapmak zorundayız.

71
00:03:31,940 --> 00:03:35,340
>> Yani geri düşünme bizim
hesaplama karmaşıklığı araç,

72
00:03:35,340 --> 00:03:39,250
Ne düşünüyorsunuz kötü
Seçim sıralama için durum zamanı?

73
00:03:39,250 --> 00:03:41,840
Sizce en iyi
Seçim sıralama için durum zamanı?

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> N karesi arasında Big O tahmin mı,
Big Omega n karesi?

76
00:03:49,325 --> 00:03:49,950
Sen haklı olurdunuz.

77
00:03:49,950 --> 00:03:52,490
Bu, aslında,
En kötü durum ve en iyi durum çalıştırmak

78
00:03:52,490 --> 00:03:55,100
Seçim sıralama zamanları.

79
00:03:55,100 --> 00:03:56,260
>> Ben Doug Lloyd değilim.

80
00:03:56,260 --> 00:03:58,600
Bu CS50 olduğunu.

81
00:03:58,600 --> 00:04:00,279