1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [Балонот Сортирај]

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP Универзитетот Харвард]

3
00:00:04,560 --> 00:00:07,500
[Ова е CS50. CS50TV]

4
00:00:08,000 --> 00:00:11,730
Меур Сортирај е пример за сортирање алгоритам -

5
00:00:11,730 --> 00:00:14,460
тоа е, постапката за сортирање збир на елементи

6
00:00:14,460 --> 00:00:15,840
опаѓачки или растечки редослед.

7
00:00:15,840 --> 00:00:18,710
На пример, ако си сакал да го решите низа се состои од броеви

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], коректна имплементација на меур Сортирај ќе се врати на

9
00:00:23,060 --> 00:00:26,260
подредени низа [2, 3, 5, 9] во растечки редослед.

10
00:00:26,260 --> 00:00:28,850
Сега, јас одам да се објасни во pseudocode како алгоритам работи.

11
00:00:28,850 --> 00:00:34,000
>> Да речеме дека ние сме сортирање листа на 5 броеви - 3, 2, 9, 6 и 5.

12
00:00:34,000 --> 00:00:37,650
Алгоритам започнува со разгледување на првите два елементи, 3 и 2,

13
00:00:37,650 --> 00:00:40,850
и проверка дали тие се на ред во однос на едни со други.

14
00:00:40,850 --> 00:00:43,150
Тие се - 3 е поголема од 2.

15
00:00:43,150 --> 00:00:45,190
Да се ​​биде во растечки редослед, тие би требало да биде обратно.

16
00:00:45,190 --> 00:00:46,610
Значи, ние ги трампа.

17
00:00:46,610 --> 00:00:49,760
Сега листа изгледа вака: [2, 3, 9, 6, 5].

18
00:00:49,760 --> 00:00:52,450
>> Следно, ќе погледнеме во вториот и третиот елементи, 3 и 9.

19
00:00:52,450 --> 00:00:55,770
Тие се во правилен ред во однос на едни со други.

20
00:00:55,770 --> 00:00:58,800
Тоа е, 3 е помалку од 9 па алгоритам не ги трампа.

21
00:00:58,800 --> 00:01:01,900
Следно, ќе погледнеме во 9 и 6. Тие се на ред.

22
00:01:01,900 --> 00:01:04,260
>> Значи, ние треба да ги трампа заради 9 е поголема од 6.

23
00:01:04,260 --> 00:01:08,840
И на крај, гледаме во последните два цели броја, 9 и 5.

24
00:01:08,840 --> 00:01:10,850
Тие се на ред, па тие мора да бидат заменети.

25
00:01:10,850 --> 00:01:13,360
По првиот комплетен помине низ листата,

26
00:01:13,360 --> 00:01:17,140
тоа би изгледало вака: [2, 3, 6, 5, 9].

27
00:01:17,140 --> 00:01:19,690
Не е лошо. Тоа е речиси подредени.

28
00:01:19,690 --> 00:01:22,450
Но, ние треба да се кандидира низ листата повторно да го добие целосно подредени.

29
00:01:22,450 --> 00:01:29,250
Две е помалку од 3, па ние не ги трампа.

30
00:01:29,250 --> 00:01:31,700
>> Три е помалку од 6, па ние не ги трампа.

31
00:01:31,700 --> 00:01:35,500
Шест е поголема од 5. Ние заменети.

32
00:01:35,500 --> 00:01:38,460
Шест е помала од 9. Ние не трампа.

33
00:01:38,460 --> 00:01:42,170
По втор пат преку, тоа би изгледало вака: [2, 3, 5, 6, 9]. Совршена.

34
00:01:42,170 --> 00:01:44,680
Сега, ајде да напишете го во pseudocode.

35
00:01:44,680 --> 00:01:48,450
Во суштина, за секој елемент во листата, треба да се погледне во него

36
00:01:48,450 --> 00:01:50,060
и елемент директно на своето право.

37
00:01:50,060 --> 00:01:53,420
Ако тие се надвор од однос еден на друг - тоа е, ако елемент на левата

38
00:01:53,420 --> 00:01:56,810
е поголем од оној на десната - ние треба да се разменуваат со два елементи.

39
00:01:56,810 --> 00:02:01,270
>> Ние го правиме ова за секој елемент од листата, и ние го направи еден поминат низ.

40
00:02:01,270 --> 00:02:05,160
Сега ние само треба да направите премин преку доволно пати за да се обезбеди листа

41
00:02:05,160 --> 00:02:06,480
е целосно, правилно подредени.

42
00:02:06,480 --> 00:02:08,889
Но, колку пати ние мора да поминат низ листата на

43
00:02:08,889 --> 00:02:10,400
Гарантирам дека ќе завршиш?

44
00:02:10,400 --> 00:02:14,730
Па, најлошото сценарио е ако имаме целосно наназад листа.

45
00:02:14,730 --> 00:02:17,840
Тогаш е потребно голем број на премин низ еднаков на бројот

46
00:02:17,840 --> 00:02:19,730
на елементите n-1.

47
00:02:19,730 --> 00:02:24,720
Ако ова не дава никаква смисла интуитивно, мислам на едноставен случај - Листа [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> Ова се случува да се земе еден премин преку да се најде правилно.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - Најлошото е тоа што со 3 елементи подредени наназад,

50
00:02:33,060 --> 00:02:34,830
тоа се случува да се земе 2 повторувања за сортирање.

51
00:02:34,830 --> 00:02:37,980
По една повторување, тоа е [2, 1, 3].

52
00:02:37,980 --> 00:02:39,550
Вториот приноси на подредени низа [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
Значи знаеш дека никогаш не треба да се оди преку низа, во целина,

54
00:02:43,350 --> 00:02:46,790
повеќе од n-1 времиња, каде n е бројот на елементи во низата.

55
00:02:47,090 --> 00:02:50,470
Таа се вика меур Сортирај бидејќи најголемиот елементи имаат тенденција да "балон-up"

56
00:02:50,470 --> 00:02:51,950
на правото прилично брзо.

57
00:02:51,950 --> 00:02:53,980
Всушност, овој алгоритам има многу интересни однесување.

58
00:02:53,980 --> 00:02:57,410
>> По m повторувања низ целата низа,

59
00:02:57,410 --> 00:02:59,000
на најдесната m елементи се гарантира

60
00:02:59,000 --> 00:03:01,000
да се решат во нивните правилната место.

61
00:03:01,000 --> 00:03:02,280
Ако сакате да видите ова за себе,

62
00:03:02,280 --> 00:03:05,500
можеме да ја обидат на целосно наназад Листа [9, 6, 5, 3, 2].

63
00:03:05,500 --> 00:03:08,220
По една помине низ целиот листа,

64
00:03:08,220 --> 00:03:09,220
[Звукот на пишување]

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
на најдесната елемент 9 е во неговото правилно место.

67
00:03:21,250 --> 00:03:24,760
По вториот премин преку, на 6 ќе имаат "клобуркаше-up" на

68
00:03:24,760 --> 00:03:26,220
Вториот најдесната место.

69
00:03:26,220 --> 00:03:28,840
На два елементи на десната - 6 и 9 - ќе биде во нивната правилна места

70
00:03:28,840 --> 00:03:30,580
по првите две помине низ тие.

71
00:03:30,580 --> 00:03:32,590
>> Значи, како ние да го користите овој да се оптимизира алгоритам?

72
00:03:32,590 --> 00:03:34,850
Па, по една повторување преку низа

73
00:03:34,850 --> 00:03:37,690
ние не, всушност треба да се провери најдесната елемент

74
00:03:37,690 --> 00:03:39,200
затоа што знаеме тоа подредени.

75
00:03:39,200 --> 00:03:43,050
По две повторувања, знаеме дека најдесната два елементи се во место.

76
00:03:43,050 --> 00:03:48,260
Значи, во целина, по к повторувања низ целиот спектар,

77
00:03:48,260 --> 00:03:51,550
проверка на последниот к елементи е излишна бидејќи знаеме

78
00:03:51,550 --> 00:03:52,360
тие се во точната локација веќе.

79
00:03:52,360 --> 00:03:54,870
>> Значи, ако сте сортирање низа од n елементи,

80
00:03:54,870 --> 00:03:57,870
на првата итерација - you'll треба да решите сите елементи - првите n-0.

81
00:03:57,870 --> 00:04:04,170
На вториот повторување, ќе треба да се погледне во сите елементи, но во последно -

82
00:04:04,170 --> 00:04:07,090
на првите n-1.

83
00:04:07,090 --> 00:04:10,520
Друга оптимизација може да биде да се провери дали листата е веќе сортирана

84
00:04:10,520 --> 00:04:11,710
по секое повторување.

85
00:04:11,710 --> 00:04:13,900
Ако тоа е веќе сортирани, ние не треба да направите било какви повеќе повторувања

86
00:04:13,900 --> 00:04:15,310
низ листата.

87
00:04:15,310 --> 00:04:16,220
Како можеме да го направите ова?

88
00:04:16,220 --> 00:04:19,360
Па, ако не се направи било свопови на премин преку на листата,

89
00:04:19,360 --> 00:04:22,350
јасно е дека листата е веќе сортирана, бидејќи ние не разменуваат ништо.

90
00:04:22,350 --> 00:04:24,160
Значи ние дефинитивно не треба да се најде повторно.

91
00:04:24,160 --> 00:04:27,960
>> Можеби можете да се иницијализира знаме променлива наречена "не подредени ', за да

92
00:04:27,960 --> 00:04:30,990
лажни и промените на true ако треба да се разменуваат сите елементи на

93
00:04:30,990 --> 00:04:32,290
еден повторување преку низа.

94
00:04:32,290 --> 00:04:35,350
Или слично, да се направи контра да се брои колку свопови ќе се направи

95
00:04:35,350 --> 00:04:37,040
на која било дадена повторување.

96
00:04:37,040 --> 00:04:40,040
На крајот на повторување, ако не се разменуваат било кој од елементите,

97
00:04:40,040 --> 00:04:41,780
знаеш листата е веќе сортирани и ќе завршиш.

98
00:04:41,780 --> 00:04:44,090
Меур Сортирај, како и другите алгоритми за сортирање, може да биде

99
00:04:44,090 --> 00:04:46,960
tweaked да работат за било какви елементи кои имаат нарачување метод.

100
00:04:46,960 --> 00:04:50,610
>> Тоа е, со оглед два елементи имате начин да се каже дали првиот

101
00:04:50,610 --> 00:04:53,770
е поголем од еднаква или помала од секунда.

102
00:04:53,770 --> 00:04:56,870
На пример, можете да сортирање букви од азбуката, велејќи

103
00:04:56,870 --> 00:05:00,520
дека <б, б <в, итн

104
00:05:00,520 --> 00:05:03,830
Или може да се најде денови од неделата каде недела е помалку од понеделник

105
00:05:03,830 --> 00:05:05,110
што е помалку од вторникот.

106
00:05:05,110 --> 00:05:09,630
>> Меур Сортирај никој случај не е многу ефикасна или брзо сортирање алгоритам.

107
00:05:09,630 --> 00:05:12,370
Нејзините најлошото траење е Биг О од n ²

108
00:05:12,370 --> 00:05:14,810
затоа што треба да направите n итерации преку листа

109
00:05:14,810 --> 00:05:18,430
проверка на сите n елементи секој премин преку, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
Ова кандидира време, значи дека како број на елементи сте сортирање зголемува,

111
00:05:22,730 --> 00:05:24,330
во бегство време се зголемува quadratically.

112
00:05:24,330 --> 00:05:27,330
>> Но, ако ефикасност не е голема загриженост на вашата програма

113
00:05:27,330 --> 00:05:29,550
или ако сте само сортирање мал број на елементи,

114
00:05:29,550 --> 00:05:31,660
може да најдете меур Сортирај корисни, бидејќи

115
00:05:31,660 --> 00:05:33,360
тоа е еден од наједноставните сортирање алгоритми за да се разбере

116
00:05:33,360 --> 00:05:34,250
и да се код.

117
00:05:34,250 --> 00:05:37,270
Тоа е исто така одличен начин да се добие искуство со преведување теоретски

118
00:05:37,270 --> 00:05:40,220
алгоритам во вистински функционирање код.

119
00:05:40,220 --> 00:05:43,000
Па, тоа е меур Сортирај за вас. Ви благодариме за гледање.

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