1
00:00:00,000 --> 00:00:07,270

2
00:00:07,270 --> 00:00:10,390
>> માર્ક GROZEN-સ્મિથ: હાય, હું માર્ક છું
સ્મિથ Grozen, અને આ Quicksort છે.

3
00:00:10,390 --> 00:00:13,520
જસ્ટ દાખલ સૉર્ટ કરો અને બબલ જેવી
સૉર્ટ કરો, Quicksort માટે અલ્ગોરિધમનો છે

4
00:00:13,520 --> 00:00:15,720
યાદી અથવા વસ્તુઓ ઝાકઝમાળ સૉર્ટ.

5
00:00:15,720 --> 00:00:19,080
સરળતા માટે, ચાલો ધારે છે કે જેઓ
વસ્તુઓ માત્ર પૂર્ણાંકો હોય છે, પરંતુ

6
00:00:19,080 --> 00:00:22,060
Quicksort માટે કામ કરે છે ખબર
માત્ર નંબરો કરતાં વધુ.

7
00:00:22,060 --> 00:00:24,720
ક્વિકસ્ટાર્ટ થોડી વધુ જટિલ છે
કરતાં નિવેશ અથવા બબલ, પરંતુ તે છે

8
00:00:24,720 --> 00:00:27,560
પણ વધારે કાર્યક્ષમ
મોટા ભાગના કિસ્સાઓમાં.

9
00:00:27,560 --> 00:00:28,150
બીજી રાહ જુઓ.

10
00:00:28,150 --> 00:00:30,760
તે માત્ર "મોટા ભાગના કહે છે શું
કિસ્સાઓમાં, "નથી" તમામ "?

11
00:00:30,760 --> 00:00:31,710
રસપ્રદ રીતે, કોઈ.

12
00:00:31,710 --> 00:00:33,560
બધા કિસ્સાઓમાં સમાન હોય છે.

13
00:00:33,560 --> 00:00:36,650
આ વિગત વિશે ચિંતા કરશો નહીં તમે જો
હજુ સુધી મોટી ઓ નોટેશનમાં જોવા મળે છે, પરંતુ છે

14
00:00:36,650 --> 00:00:39,730
Quicksort એક ઓ (એન સ્ક્વેર્ડ) એલ્ગોરિધમ છે
સૌથી ખરાબ છે, જેમ

15
00:00:39,730 --> 00:00:41,430
નિવેશ અથવા બબલ સૉર્ટ કરો.

16
00:00:41,430 --> 00:00:44,950
જો કે, તે સામાન્ય રીતે વધુ કામ કરે છે
જૂની એનાલોગ મીટર અલ્ગોરિધમનો છે.

17
00:00:44,950 --> 00:00:45,750
શા માટે?

18
00:00:45,750 --> 00:00:46,810
અમે પછી પાછા તે માટે મળશે.

19
00:00:46,810 --> 00:00:49,610
પરંતુ હવે માટે છે, માત્ર શીખીએ
Quicksort કેવી રીતે કામ કરે.

20
00:00:49,610 --> 00:00:53,080
>> તેથી આપણે આ Quicksorting લઈ જવામાં દો
નાના થી પૂર્ણાંકો એરે

21
00:00:53,080 --> 00:00:54,260
સૌથી માટે.

22
00:00:54,260 --> 00:01:00,110
અહ તે પૂર્ણાંકો 6 છે
5, 1, 3, 8, 4, 7, 9, અને 2.

23
00:01:00,110 --> 00:01:03,480
પ્રથમ, અમે અંતિમ તત્વ પસંદ
આ એરે - આ કિસ્સામાં, બે -

24
00:01:03,480 --> 00:01:06,870
અને તે "ધરી." કૉલ પછી, આપણે
બે વસ્તુઓ જોવા શરૂ -

25
00:01:06,870 --> 00:01:10,220
એક, હું સંદર્ભ લો પડશે જે સૌથી ઓછી અનુક્રમણિકા,
અધિકાર છે માટે રહેતા તરીકે

26
00:01:10,220 --> 00:01:13,970
દિવાલ, અને, બે, પાંચ leftmost
હું "વર્તમાન કહી શકશો કે જે તત્વ છે,

27
00:01:13,970 --> 00:01:17,260
ઘટક. "અમે શું કરી રહ્યા છીએ છે
અન્ય બીજા બધા તત્વો, જુઓ

28
00:01:17,260 --> 00:01:20,930
ધરી કરતા, અને તમામ ઘટકો મૂકવા
આ માટે ધરી કરતા નાની

29
00:01:20,930 --> 00:01:24,140
દિવાલ છોડી અને તે બધા
આ માટે ધરી કરતાં મોટી

30
00:01:24,140 --> 00:01:25,570
દિવાલ અધિકાર.

31
00:01:25,570 --> 00:01:29,560
પછી, છેવટે, અમે ધરી મૂકવા પડશે
અધિકાર વચ્ચે મૂકવા કે દિવાલ પર

32
00:01:29,560 --> 00:01:32,970
તે કરતા નાની બધી સંખ્યાઓ
અને તમામ નંબરો મોટા.

33
00:01:32,970 --> 00:01:34,460
>> તેથી આપણે તે કરીએ.

34
00:01:34,460 --> 00:01:38,540
2 ચૂંટો, પાંચ પર દિવાલ મૂકી
શરૂઆત, અને 6 આ "વર્તમાન કૉલ

35
00:01:38,540 --> 00:01:41,590
ઘટક. "તો અમે જોવા માંગો છો
અમારા વર્તમાન તત્વ, 6.

36
00:01:41,590 --> 00:01:44,200
અને તે કરતાં મોટી છે કારણ કે
2, અમે ત્યાં છોડી

37
00:01:44,200 --> 00:01:45,610
દિવાલ અધિકાર.

38
00:01:45,610 --> 00:01:48,980
પછી, અમે તરીકે 5 જોવા પર ખસેડો અમારા
વર્તમાન તત્વ અને જુઓ કે આ

39
00:01:48,980 --> 00:01:51,840
ફરીથી, જો ધરી કરતાં મોટી છે, તેથી અમે
તે યોગ્ય છે કે જ્યાં છે એમ છોડી દો

40
00:01:51,840 --> 00:01:53,190
દિવાલ બાજુ.

41
00:01:53,190 --> 00:01:53,880
અમે ખસેડવા.

42
00:01:53,880 --> 00:01:56,750
અમારા વર્તમાન ઘટક છે
હવે 1, અને - ઓહ.

43
00:01:56,750 --> 00:01:58,030
આ હવે અલગ છે.

44
00:01:58,030 --> 00:02:00,890
વર્તમાન તત્વ હવે કરતા ઓછી છે
ધરી છે, તેથી અમે તે મૂકેલ

45
00:02:00,890 --> 00:02:02,570
દિવાલ ડાબી.

46
00:02:02,570 --> 00:02:06,555
આ કરવા માટે, આપણે માત્ર સ્વિચ દો
સૌથી ઓછી ઇન્ડેક્સ સાથે વર્તમાન તત્વ

47
00:02:06,555 --> 00:02:07,970
ફક્ત દિવાલ જમણી બેઠક.

48
00:02:07,970 --> 00:02:14,050

49
00:02:14,050 --> 00:02:17,570
હવે, અમે એક ઇન્ડેક્સ દિવાલ ખસેડો
જેથી 1 ડાબી પર છે

50
00:02:17,570 --> 00:02:19,750
હવે દીવાલ બાજુ.

51
00:02:19,750 --> 00:02:20,310
>> રાહ જુઓ.

52
00:02:20,310 --> 00:02:23,450
હું માત્ર પર તત્વો મિશ્ર
દિવાલ જમણી બાજુ, હું નથી કરી?

53
00:02:23,450 --> 00:02:23,890
ચિંતા કરશો નહીં.

54
00:02:23,890 --> 00:02:24,930
કે દંડ છે.

55
00:02:24,930 --> 00:02:27,570
અમે હવે વિશે કાળજી આ જ વસ્તુ
એ માટે આ તમામ તત્વો

56
00:02:27,570 --> 00:02:29,570
દિવાલ અધિકાર ઘણી મોટી હોય છે
ધરી કરતા.

57
00:02:29,570 --> 00:02:31,760
કોઈ વાસ્તવિક માટે હજુ સુધી ધારવામાં આવે છે.

58
00:02:31,760 --> 00:02:33,200
>> હવે, પાછા સૉર્ટ કરો.

59
00:02:33,200 --> 00:02:35,840
તેથી જો આપણે જોઈ પર ચાલુ
તત્વો બાકીના.

60
00:02:35,840 --> 00:02:39,075
અને આ કિસ્સામાં, અમે જુઓ કે
પાંચ કરતાં અન્ય તત્વો ઓછા

61
00:02:39,075 --> 00:02:42,100
ધરી છે, તેથી અમે તેમને બધા છોડી
દિવાલ જમણી બાજુ.

62
00:02:42,100 --> 00:02:45,980
છેલ્લે, અમે વર્તમાન તત્વ મેળવવા
અને તે ધરી છે કે નહીં તે જોવા.

63
00:02:45,980 --> 00:02:48,830
હવે, કે અમે બે હોય છે કે જે થાય છે
એરે, પ્રથમ હોવા વિભાગો

64
00:02:48,830 --> 00:02:51,820
ધરી પર અને ડાબી બાજુ પર નાના
દિવાલ, અને બીજા ક્રમે છે

65
00:02:51,820 --> 00:02:54,500
આ માટે ધરી કરતાં મોટી
દિવાલ જમણી બાજુ.

66
00:02:54,500 --> 00:02:57,040
અમે વચ્ચે ધરી તત્વ મૂકેલ
બે, અને પછી અમે ખબર પડશે

67
00:02:57,040 --> 00:03:01,000
ધરી તેના જમણા કે
અંતિમ છટણી સ્થાન.

68
00:03:01,000 --> 00:03:04,980
તેથી અમે પ્રથમ તત્વ સ્વિચ
ધરી સાથે દિવાલ જમણી બાજુ,

69
00:03:04,980 --> 00:03:06,410
અને આપણે જાણીએ છીએ ધરી માતાનો
તેની સાચી સ્થિતિમાં.

70
00:03:06,410 --> 00:03:11,130

71
00:03:11,130 --> 00:03:15,650
>> અમે પછી માટે આ પ્રક્રિયા પુનરાવર્તન
subarrays છોડી અને ધરી ઓફ અધિકાર.

72
00:03:15,650 --> 00:03:18,700
છેલ્લા subarray માત્ર એક જ છે
તત્વ લાંબા, અમે તે પહેલાથી જ ખબર

73
00:03:18,700 --> 00:03:22,480
છટણી તમે કેવી રીતે બહાર થઇ શકે છે
જો તમે માત્ર એક તત્વ છો ઓર્ડર?

74
00:03:22,480 --> 00:03:28,860
આ subarray જમણી બાજુ માટે, અમે
ધરી દિવાલ 5 છે, અને જુઓ કે

75
00:03:28,860 --> 00:03:32,250
માત્ર 6 બાકી છે.

76
00:03:32,250 --> 00:03:34,970
અને વર્તમાન તત્વ પણ
6 તરીકે બહાર શરૂ થાય છે.

77
00:03:34,970 --> 00:03:36,200
તેથી 6 5 કરતા વધારે છે.

78
00:03:36,200 --> 00:03:38,590
તે પર છે, જ્યાં અમે તેને છોડી
દિવાલ જમણી બાજુ.

79
00:03:38,590 --> 00:03:41,060
હવે, પર જતાં, 3 5 કરતાં ઓછી છે.

80
00:03:41,060 --> 00:03:44,160
તેથી અમે પ્રથમ તત્વ સાથે સ્વિચ
દિવાલ માત્ર અધિકાર.

81
00:03:44,160 --> 00:03:47,944

82
00:03:47,944 --> 00:03:50,750
હવે, હું એક દિવાલ ખસેડવામાં આવ્યા છે.

83
00:03:50,750 --> 00:03:53,010
હવે, 8 પર જતાં.

84
00:03:53,010 --> 00:03:56,480
8 5 કરતા વધારે છે
અને તેથી અમે તેને છોડી દો.

85
00:03:56,480 --> 00:03:58,720
આ 4 5 કરતાં ઓછી છે, તેથી અમે તે કરો.

86
00:03:58,720 --> 00:04:02,950

87
00:04:02,950 --> 00:04:03,570
અને પર.

88
00:04:03,570 --> 00:04:04,820
અને પર.

89
00:04:04,820 --> 00:04:10,190

90
00:04:10,190 --> 00:04:13,670
>> અમે પર પ્રક્રિયા પુનરાવર્તન દર વખતે
એરે ડાબી અને જમણી બાજુ. અમે

91
00:04:13,670 --> 00:04:17,010
એક ધરી પસંદ કરો અને સરખામણી કરો
અને બાકી અન્ય સ્તર બનાવવા અને

92
00:04:17,010 --> 00:04:18,240
અધિકાર subarrays.

93
00:04:18,240 --> 00:04:21,500
આ ફરી યાદ આવવું કોલ સુધી ચાલુ રહેશે
આપણે કરેલા જ્યારે પુર્ણ

94
00:04:21,500 --> 00:04:25,290
માં સમગ્ર એરે અપ વિ
લંબાઈ 1 માત્ર subarrays.

95
00:04:25,290 --> 00:04:28,060
ત્યાંથી, અમે એરે છટણી કરવામાં આવે છે
દરેક તત્વ છે, કારણ કે અંતે

96
00:04:28,060 --> 00:04:29,330
અમુક બિંદુએ, એક ધરી રહી.

97
00:04:29,330 --> 00:04:32,720
અન્ય શબ્દોમાં, દરેક તત્વ તરીકે, બધા
ડાબી નંબરો ઓછા હોય

98
00:04:32,720 --> 00:04:36,420
કિંમતો અને માટે બધી સંખ્યાઓ
અધિકાર વધારે કિંમતો છે.

99
00:04:36,420 --> 00:04:38,980
>> આ પદ્ધતિ ખૂબ જ સારી રીતે કામ કરે છે જો
પસંદ કરેલ ધરી છે નીચેની કોડ ગુમ

100
00:04:38,980 --> 00:04:41,930
લગભગ મધ્યમાં
યાદીમાં કિંમતો શ્રેણી.

101
00:04:41,930 --> 00:04:45,630
અમે ખસેડવા પછી આ છે, કે જે તેનો અર્થ એ થાય
ઘણા વિશે ત્યાં આસપાસ તત્વો,

102
00:04:45,630 --> 00:04:48,390
ધરી ડાબી તત્વો
જમણી ત્યાં તરીકે.

103
00:04:48,390 --> 00:04:52,380
અને ના વિભાજન અને જીતી પ્રકૃતિ
Quicksort અલ્ગોરિધમનો પછી લેવામાં આવે છે

104
00:04:52,380 --> 00:04:53,850
પૂર્ણ લાભ.

105
00:04:53,850 --> 00:04:57,500
આ ઓ એક રનટાઈમ બનાવે (n લોગ એન,)
અમે હોય તો n એ 1 બાદ પાંચ n એ, કારણ કે

106
00:04:57,500 --> 00:05:01,640
દરેક પેઢી અને લોગ પર તુલના
અમે યાદી વિભાજીત હોય n એ, કારણ કે

107
00:05:01,640 --> 00:05:03,210
n વખત લોગ.

108
00:05:03,210 --> 00:05:06,160
જો કે, સૌથી ખરાબ કિસ્સામાં,
અલ્ગોરિધમનો ખરેખર ઓ (n હોઈ શકે છે

109
00:05:06,160 --> 00:05:09,850
સ્ક્વેર્ડ.) દરેક પેઢી પર ધારો કે,
ધરી જ બને છે

110
00:05:09,850 --> 00:05:12,520
નાના અથવા તો સૌથી મોટી
અમે સૉર્ટ કરી રહ્યા છો નંબરો.

111
00:05:12,520 --> 00:05:15,870
આ યાદી તોડી તેનો અર્થ એ થાય
સમય અને નિર્માણ n એ ઓછા 1 N

112
00:05:15,870 --> 00:05:17,690
તુલના દરેક એક સમય.

113
00:05:17,690 --> 00:05:20,490
આમ, n ના ઓ સ્ક્વેર્ડ.

114
00:05:20,490 --> 00:05:22,000
>> અમે કેવી રીતે પદ્ધતિ સુધારી શકું?

115
00:05:22,000 --> 00:05:25,100
પદ્ધતિ સુધારવા માટે એક સારો માર્ગ છે
સંભાવના પર કાપવામાં કે

116
00:05:25,100 --> 00:05:28,150
આ રનટાઈમ ક્યારેય ખરેખર છે
સ્ક્વેર્ડ n ના ઓ.

117
00:05:28,150 --> 00:05:31,860
આ સૌથી ખરાબ, ખરાબ કેસ દૃશ્ય યાદ રાખો
માત્ર થાય છે જ્યારે

118
00:05:31,860 --> 00:05:35,320
પસંદ ધરી હંમેશા સૌથી વધુ છે
અથવા એરે સૌથી ઓછી કિંમત.

119
00:05:35,320 --> 00:05:38,630
આ ઓછી થાય તેવી શક્યતા છે તેની ખાતરી કરવા માટે,
અમે આ ધરી શોધી શકો છો

120
00:05:38,630 --> 00:05:42,610
ઘણા તત્વો અને પસંદ
મધ્ય કિંમત લેવા.

121
00:05:42,610 --> 00:05:44,650
>> મારું નામ, માર્ક Grozen-સ્મિથ છે
અને આ CS50 છે.

122
00:05:44,650 --> 00:05:47,790

123
00:05:47,790 --> 00:05:50,930
>> સરળતા માટે, ચાલો ધારે છે કે જેઓ
વસ્તુઓ માત્ર પૂર્ણાંકો હોય છે, પરંતુ

124
00:05:50,930 --> 00:05:51,970
કે Quicksert ખબર છે -

125
00:05:51,970 --> 00:05:53,160
Quicksert?

126
00:05:53,160 --> 00:05:55,200
માફ કરશો.

127
00:05:55,200 --> 00:06:02,000
>> અહીં અમે પૂર્ણાંકો છે
6, 5, 1, 3, 8, 4, 9.

128
00:06:02,000 --> 00:06:03,200
>> 1 વક્તા: ખરેખર?

129
00:06:03,200 --> 00:06:04,850
>> 2 વક્તા: ત્યાં બંધ ન કરો.

130
00:06:04,850 --> 00:06:06,100
>> 1 વક્તા: ખરેખર?

131
00:06:06,100 --> 00:06:08,491