1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [BUBBLE SORT]

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP Sveučilištu Harvard]

3
00:00:04,560 --> 00:00:07,500
[OVO JE CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Bubble Sortiraj je primjer sortiranje algoritma -

5
00:00:11,730 --> 00:00:14,460
to jest, postupak za sortiranje skup elemenata u

6
00:00:14,460 --> 00:00:15,840
uzlazno ili silazno.

7
00:00:15,840 --> 00:00:18,710
Na primjer, ako ste htjeli sortirati niz koji se sastoji od brojeva

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], ispravna provedba Bubble Poredaj bi povratak

9
00:00:23,060 --> 00:00:26,260
razvrstani niz [2, 3, 5, 9] uzlaznim redoslijedom.

10
00:00:26,260 --> 00:00:28,850
Sada, ja ću objasniti u pseudocode kako algoritam radi.

11
00:00:28,850 --> 00:00:34,000
>> Recimo da smo sortiranje popis pet brojeva - 3, 2, 9, 6, i 5.

12
00:00:34,000 --> 00:00:37,650
Algoritam započinje gledanjem na prva dva elementa, 3 i 2,

13
00:00:37,650 --> 00:00:40,850
i provjere da li su iz reda u odnosu na druge.

14
00:00:40,850 --> 00:00:43,150
Oni su - 3 je veći od 2.

15
00:00:43,150 --> 00:00:45,190
Da bi se u uzlaznom redoslijedu, oni bi trebali biti obrnuto.

16
00:00:45,190 --> 00:00:46,610
Dakle, mi ih zamijeniti.

17
00:00:46,610 --> 00:00:49,760
Sada popis izgleda ovako: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Dalje, mi gledamo na drugi i treći elementima, tri i devet.

19
00:00:52,450 --> 00:00:55,770
Oni su u ispravnom redoslijedu u odnosu na drugoga.

20
00:00:55,770 --> 00:00:58,800
To je, tri manje od 9 pa algoritam ne mijenjati ih.

21
00:00:58,800 --> 00:01:01,900
Dalje, mi gledamo na devet i šest. Oni su iz reda.

22
00:01:01,900 --> 00:01:04,260
>> Dakle, moramo ih zamijeniti, jer devet je veća od šest.

23
00:01:04,260 --> 00:01:08,840
Na kraju, mi gledamo na posljednja dva cijeli brojevi, 9 i 5.

24
00:01:08,840 --> 00:01:10,850
Oni su od reda, tako da oni moraju biti zamijeniti.

25
00:01:10,850 --> 00:01:13,360
Nakon prvog kompletni prolaze kroz popisu

26
00:01:13,360 --> 00:01:17,140
to izgleda ovako: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Nije loše. To je gotovo riješeno.

28
00:01:19,690 --> 00:01:22,450
Ali moramo pokrenuti kroz popis opet da ga u potpunosti riješeno.

29
00:01:22,450 --> 00:01:29,250
Dva je manje od tri, tako da mi ne mijenjati ih.

30
00:01:29,250 --> 00:01:31,700
>> Tri je manje od 6, pa mi ne mijenjati ih.

31
00:01:31,700 --> 00:01:35,500
Šest je veći od 5. Mi zamijenili.

32
00:01:35,500 --> 00:01:38,460
Šest je manji od 9. Mi ne zamijene.

33
00:01:38,460 --> 00:01:42,170
Nakon drugog prolaza kroz, to izgleda ovako: [2, 3, 5, 6, 9]. Savršeno.

34
00:01:42,170 --> 00:01:44,680
Sada, neka je napisati u pseudocode.

35
00:01:44,680 --> 00:01:48,450
Uglavnom, za svaki element u listi, trebamo gledati na to

36
00:01:48,450 --> 00:01:50,060
i element izravno svojoj desnoj strani.

37
00:01:50,060 --> 00:01:53,420
Ako su iz reda u odnosu na svaki drugi - to jest, ako se element na lijevoj

38
00:01:53,420 --> 00:01:56,810
je veća od one na desnoj strani - treba zamijeniti dva elementa.

39
00:01:56,810 --> 00:02:01,270
>> Mi to učiniti za svaki element liste, a mi smo napravili jedan proći kroz.

40
00:02:01,270 --> 00:02:05,160
Sada samo moramo raditi na prolazni dovoljno puta da se osigura popis

41
00:02:05,160 --> 00:02:06,480
je u potpunosti, pravilno razvrstani.

42
00:02:06,480 --> 00:02:08,889
No, koliko puta moramo proći kroz popisu

43
00:02:08,889 --> 00:02:10,400
jamčiti da ćemo učiniti?

44
00:02:10,400 --> 00:02:14,730
Pa, najgori scenarij je da imamo potpuno unatrag popis.

45
00:02:14,730 --> 00:02:17,840
Tada je potrebno nekoliko pass-through jednak broju

46
00:02:17,840 --> 00:02:19,730
elemenata n-1.

47
00:02:19,730 --> 00:02:24,720
Ako to ne smisla intuitivno, mislim jednostavnog slučaju - popis [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> To se događa da se jedan prolazni sortirati ispravno.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - Najgori slučaj je da se s tri elementa razvrstani unatrag,

50
00:02:33,060 --> 00:02:34,830
to će potrajati dva ponavljanja za sortiranje.

51
00:02:34,830 --> 00:02:37,980
Nakon jednog iteraciji, to je [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Drugi rađa sortirani array [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Pa znaš da nikada ne morate proći kroz niz, u cjelini,

54
00:02:43,350 --> 00:02:46,790
više od n-1 puta, gdje je n broj elemenata u polju.

55
00:02:47,090 --> 00:02:50,470
To se zove Bubble Sortiraj jer najveći elementi imaju tendenciju da "balon-up '

56
00:02:50,470 --> 00:02:51,950
desno prilično brzo.

57
00:02:51,950 --> 00:02:53,980
U stvari, ovaj algoritam ima vrlo zanimljivu ponašanje.

58
00:02:53,980 --> 00:02:57,410
>> Nakon m iteracija kroz cijeli niz,

59
00:02:57,410 --> 00:02:59,000
krajnjem desnom m elementi su zajamčena

60
00:02:59,000 --> 00:03:01,000
biti razvrstani u njihovom ispravnom mjestu.

61
00:03:01,000 --> 00:03:02,280
Ako želite vidjeti ovo za sebe,

62
00:03:02,280 --> 00:03:05,500
možemo probati na potpuno unatrag popisu [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
Nakon jednom prolazu kroz cijeli popis,

64
00:03:08,220 --> 00:03:09,220
[Zvuk pisanja]

65
00:03:09,220 --> 00:03:18,790
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]

66
00:03:18,790 --> 00:03:21,250
desni elemenat 9 je na svom mjestu.

67
00:03:21,250 --> 00:03:24,760
Nakon što je drugi prolazni, 6 će imati 'bubbled-up "na

68
00:03:24,760 --> 00:03:26,220
drugi desni mjesto.

69
00:03:26,220 --> 00:03:28,840
Ova dva elementa na desno - 6 i 9 - bit će u njihovim pravilnim mjestima

70
00:03:28,840 --> 00:03:30,580
nakon prva dva pass-through.

71
00:03:30,580 --> 00:03:32,590
>> Dakle, kako možemo koristiti ovu optimizirati algoritam?

72
00:03:32,590 --> 00:03:34,850
Pa, nakon jedne iteracije kroz niz

73
00:03:34,850 --> 00:03:37,690
mi zapravo ne trebaju provjeriti desni elementa

74
00:03:37,690 --> 00:03:39,200
jer znamo da je riješeno.

75
00:03:39,200 --> 00:03:43,050
Nakon dva iteracija, znamo jesu li desni dva elementa su na mjestu.

76
00:03:43,050 --> 00:03:48,260
Dakle, u cjelini, nakon k iteracija kroz cijeli niz,

77
00:03:48,260 --> 00:03:51,550
Provjera posljednje k elemenata je suvišan, jer znamo

78
00:03:51,550 --> 00:03:52,360
oni su na pravom mjestu već.

79
00:03:52,360 --> 00:03:54,870
>> Dakle, ako ste sortiranje niz od n elemenata,

80
00:03:54,870 --> 00:03:57,870
na prvoj iteraciji - you'll morati sortirati sve elemente - prvi n-0.

81
00:03:57,870 --> 00:04:04,170
Na drugoj iteraciji, morat ćete pogledati sve elemente, ali zadnji -

82
00:04:04,170 --> 00:04:07,090
prvi n-1.

83
00:04:07,090 --> 00:04:10,520
Drugi optimizacija može biti da provjerite je li popis već razvrstani

84
00:04:10,520 --> 00:04:11,710
nakon svake iteracije.

85
00:04:11,710 --> 00:04:13,900
Ako je već razvrstani, mi ne trebamo da bi bilo više iteracije

86
00:04:13,900 --> 00:04:15,310
kroz popis.

87
00:04:15,310 --> 00:04:16,220
Kako možemo to učiniti?

88
00:04:16,220 --> 00:04:19,360
Pa, ako mi ne bi bilo zamjene na prolazni popisa,

89
00:04:19,360 --> 00:04:22,350
jasno je da je popis već razvrstani jer nismo zamijeniti ništa.

90
00:04:22,350 --> 00:04:24,160
Dakle, mi definitivno nemamo za sortiranje ponovno.

91
00:04:24,160 --> 00:04:27,960
>> Možda bi mogao inicijalizirati varijablu zastave pod nazivom 'Ne razvrstani' na

92
00:04:27,960 --> 00:04:30,990
false i promijenite ga vrijedi ako imate za zamjenu nikakve elemente na

93
00:04:30,990 --> 00:04:32,290
jedan iteracija kroz niz.

94
00:04:32,290 --> 00:04:35,350
Ili slično, napraviti brojač brojati koliko swaps napraviti

95
00:04:35,350 --> 00:04:37,040
na svakom iteracija.

96
00:04:37,040 --> 00:04:40,040
Na kraju je iteracija, ako nije zamijeniti bilo kojeg od elemenata,

97
00:04:40,040 --> 00:04:41,780
znate popis već razvrstani i gotovi ste.

98
00:04:41,780 --> 00:04:44,090
Bubble Sortiranje, kao i druge sortiranja algoritama, može biti

99
00:04:44,090 --> 00:04:46,960
praćka za rad svih elemenata koji imaju naručivanja metodu.

100
00:04:46,960 --> 00:04:50,610
>> To je, s obzirom na dva elementa imate način za reći, ako prvi

101
00:04:50,610 --> 00:04:53,770
je veći od, jednak ili manji od drugog.

102
00:04:53,770 --> 00:04:56,870
Na primjer, možete sortirati slova abecede rekavši

103
00:04:56,870 --> 00:05:00,520
da <b, b <c, itd.

104
00:05:00,520 --> 00:05:03,830
Ili ste mogli sortirati dana u tjednu u kojem je nedjelja manje nego ponedjeljak

105
00:05:03,830 --> 00:05:05,110
što je manje od utorak.

106
00:05:05,110 --> 00:05:09,630
>> Bubble Sortiraj nipošto nije vrlo učinkovit ili brzo sortiranje algoritam.

107
00:05:09,630 --> 00:05:12,370
Njegova najgorem slučaju enja je Big O n ²

108
00:05:12,370 --> 00:05:14,810
jer morate napraviti n iteracija kroz popis

109
00:05:14,810 --> 00:05:18,430
provjeru svih n elemente svaki prolazni, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Ovaj put pokrenuti znači da kao broj elemenata ste sortiranje povećava,

111
00:05:22,730 --> 00:05:24,330
pokrenuti vrijeme povećava kvadratnom.

112
00:05:24,330 --> 00:05:27,330
>> Ali ako učinkovitost nije glavna briga programu

113
00:05:27,330 --> 00:05:29,550
ili ako ste samo sortiranje mali broj elemenata,

114
00:05:29,550 --> 00:05:31,660
možda će vam Bubble Sortiraj koristan jer

115
00:05:31,660 --> 00:05:33,360
to je jedan od najjednostavnijih sortiranje algoritama razumjeti

116
00:05:33,360 --> 00:05:34,250
i kodirati.

117
00:05:34,250 --> 00:05:37,270
To je također odličan način da dobijete iskustvo s prevođenjem teorijsko

118
00:05:37,270 --> 00:05:40,220
algoritam u stvarnom funkcioniranju koda.

119
00:05:40,220 --> 00:05:43,000
Pa, to je Bubble Poredaj za vas. Hvala za gledanje.

120
00:05:43,000 --> 00:05:44,000
CS50.TV