1
00:00:00,000 --> 00:00:05,726
>> [MUSIC PLAYING]

2
00:00:05,726 --> 00:00:08,600
Doug LLOYD: Seleksi semacam adalah
algoritma yang, seperti yang Anda harapkan,

3
00:00:08,600 --> 00:00:10,470
macam satu set elemen.

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

5
00:00:12,470 --> 00:00:15,260
instruksi untuk menyelesaikan tugas.

6
00:00:15,260 --> 00:00:17,580
>> Dalam seleksi mengurutkan
Ide dasarnya adalah ini,

7
00:00:17,580 --> 00:00:22,080
menemukan elemen terkecil dan disortir
menambahkannya ke akhir daftar diurutkan.

8
00:00:22,080 --> 00:00:26,970
Efektif apa yang dilakukan adalah membangun
daftar diurutkan, salah satu elemen pada suatu waktu.

9
00:00:26,970 --> 00:00:29,800
Memecahnya ke pseudocode
kita bisa menyatakan algoritma ini

10
00:00:29,800 --> 00:00:34,490
sebagai berikut, ulangi ini sampai
tidak ada unsur disortir tetap.

11
00:00:34,490 --> 00:00:38,660
Cari melalui disortir
Data untuk mencari nilai terkecil,

12
00:00:38,660 --> 00:00:44,130
kemudian swap nilai terkecil dengan
elemen pertama dari bagian yang tidak dipisahkan.

13
00:00:44,130 --> 00:00:47,130
>> Ini dapat membantu untuk memvisualisasikan ini,
jadi mari kita lihat ini.

14
00:00:47,130 --> 00:00:49,710
Jadi ini, saya berpendapat, adalah
Array disortir dan saya sudah

15
00:00:49,710 --> 00:00:53,040
ditunjukkan dengan menunjukkan bahwa semua
dari unsur-unsur yang berwarna merah,

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

17
00:00:54,420 --> 00:00:57,670
Ini adalah seluruh yang
disortir bagian dari array.

18
00:00:57,670 --> 00:01:02,020
>> Jadi mari kita pergi melalui langkah-langkah
Temukan sort untuk mengurutkan array ini.

19
00:01:02,020 --> 00:01:05,296
Jadi sekali lagi, kita akan ulangi
sampai tidak ada unsur disortir tetap.

20
00:01:05,296 --> 00:01:07,920
Kita akan cari melalui
Data untuk mencari nilai terkecil,

21
00:01:07,920 --> 00:01:11,990
dan kemudian menukar bahwa nilai dengan
elemen pertama dari bagian yang tidak dipisahkan.

22
00:01:11,990 --> 00:01:14,380
>> Sekarang, sekali lagi, seluruh yang
Array adalah bagian yang tidak dipisahkan.

23
00:01:14,380 --> 00:01:16,534
Semua elemen merah disortir.

24
00:01:16,534 --> 00:01:18,700
Jadi kita mencari melalui dan
kita menemukan nilai terkecil.

25
00:01:18,700 --> 00:01:20,533
Kami mulai dari awal,
kita pergi ke akhir,

26
00:01:20,533 --> 00:01:23,630
kita menemukan nilai terkecil adalah, salah satu.

27
00:01:23,630 --> 00:01:24,860
Jadi itu bagian satu.

28
00:01:24,860 --> 00:01:29,440
Dan kemudian bagian dua, menukar yang nilai dengan
elemen pertama dari bagian disortir,

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

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

31
00:01:34,980 --> 00:01:37,320
Ketika kita melakukan ini, kita bisa
visual melihat bahwa kami telah

32
00:01:37,320 --> 00:01:41,260
pindah elemen terkecil dihargai
dari array, untuk awal.

33
00:01:41,260 --> 00:01:43,920
Efektif menyortir elemen.

34
00:01:43,920 --> 00:01:47,520
>> Dan jadi kita memang bisa mengkonfirmasi
dan negara yang satu, diurutkan.

35
00:01:47,520 --> 00:01:52,080
Dan jadi kita akan menunjukkan bagian diurutkan
dari array kita, dengan mewarnai biru.

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

37
00:01:53,860 --> 00:01:57,430
Kami mencari melalui bagian disortir dari
array untuk menemukan elemen terkecil.

38
00:01:57,430 --> 00:01:59,000
Dalam hal ini, itu dua.

39
00:01:59,000 --> 00:02:02,100
>> Kami menukar bahwa dengan yang pertama
unsur bagian yang tidak dipisahkan.

40
00:02:02,100 --> 00:02:05,540
Dalam hal ini dua juga terjadi menjadi
elemen pertama dari bagian yang tidak dipisahkan.

41
00:02:05,540 --> 00:02:08,650
Jadi kita menukar dua dengan dirinya sendiri,
yang benar-benar hanya meninggalkan dua

42
00:02:08,650 --> 00:02:11,257
mana itu, dan itu diurutkan.

43
00:02:11,257 --> 00:02:13,840
Melanjutkan, kami mencari melalui
untuk menemukan elemen terkecil.

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

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

46
00:02:17,650 --> 00:02:19,450
Dan sekarang tiga diurutkan.

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

48
00:02:22,440 --> 00:02:28,070
Kami swap dengan elemen pertama dari
bagian disortir, dan sekarang empat diurutkan.

49
00:02:28,070 --> 00:02:29,910
>> Kami menemukan bahwa lima adalah
elemen terkecil.

50
00:02:29,910 --> 00:02:32,900
Kami swap dengan yang pertama
unsur bagian yang tidak dipisahkan.

51
00:02:32,900 --> 00:02:34,740
Dan sekarang lima diurutkan.

52
00:02:34,740 --> 00:02:36,660
>> Dan kemudian terakhir, kami
bagian disortir terdiri

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

54
00:02:38,576 --> 00:02:41,740
dan kami menemukan bahwa enam adalah
terkecil, dan pada kenyataannya, hanya elemen.

55
00:02:41,740 --> 00:02:44,906
Dan kemudian kita dapat menyatakan bahwa itu diurutkan.

56
00:02:44,906 --> 00:02:47,530
Dan sekarang kami sudah beralih array kita
dari yang benar-benar unsorted

57
00:02:47,530 --> 00:02:52,660
merah, untuk benar-benar diurutkan
warna biru, menggunakan semacam seleksi.

58
00:02:52,660 --> 00:02:54,920
>> Jadi apa skenario terburuk di sini?

59
00:02:54,920 --> 00:02:57,830
Baik di terburuk mutlak
kasus, kita harus melihat lebih

60
00:02:57,830 --> 00:03:02,170
semua elemen dari array untuk
menemukan elemen disortir terkecil,

61
00:03:02,170 --> 00:03:04,750
dan kami harus mengulangi
Proses ini n kali.

62
00:03:04,750 --> 00:03:09,090
Sekali untuk setiap elemen dari array
karena kita hanya, dalam algoritma ini,

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

64
00:03:12,180 --> 00:03:13,595
>> Apa skenario kasus terbaik?

65
00:03:13,595 --> 00:03:15,040
Baik itu persis sama, kan?

66
00:03:15,040 --> 00:03:18,440
Kami benar-benar harus tetap melangkah melalui
setiap elemen dari array

67
00:03:18,440 --> 00:03:22,040
untuk mengkonfirmasi bahwa itu adalah,
pada kenyataannya, elemen terkecil.

68
00:03:22,040 --> 00:03:26,760
>> Jadi kasus runtime terburuk, kami
harus mengulangi proses n kali,

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

70
00:03:28,960 --> 00:03:31,940
Dan dalam skenario kasus terbaik,
kita harus melakukan hal yang sama.

71
00:03:31,940 --> 00:03:35,340
>> Jadi berpikir kembali ke kami
komputasi toolbox kompleksitas,

72
00:03:35,340 --> 00:03:39,250
apa yang Anda pikirkan adalah yang terburuk
kasus runtime untuk seleksi semacam?

73
00:03:39,250 --> 00:03:41,840
Apa yang Anda pikirkan adalah yang terbaik
kasus runtime untuk seleksi semacam?

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

75
00:03:44,760 --> 00:03:49,325
>> Apakah Anda menebak Big O n kuadrat,
dan Big Omega n kuadrat?

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

77
00:03:49,950 --> 00:03:52,490
Mereka adalah, pada kenyataannya,
kasus terburuk dan kasus terbaik run

78
00:03:52,490 --> 00:03:55,100
kali, untuk seleksi semacam.

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

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

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