1
00:00:00,000 --> 00:00:05,726
>> [Bermain muzik]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: jenis Pemilihan adalah
algoritma yang, seperti yang anda jangkakan,

3
00:00:08,600 --> 00:00:10,470
menyusun satu set unsur-unsur.

4
00:00:10,470 --> 00:00:12,470
Dan algoritma ingat
adalah satu set langkah-demi-langkah

5
00:00:12,470 --> 00:00:15,260
arahan untuk menyiapkan tugas.

6
00:00:15,260 --> 00:00:17,580
>> Dalam pemilihan menyusun
Idea asas adalah ini,

7
00:00:17,580 --> 00:00:22,080
mencari elemen terisih yang paling kecil dan
menambah kepada akhir senarai disusun.

8
00:00:22,080 --> 00:00:26,970
Berkesan apa yang dilakukan adalah membina
senarai disusun, satu elemen pada satu masa.

9
00:00:26,970 --> 00:00:29,800
Memecahkannya kepada kod pseudo
kita boleh menyatakan algoritma ini

10
00:00:29,800 --> 00:00:34,490
seperti berikut, ulangi ini sehingga
tiada unsur terisih kekal.

11
00:00:34,490 --> 00:00:38,660
Mencari melalui terisih
data untuk mencari nilai yang paling kecil,

12
00:00:38,660 --> 00:00:44,130
kemudian menukar nilai yang paling kecil dengan
Elemen pertama bahagian terisih.

13
00:00:44,130 --> 00:00:47,130
>> Ia boleh membantu untuk menggambarkan ini,
jadi mari kita lihat ini.

14
00:00:47,130 --> 00:00:49,710
Jadi ini, saya berpendapat, adalah
lokasi terisih dan saya telah

15
00:00:49,710 --> 00:00:53,040
menunjukkan ia dengan menunjukkan bahawa semua
unsur-unsur yang berwarna merah,

16
00:00:53,040 --> 00:00:54,420
mereka belum disusun.

17
00:00:54,420 --> 00:00:57,670
Ini adalah keseluruhan
sebahagian terisih array.

18
00:00:57,670 --> 00:01:02,020
>> Jadi mari kita pergi melalui langkah-langkah
jenis pemilihan untuk menyusun pelbagai ini.

19
00:01:02,020 --> 00:01:05,296
Jadi sekali lagi, kita akan berulang
sehingga tidak ada unsur-unsur terisih kekal.

20
00:01:05,296 --> 00:01:07,920
Kami carian gonna melalui
data untuk mencari nilai yang paling kecil,

21
00:01:07,920 --> 00:01:11,990
dan kemudian menukar nilai itu dengan
Elemen pertama bahagian terisih.

22
00:01:11,990 --> 00:01:14,380
>> Buat masa ini, sekali lagi, keseluruhan
lokasi adalah bahagian yang terisih.

23
00:01:14,380 --> 00:01:16,534
Semua unsur-unsur merah terisih.

24
00:01:16,534 --> 00:01:18,700
Oleh itu, kita mencari melalui dan
kita mencari nilai yang paling kecil.

25
00:01:18,700 --> 00:01:20,533
Kami bermula pada awal,
kita pergi ke akhirnya,

26
00:01:20,533 --> 00:01:23,630
kita mencari nilai yang paling kecil adalah, satu.

27
00:01:23,630 --> 00:01:24,860
Jadi itulah bahagian satu.

28
00:01:24,860 --> 00:01:29,440
Dan kemudian bahagian dua, menukar nilai itu dengan
elemen pertama bahagian terisih,

29
00:01:29,440 --> 00:01:31,340
atau unsur merah yang pertama.

30
00:01:31,340 --> 00:01:34,980
>> Dalam hal ini yang akan menjadi
lima, jadi kami menukar satu dan lima.

31
00:01:34,980 --> 00:01:37,320
Apabila kita melakukan ini, kita boleh
visual melihat bahawa kami telah

32
00:01:37,320 --> 00:01:41,260
berpindah elemen terkecil bernilai
array, untuk awal-awal lagi.

33
00:01:41,260 --> 00:01:43,920
Berkesan menyusun elemen yang.

34
00:01:43,920 --> 00:01:47,520
>> Dan supaya kita memang boleh mengesahkan
dan negeri yang satu, disusun.

35
00:01:47,520 --> 00:01:52,080
Dan dengan itu kita akan menunjukkan bahagian yang disusun
pelbagai kami, dengan mewarna ia biru.

36
00:01:52,080 --> 00:01:53,860
>> Sekarang kita hanya mengulangi proses lagi.

37
00:01:53,860 --> 00:01:57,430
Mencari melalui bahagian Unsorted
mudah untuk mencari elemen yang paling kecil.

38
00:01:57,430 --> 00:01:59,000
Dalam kes ini, ia dua.

39
00:01:59,000 --> 00:02:02,100
>> Kami menukar bahawa dengan yang pertama
elemen bahagian terisih.

40
00:02:02,100 --> 00:02:05,540
Dalam kes ini dua juga berlaku untuk menjadi
elemen pertama bahagian terisih.

41
00:02:05,540 --> 00:02:08,650
Oleh itu, kita swap dua dengan sendiri,
yang benar-benar hanya meninggalkan dua

42
00:02:08,650 --> 00:02:11,257
di mana ia adalah, dan ia disusun.

43
00:02:11,257 --> 00:02:13,840
Meneruskan, kita mencari melalui
untuk mencari elemen yang paling kecil.

44
00:02:13,840 --> 00:02:15,030
Ia adalah tiga.

45
00:02:15,030 --> 00:02:17,650
Kami tukar dengan yang pertama
elemen, iaitu lima.

46
00:02:17,650 --> 00:02:19,450
Dan kini tiga disusun.

47
00:02:19,450 --> 00:02:22,440
>> Kami mencari melalui lagi, dan kami
mencari elemen yang paling kecil adalah empat.

48
00:02:22,440 --> 00:02:28,070
Kami tukar dengan unsur pertama
sebahagian terisih, dan kini empat disusun.

49
00:02:28,070 --> 00:02:29,910
>> Kami mendapati bahawa lima adalah
unsur yang paling kecil.

50
00:02:29,910 --> 00:02:32,900
Kami tukar dengan yang pertama
elemen bahagian terisih.

51
00:02:32,900 --> 00:02:34,740
Dan kini lima disusun.

52
00:02:34,740 --> 00:02:36,660
>> Dan kemudian akhir sekali, kami
sebahagian terisih terdiri

53
00:02:36,660 --> 00:02:38,576
hanya satu unsur,
jadi kami mencari melalui

54
00:02:38,576 --> 00:02:41,740
dan kita dapati bahawa enam adalah
paling kecil, dan sebenarnya, hanya unsur.

55
00:02:41,740 --> 00:02:44,906
Dan kemudian kita boleh menyatakan bahawa ia disusun.

56
00:02:44,906 --> 00:02:47,530
Dan sekarang kita telah bertukar pelbagai kami
daripada sepenuhnya terisih

57
00:02:47,530 --> 00:02:52,660
merah, untuk benar-benar disusun
biru, menggunakan jenis pemilihan.

58
00:02:52,660 --> 00:02:54,920
>> Jadi apa kes yang teruk di sini?

59
00:02:54,920 --> 00:02:57,830
Baik dalam yang paling teruk mutlak
kes, kita perlu melihat ke atas

60
00:02:57,830 --> 00:03:02,170
semua elemen array untuk
mencari elemen terisih yang paling kecil,

61
00:03:02,170 --> 00:03:04,750
dan kita perlu mengulangi
proses ini n masa.

62
00:03:04,750 --> 00:03:09,090
Sebaik sahaja untuk setiap elemen array
kerana kita sahaja, dalam algoritma ini,

63
00:03:09,090 --> 00:03:12,180
semacam satu elemen pada satu masa.

64
00:03:12,180 --> 00:03:13,595
>> Apakah senario kes terbaik?

65
00:03:13,595 --> 00:03:15,040
Biasanya tidak sama, bukan?

66
00:03:15,040 --> 00:03:18,440
Kami benar-benar perlu masih melangkah melalui
setiap elemen tunggal array

67
00:03:18,440 --> 00:03:22,040
untuk mengesahkan bahawa ia adalah,
sebenarnya, elemen yang paling kecil.

68
00:03:22,040 --> 00:03:26,760
>> Oleh itu, kes runtime paling teruk, kita
perlu mengulangi proses n kali,

69
00:03:26,760 --> 00:03:28,960
sekali untuk setiap n unsur-unsur.

70
00:03:28,960 --> 00:03:31,940
Dan dalam kes senario yang terbaik,
kita perlu melakukan perkara yang sama.

71
00:03:31,940 --> 00:03:35,340
>> Jadi memikirkan kembali kami
toolbox kerumitan pengiraan,

72
00:03:35,340 --> 00:03:39,250
apa yang anda fikir adalah yang paling teruk
kes runtime untuk jenis pemilihan?

73
00:03:39,250 --> 00:03:41,840
Apa yang anda fikir adalah yang terbaik
kes runtime untuk jenis pemilihan?

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

75
00:03:44,760 --> 00:03:49,325
>> Adakah anda rasa Big O n kuasa dua,
dan Big Omega n kuasa dua?

76
00:03:49,325 --> 00:03:49,950
Anda akan menjadi betul.

77
00:03:49,950 --> 00:03:52,490
Mereka adalah, sebenarnya,
kes yang paling teruk dan kes terbaik jangka

78
00:03:52,490 --> 00:03:55,100
kali, untuk jenis pemilihan.

79
00:03:55,100 --> 00:03:56,260
>> Saya Doug Lloyd.

80
00:03:56,260 --> 00:03:58,600
Ini adalah CS50.

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