1
00:00:00,000 --> 00:00:05,726
>> [MUZYKI]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Wybór rodzaju jest
algorytm, który, jak można się spodziewać,

3
00:00:08,600 --> 00:00:10,470
sortuje zestaw elementów.

4
00:00:10,470 --> 00:00:12,470
I algorytm wycofywania
to zestaw krok po kroku

5
00:00:12,470 --> 00:00:15,260
instrukcji do wykonania zadania.

6
00:00:15,260 --> 00:00:17,580
>> W doborze posortować
Podstawowym założeniem jest to,

7
00:00:17,580 --> 00:00:22,080
niesortowanych znaleźć najmniejszy element i
dodać go do końca listy sortowane.

8
00:00:22,080 --> 00:00:26,970
Skutecznie co to robi jest budowa
sortowaną listę jeden element w określonym czasie.

9
00:00:26,970 --> 00:00:29,800
Złamanie go do Pseudokod
możemy stwierdzić tego algorytmu

10
00:00:29,800 --> 00:00:34,490
w następujący sposób, powtórzyć, aż
brak elementów nieposortowane pozostać.

11
00:00:34,490 --> 00:00:38,660
Szukaj poprzez nieposortowane
Dane znaleźć najmniejszą wartość,

12
00:00:38,660 --> 00:00:44,130
następnie zamienić najmniejszą wartość z
Pierwszym elementem nieposortowanej części.

13
00:00:44,130 --> 00:00:47,130
>> To może pomóc w wizualizacji tego,
więc rzućmy okiem na to.

14
00:00:47,130 --> 00:00:49,710
Więc to, jak twierdzą, jest
nieposortowane tablica i mam

15
00:00:49,710 --> 00:00:53,040
wskazane go przez wskazanie, że wszystkie
elementy są w kolorze czerwonym,

16
00:00:53,040 --> 00:00:54,420
nie są one jednak klasyfikowane.

17
00:00:54,420 --> 00:00:57,670
Jest cała
nieposortowane część tablicy.

18
00:00:57,670 --> 00:01:02,020
>> Więc chodźmy po schodach
Wybór rodzaju sortowania tej tablicy.

19
00:01:02,020 --> 00:01:05,296
Więc jeszcze raz, że my będziemy powtarzać
dopóki pozostają żadne elementy nieposortowane.

20
00:01:05,296 --> 00:01:07,920
Będziemy przeszukiwać
Dane znaleźć najmniejszą wartość,

21
00:01:07,920 --> 00:01:11,990
a następnie zamienić tę wartość z
Pierwszym elementem nieposortowanej części.

22
00:01:11,990 --> 00:01:14,380
>> Teraz znowu cała
Tablica jest nieposortowane częścią.

23
00:01:14,380 --> 00:01:16,534
Wszystkie elementy są nieposortowane czerwonych.

24
00:01:16,534 --> 00:01:18,700
Tak więc przeszukiwać i
znaleźć najmniejszą wartość.

25
00:01:18,700 --> 00:01:20,533
Zaczynamy na początku,
idziemy do końca,

26
00:01:20,533 --> 00:01:23,630
znaleźć najmniejszą wartość jest jeden.

27
00:01:23,630 --> 00:01:24,860
Więc to jest część pierwsza.

28
00:01:24,860 --> 00:01:29,440
A następnie część druga, zamienić tę wartość z
pierwszym elementem nieposortowanej części,

29
00:01:29,440 --> 00:01:31,340
lub pierwszy red elementem.

30
00:01:31,340 --> 00:01:34,980
>> W tym przypadku, byłoby
pięć, więc zamienić jeden i pięć.

31
00:01:34,980 --> 00:01:37,320
Gdy to zrobimy, możemy
wizualnie zobaczyć, że mamy

32
00:01:37,320 --> 00:01:41,260
przeniósł najmniejszy o wartości elementu
tablicy, na samym początku.

33
00:01:41,260 --> 00:01:43,920
Skutecznie sortowania ten element.

34
00:01:43,920 --> 00:01:47,520
>> I tak możemy rzeczywiście potwierdzają
i stwierdza, że ​​jeden, jest klasyfikowane.

35
00:01:47,520 --> 00:01:52,080
I tak będziemy wskazywać posortowane części
z naszej tablicy, kolorując to niebieski.

36
00:01:52,080 --> 00:01:53,860
>> Teraz tylko powtórzyć proces ponownie.

37
00:01:53,860 --> 00:01:57,430
Mamy przeszukać nieposortowanej części
tablica znaleźć najmniejszy element.

38
00:01:57,430 --> 00:01:59,000
W tym przypadku, to jest dwa.

39
00:01:59,000 --> 00:02:02,100
>> Możemy zamienić, że z pierwszym
elementem nieposortowanej części.

40
00:02:02,100 --> 00:02:05,540
W tym przypadku dwie również dzieje się
pierwszym elementem nieposortowanej części.

41
00:02:05,540 --> 00:02:08,650
Tak więc zamienić dwa z siebie,
które tak naprawdę pozostawia dwa

42
00:02:08,650 --> 00:02:11,257
gdzie jest, i to jest klasyfikowane.

43
00:02:11,257 --> 00:02:13,840
Kontynuując, możemy przeszukiwać
znaleźć najmniejszy element.

44
00:02:13,840 --> 00:02:15,030
To trzy.

45
00:02:15,030 --> 00:02:17,650
Możemy zamienić go z pierwszym
Element, który jest pięć lat.

46
00:02:17,650 --> 00:02:19,450
A teraz trzy są sortowane.

47
00:02:19,450 --> 00:02:22,440
>> Mamy przeszukać ponownie, a my
znaleźć najmniejszy element jest cztery.

48
00:02:22,440 --> 00:02:28,070
Możemy zamienić go z pierwszym elementem
Część nieposortowane, a teraz cztery są sortowane.

49
00:02:28,070 --> 00:02:29,910
>> Uważamy, że pięć jest
najmniejszy element.

50
00:02:29,910 --> 00:02:32,900
Możemy zamienić go z pierwszym
elementem nieposortowanej części.

51
00:02:32,900 --> 00:02:34,740
I teraz pięć jest posortowana.

52
00:02:34,740 --> 00:02:36,660
>> I wtedy wreszcie, nasze
nieposortowane część składa się

53
00:02:36,660 --> 00:02:38,576
z tylko jednego elementu
więc przeszukiwać

54
00:02:38,576 --> 00:02:41,740
i okazuje się, że sześć jest
Najmniejszy i w rzeczywistości jedynym elementem.

55
00:02:41,740 --> 00:02:44,906
I wtedy możemy stwierdzić, że jest klasyfikowane.

56
00:02:44,906 --> 00:02:47,530
A teraz mamy włączony naszą tablicę
przed całkowitym nieposortowane

57
00:02:47,530 --> 00:02:52,660
na czerwono, aby całkowicie klasyfikowane
w kolorze niebieskim, za pomocą wyboru rodzaju.

58
00:02:52,660 --> 00:02:54,920
>> Więc co jest najgorszym przypadku tutaj?

59
00:02:54,920 --> 00:02:57,830
Dobrze się najgorszego
Sprawa, musimy spojrzeć na

60
00:02:57,830 --> 00:03:02,170
wszystkie elementy tablicy do
znaleźć najmniejszą niesegregowanych elementu,

61
00:03:02,170 --> 00:03:04,750
i musimy powtórzyć
proces ten n razy.

62
00:03:04,750 --> 00:03:09,090
Raz dla każdego elementu tablicy
dlatego, że tylko w tym algorytmie,

63
00:03:09,090 --> 00:03:12,180
jakby jeden element na raz.

64
00:03:12,180 --> 00:03:13,595
>> Jaki jest najlepszy scenariusz?

65
00:03:13,595 --> 00:03:15,040
Cóż, to jest dokładnie to samo, prawda?

66
00:03:15,040 --> 00:03:18,440
Aktualnie mamy do jeszcze krok po kroku
każdy element tablicy

67
00:03:18,440 --> 00:03:22,040
W celu potwierdzenia, że ​​jest to,
W rzeczywistości, najmniejsze elementem.

68
00:03:22,040 --> 00:03:26,760
>> Tak więc w najgorszym przypadku czas pracy, możemy
trzeba powtórzyć proces n razy,

69
00:03:26,760 --> 00:03:28,960
raz dla każdej z n elementów.

70
00:03:28,960 --> 00:03:31,940
A w najlepszym przypadku,
musimy zrobić to samo.

71
00:03:31,940 --> 00:03:35,340
>> Więc wracając myślami do naszego
Złożoność obliczeniowa przybornik,

72
00:03:35,340 --> 00:03:39,250
jak myślisz, co jest najgorsze
Sprawa wykonawcze do wyboru rodzaju?

73
00:03:39,250 --> 00:03:41,840
Jak myślisz, co jest najlepsze
Sprawa wykonawcze do wyboru rodzaju?

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

75
00:03:44,760 --> 00:03:49,325
>> Czy domyślasz Big O n do kwadratu,
i Big Omega n do kwadratu?

76
00:03:49,325 --> 00:03:49,950
Byłbyś w prawo.

77
00:03:49,950 --> 00:03:52,490
Są to w rzeczywistości
Najgorszy i najlepszy prowadzony przypadku

78
00:03:52,490 --> 00:03:55,100
razy, do wyboru rodzaju.

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

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

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