1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] ટોમી: ચાલો પસંદગી સૉર્ટ પર એક નજર અલ્ગોરિધમ લેવા

2
00:00:09,980 --> 00:00:12,800
સંખ્યાની યાદી લઈને તેમને સોર્ટિંગ કરવા માટે.

3
00:00:12,800 --> 00:00:15,750
એક એલ્ગોરિધમ, યાદ રાખો કે, માત્ર એક પગલું દ્વારા પગલું છે

4
00:00:15,750 --> 00:00:18,370
એક કાર્ય પૂર્ણ કરવા માટે પ્રક્રિયા.

5
00:00:18,370 --> 00:00:21,470
પસંદગી સૉર્ટ પાછળનો મૂળ ખ્યાલ વિભાજિત છે

6
00:00:21,470 --> 00:00:23,390
બે વિભાગોમાં અમારા સૂચિ -

7
00:00:23,390 --> 00:00:26,810
એક છટણી ભાગ અને એક ક્રમમાંગોઠવાયેલનથી ભાગ.

8
00:00:26,810 --> 00:00:30,200
અલગોરિધમ દરેક પગલે, એક નંબર પરથી ખસેડવામાં આવે

9
00:00:30,200 --> 00:00:33,800
છેવટે સુધી છટણી ભાગ માટે ક્રમમાંગોઠવાયેલનથી ભાગ

10
00:00:33,800 --> 00:00:35,880
સમગ્ર યાદી સૉર્ટ થાય છે.

11
00:00:35,880 --> 00:00:38,510
તેથી અહીં છ નંબરોની યાદી છે -

12
00:00:38,510 --> 00:00:44,010
23, 42, 4, 16, 8, અને 15.

13
00:00:44,010 --> 00:00:47,680
હમણાં સમગ્ર યાદીમાં ક્રમમાંગોઠવાયેલનથી માનવામાં આવે છે.

14
00:00:47,680 --> 00:00:51,770
તેમ છતાં 16 જેવા નંબર પહેલેથી જ તેની યોગ્ય હોઈ શકે છે

15
00:00:51,770 --> 00:00:56,040
સ્થાન, અમારા અલગોરિધમ સુધી કે જાણીને કોઈ રીત છે

16
00:00:56,040 --> 00:00:57,980
સમગ્ર યાદી સૉર્ટ થાય છે.

17
00:00:57,980 --> 00:01:01,355
તેથી અમે દરેક નંબર માને છે ક્રમમાંગોઠવાયેલનથી કરી ત્યાં સુધી અમે સૉર્ટ પડશે

18
00:01:01,355 --> 00:01:03,800
તે જાતને.

19
00:01:03,800 --> 00:01:06,890
અમે જાણીએ છીએ કે અમે યાદી ચડતા ક્રમમાં કરવા માંગો છો.

20
00:01:06,890 --> 00:01:10,200
તેથી અમે અમારી યાદીમાં છટણી ભાગ બિલ્ડ કરવા માંગો છો પડશે

21
00:01:10,200 --> 00:01:13,280
ડાબેથી જમણી તરફ, સૌથી મોટી નાનું.

22
00:01:13,280 --> 00:01:17,970
કે કરવા માટે, અમે લઘુત્તમ ક્રમમાંગોઠવાયેલનથી તત્વ શોધવા જરૂર પડશે

23
00:01:17,970 --> 00:01:21,350
અને તે છટણી ભાગ ઓવરને અંતે મૂકો.

24
00:01:21,350 --> 00:01:25,370
આ યાદીમાં નથી છટણી કરવામાં આવે છે, જે માત્ર કે રસ્તો એ છે

25
00:01:25,370 --> 00:01:29,330
આ ક્રમમાંગોઠવાયેલનથી ભાગ દરેક તત્વ પર જુઓ, યાદ

26
00:01:29,330 --> 00:01:32,010
જે તત્વ સૌથી નીચો અને સરખામણી છે

27
00:01:32,010 --> 00:01:33,770
કે દરેક તત્વ.

28
00:01:33,770 --> 00:01:36,150
તેથી અમે પ્રથમ 23 એ જોવા મળશે.

29
00:01:36,150 --> 00:01:38,650
આ પ્રથમ તત્વ અમે જોયેલા છે, તેથી અમે યાદ પડશે

30
00:01:38,650 --> 00:01:40,050
તે ઓછામાં ઓછા છે.

31
00:01:40,050 --> 00:01:42,320
આગામી અમે 42 જોવા મળશે.

32
00:01:42,320 --> 00:01:46,720
42 23 કરતા મોટા છે, તેથી 23 હજુ પણ ઓછામાં ઓછા છે.

33
00:01:46,720 --> 00:01:51,210
આગળ 4 જે 23 કરતાં ઓછી હોય છે, તેથી અમે 4 યાદ પડશે

34
00:01:51,210 --> 00:01:52,880
નવા ન્યુનતમ.

35
00:01:52,880 --> 00:01:56,380
આગામી 16 જે 4 કરતાં મોટી છે, જેથી 4

36
00:01:56,380 --> 00:01:57,980
હજુ પણ ઓછામાં ઓછા છે.

37
00:01:57,980 --> 00:02:03,670
8 4 કરતાં મોટી છે, અને 15 4 કરતાં પણ મોટો છે, જેથી 4 હોવા જ જોઈએ

38
00:02:03,670 --> 00:02:05,980
નાના ક્રમમાંગોઠવાયેલનથી તત્વ.

39
00:02:05,980 --> 00:02:09,350
તેથી ભલે મનુષ્યો અમે તરત જ જુઓ કે 4 શકે છે

40
00:02:09,350 --> 00:02:12,300
લઘુત્તમ તત્વ, અમારા અલગોરિધમ માટે જોવા જરૂર

41
00:02:12,300 --> 00:02:15,710
દરેક ક્રમમાંગોઠવાયેલનથી તત્વ, પણ પછી અમે 4 એ શોધ્યું છે - તે

42
00:02:15,710 --> 00:02:16,860
ન્યૂનતમ તત્વ.

43
00:02:16,860 --> 00:02:19,900
તેથી હવે અમે લઘુત્તમ તત્વ, 4 મળ્યાં છે, અમે માંગો છો પડશે

44
00:02:19,900 --> 00:02:23,410
તેને યાદીમાં છટણી ભાગ ખસેડો.

45
00:02:23,410 --> 00:02:27,320
જ્યારથી આ પ્રથમ પગલું છે, એનો અર્થ અમે અંતે 4 મૂકેલ

46
00:02:27,320 --> 00:02:29,680
યાદી શરૂઆત.

47
00:02:29,680 --> 00:02:33,040
23 હમણાં યાદી શરૂઆતમાં આવું છે,

48
00:02:33,040 --> 00:02:36,080
ચાલો આ 4 અને 23 ના સ્વેપ.

49
00:02:36,080 --> 00:02:38,870
તેથી હવે અમારી યાદી આ જેવો દેખાય છે.

50
00:02:38,870 --> 00:02:42,710
અમે જાણીએ છીએ કે 4 તેના અંતિમ સ્થાન હોવું જ જોઈએ, કારણ કે તે છે

51
00:02:42,710 --> 00:02:45,890
બન્ને નાના અને શરૂઆતમાં તત્વ તત્વ

52
00:02:45,890 --> 00:02:46,960
આ યાદીમાં છે.

53
00:02:46,960 --> 00:02:50,650
આ અર્થ કે જેથી અમે ક્યારેય તેને ફરીથી ખસેડવા જરૂર નથી.

54
00:02:50,650 --> 00:02:53,910
તેથી આપણે આ પ્રક્રિયા પુનરાવર્તન કરવા માટે અન્ય તત્વ ઉમેરો

55
00:02:53,910 --> 00:02:55,910
યાદીમાં છટણી ભાગ.

56
00:02:55,910 --> 00:02:58,950
અમે જાણીએ છીએ કે અમે 4 એ જોવા જરૂર નથી, કારણ કે તે

57
00:02:58,950 --> 00:03:00,000
પહેલેથી સોર્ટ થાય છે.

58
00:03:00,000 --> 00:03:03,540
તેથી અમે 42 એ શરૂ થાય છે, જેને આપણે તરીકે યાદ શકો છો

59
00:03:03,540 --> 00:03:05,290
ન્યૂનતમ તત્વ.

60
00:03:05,290 --> 00:03:08,700
અમે આગામી તેથી અમે 23 કે જેને 42 કરતાં ઓછી હોય જોવા કરીશું, જેથી

61
00:03:08,700 --> 00:03:11,620
યાદ 23 નવા લઘુત્તમ છે.

62
00:03:11,620 --> 00:03:14,870
આગામી અમે 16 જે 23 કરતાં ઓછી છે, જેથી જુઓ,

63
00:03:14,870 --> 00:03:16,800
16 નવા લઘુત્તમ છે.

64
00:03:16,800 --> 00:03:19,720
હવે અમે 8 જેમાં 16 કરતા પણ ઓછી છે, જેથી જુઓ,

65
00:03:19,720 --> 00:03:21,130
8 નવા લઘુત્તમ છે.

66
00:03:21,130 --> 00:03:25,900
અને 8 આખરે 15 કરતાં ઓછી છે, તેથી આપણે જાણીએ છીએ કે 8 ઓછામાં ઓછા છે

67
00:03:25,900 --> 00:03:27,780
ક્રમમાંગોઠવાયેલનથી તત્વ.

68
00:03:27,780 --> 00:03:30,660
તેથી તેનો અર્થ એ કે અમે 8 ના છટણી માટે ઉમેરી જોઈએ

69
00:03:30,660 --> 00:03:32,450
યાદીમાં ભાગ.

70
00:03:32,450 --> 00:03:35,990
હમણાં જ એક માત્ર 4 છટણી તત્વ છે, તેથી અમે મૂકવા માંગો છો

71
00:03:35,990 --> 00:03:38,410
આ 8 એ માટે 4 આગામી.

72
00:03:38,410 --> 00:03:41,920
42 હોવાના ના ક્રમમાંગોઠવાયેલનથી ભાગ પ્રથમ તત્વ છે

73
00:03:41,920 --> 00:03:47,260
યાદી, અમે 42 અને 8 ના સ્વેપ કરવા માંગો છો પડશે.

74
00:03:47,260 --> 00:03:49,680
તેથી હવે અમારી યાદી આ જેવો દેખાય છે.

75
00:03:49,680 --> 00:03:53,830
4 અને 8 યાદીમાં છટણી ભાગ પ્રતિનિધિત્વ કરે છે, અને

76
00:03:53,830 --> 00:03:56,440
બાકી નંબરો ક્રમમાંગોઠવાયેલનથી પ્રતિનિધિત્વ

77
00:03:56,440 --> 00:03:58,260
યાદીમાં ભાગ.

78
00:03:58,260 --> 00:04:00,630
તેથી આપણે અન્ય પુનરાવૃત્તિ સાથે ચાલુ રાખો.

79
00:04:00,630 --> 00:04:03,850
અમે 23 સાથે આ સમય શરૂ કરવા માટે, કારણ કે અમે જોવા જરૂર નથી

80
00:04:03,850 --> 00:04:05,770
4 અને હવે 8 કારણ કે તેઓ કરેલા

81
00:04:05,770 --> 00:04:07,660
પહેલેથી જ છટણી કરવામાં આવી છે.

82
00:04:07,660 --> 00:04:10,270
16 23 કરતા પણ ઓછી છે, તેથી અમે યાદ પડશે

83
00:04:10,270 --> 00:04:12,070
16 નવા ન્યુનતમ.

84
00:04:12,070 --> 00:04:18,149
16 42 કરતા પણ ઓછી છે, પરંતુ 15 16 કરતા પણ ઓછી છે, તેથી 15 જ હોવી જોઈએ

85
00:04:18,149 --> 00:04:20,480
લઘુત્તમ ક્રમમાંગોઠવાયેલનથી તત્વ.

86
00:04:20,480 --> 00:04:24,580
તેથી હવે અમે 15 અને 23 ને સ્વેપ કરવા માંગો છો

87
00:04:24,580 --> 00:04:26,310
અમને આ યાદી આપે છે.

88
00:04:26,310 --> 00:04:30,500
યાદીમાં છટણી ભાગ 8 4, અને 15 નો સમાવેશ થાય છે, અને

89
00:04:30,500 --> 00:04:33,210
આ તત્વો હજુ પણ ક્રમમાંગોઠવાયેલનથી છે.

90
00:04:33,210 --> 00:04:36,900
પરંતુ તે જ બને છે કે આગામી ક્રમમાંગોઠવાયેલનથી તત્વ, 16,

91
00:04:36,900 --> 00:04:38,480
પહેલાંથી જ સોર્ટ થાય છે.

92
00:04:38,480 --> 00:04:42,060
જો કે, ત્યાં અમારા અલગોરિધમ માટે કોઈ રીત છે તે જાણવા માટે કે 16

93
00:04:42,060 --> 00:04:45,230
તેના યોગ્ય સ્થાન પહેલેથી જ છે, તેથી અમે હજુ પણ જરૂર

94
00:04:45,230 --> 00:04:47,870
બરાબર એ જ પ્રક્રિયા પુનરાવર્તન કરો.

95
00:04:47,870 --> 00:04:53,750
તેથી અમે જુઓ કે 16 42 કરતાં ઓછી છે, અને 16 23 કરતાં ઓછી છે, જેથી

96
00:04:53,750 --> 00:04:56,230
16 લઘુત્તમ તત્વ હોવા જ જોઈએ.

97
00:04:56,230 --> 00:04:59,010
તે અશક્ય છે કે પોતે આ તત્વ સ્વેપ તેથી, અમે આ કરી શકો છો

98
00:04:59,010 --> 00:05:01,780
ફક્ત તે આ સ્થાન છોડી દો.

99
00:05:01,780 --> 00:05:04,660
જેથી અમે અમારા અલગોરિધમ એક વધુ પાસ કરવાની જરૂર છે.

100
00:05:04,660 --> 00:05:09,370
42 23 કરતા વધારે છે, તેથી 23 એ જ હોવી જોઈએ

101
00:05:09,370 --> 00:05:10,970
ન્યૂનતમ ક્રમમાંગોઠવાયેલનથી તત્વ.

102
00:05:10,970 --> 00:05:17,410
એકવાર અમે 23 અને 42 ના સ્વેપ, અમે અમારી અંતિમ સાથે અંત

103
00:05:17,410 --> 00:05:18,530
છટણી યાદી -

104
00:05:18,530 --> 00:05:23,390
4, 8, 15, 16, 23, 42.

105
00:05:23,390 --> 00:05:26,830
અમે જાણીએ 42 યોગ્ય સ્થાને હોઈ કારણ કે તે હોવું જ જોઈએ

106
00:05:26,830 --> 00:05:30,210
માત્ર તત્વ બાકી છે, અને તે પસંદગી સૉર્ટ છે.

107
00:05:30,210 --> 00:05:32,100
ચાલો હવે કેટલાક અમારા અલગોરિધમ નિશ્ચિત સ્વરૂપ આપવું

108
00:05:32,100 --> 00:05:34,540
સ્યુડોકોડનો.

109
00:05:34,540 --> 00:05:37,760
એક લીટી પર, અમે જોઈ શકો છો કે અમે ઉપર સંકલિત કરવાની જરૂર

110
00:05:37,760 --> 00:05:39,530
યાદી દરેક તત્વ.

111
00:05:39,530 --> 00:05:42,150
છેલ્લા તત્વ સિવાય, ત્યારથી 1 તત્વ

112
00:05:42,150 --> 00:05:44,230
યાદી પહેલેથી સૉર્ટ થાય છે.

113
00:05:44,230 --> 00:05:48,100
બે લીટી પર, અમે ક્રમમાંગોઠવાયેલનથી પ્રથમ તત્વ ધ્યાનમાં

114
00:05:48,100 --> 00:05:51,080
યાદીમાં ભાગ લઘુત્તમ છે, કારણ કે અમે અમારા સાથે કર્યું

115
00:05:51,080 --> 00:05:53,750
ઉદાહરણ તરીકે, તેથી અમે સાથે સરખામણી કંઈક હોય છે.

116
00:05:53,750 --> 00:05:57,260
ત્રણ લીટી બીજા લૂપ છીએ, જેમાં આપણે ઉપર ફરી વળવું શરૂ થાય છે

117
00:05:57,260 --> 00:05:59,170
દરેક ક્રમમાંગોઠવાયેલનથી તત્વ.

118
00:05:59,170 --> 00:06:02,150
અમે જાણીએ છીએ કે હું iterations પછી, સોર્ટ ભાગ

119
00:06:02,150 --> 00:06:05,330
અમારા યાદી દરેક પગલું થી હું તેને તત્વો હોવી જ જોઈએ

120
00:06:05,330 --> 00:06:06,890
એક તત્વ ગોઠવે છે.

121
00:06:06,890 --> 00:06:11,770
જેથી પ્રથમ ક્રમમાંગોઠવાયેલનથી તત્વ હું વત્તા 1 સ્થિતિમાં જ હોવી જોઈએ.

122
00:06:11,770 --> 00:06:15,440
ચાર લીટી પર, અમે લઘુત્તમ કરવા માટે વર્તમાન તત્વ તુલના

123
00:06:15,440 --> 00:06:17,750
તત્વ કે અમે અત્યાર સુધી જોઇ છે.

124
00:06:17,750 --> 00:06:20,560
જો વર્તમાન તત્વ લઘુત્તમ કરતા ઓછી છે

125
00:06:20,560 --> 00:06:23,870
તત્વ, તો પછી અમે નવા તરીકે વર્તમાન તત્વ યાદ

126
00:06:23,870 --> 00:06:26,250
પાંચ લાઇન પર ન્યૂનતમ.

127
00:06:26,250 --> 00:06:29,900
છેલ્લે, છ અને સાત રેખાઓ પર, અમે ન્યૂનતમ સ્વેપ

128
00:06:29,900 --> 00:06:33,080
પ્રથમ ક્રમમાંગોઠવાયેલનથી તત્વ સાથે ત્યાં તત્વ,

129
00:06:33,080 --> 00:06:36,990
તે યાદીમાં છટણી ભાગ ઉમેરી રહ્યા હોય.

130
00:06:36,990 --> 00:06:40,030
એકવાર અમે અલ્ગોરિધમ છે, એક મહત્વપૂર્ણ પ્રશ્ન પૂછી

131
00:06:40,030 --> 00:06:43,370
જાતને પ્રોગ્રામરો સુધી કેવી રીતે છે લીઘા હતા?

132
00:06:43,370 --> 00:06:46,970
અમે પ્રથમ પ્રશ્ન પૂછવા પડશે લાંબા તે કેવી રીતે આ માટે લે

133
00:06:46,970 --> 00:06:50,070
અલ્ગોરિધમનો ખરાબ કેસ ચલાવવા માટે?

134
00:06:50,070 --> 00:06:51,640
રિકોલ અમે આ દોડ પ્રતિનિધિત્વ

135
00:06:51,640 --> 00:06:55,060
મોટું ઓ નોટેશનમાં સાથે સમય.

136
00:06:55,060 --> 00:06:58,650
ક્રમમાં લઘુત્તમ ક્રમમાંગોઠવાયેલનથી તત્વ નક્કી કરવા માટે અમે,

137
00:06:58,650 --> 00:07:01,880
અનિવાર્યપણે કરવા માટે યાદી દરેક તત્વ સરખાવવા હતી

138
00:07:01,880 --> 00:07:04,040
યાદીમાં દરેક અન્ય તત્વ.

139
00:07:04,040 --> 00:07:08,430
તર્ક, એન સ્ક્વેર્ડ કામગીરીના એક ઓ જેવી આ ધ્વનિઓ.

140
00:07:08,430 --> 00:07:12,050
અમારા સ્યુડોકોડનો અંતે છીએ, અમે પણ અંદર નેસ્ટ લૂપ છે

141
00:07:12,050 --> 00:07:14,420
અન્ય, એક ઓ જેવા લૂપ જે ખરેખર લાગે

142
00:07:14,420 --> 00:07:16,480
n સ્ક્વેર્ડ ઓપરેશન.

143
00:07:16,480 --> 00:07:19,250
જોકે યાદ રાખો કે અમે જોશે જરૂર ન હતી

144
00:07:19,250 --> 00:07:23,460
સમગ્ર યાદી જ્યારે લઘુત્તમ ક્રમમાંગોઠવાયેલનથી તત્વ નક્કી?

145
00:07:23,460 --> 00:07:26,600
એકવાર અમે જાણતા હતા કે 4 છટણી કરવામાં આવી હતી, ઉદાહરણ તરીકે કર્યું છે, તો અમે નથી

146
00:07:26,600 --> 00:07:28,170
તેને ફરીથી જોવાની જરૂર નથી.

147
00:07:28,170 --> 00:07:31,020
તેથી આ ચાલી રહેલ સમય નથી નીચલા?

148
00:07:31,020 --> 00:07:34,510
6 લંબાઈ અમારી યાદી માટે, અમે પાંચ બનાવવા જરૂરી

149
00:07:34,510 --> 00:07:37,990
પ્રથમ તત્વ માટે સરખામણીઓ માટે ચાર સરખામણીઓ

150
00:07:37,990 --> 00:07:40,750
બીજા તત્વ, અને તેથી પર.

151
00:07:40,750 --> 00:07:44,690
એટલે કે પગલાંઓ કુલ સંખ્યા સરવાળો છે

152
00:07:44,690 --> 00:07:49,160
1 થી 1 બાદ યાદી લંબાઈ માટે પૂર્ણાંકો.

153
00:07:49,160 --> 00:07:51,005
અમે એક શ્રેઢી સાથે આ પ્રતિનિધિત્વ કરી શકે છે.

154
00:07:57,980 --> 00:07:59,910
અમે summations માં અહીં જશે.

155
00:07:59,910 --> 00:08:04,900
પરંતુ તે તારણ છે કે જે આ શ્રેઢી n વખત સમાન છે

156
00:08:04,900 --> 00:08:07,540
n બાદ 1 2 બનાવ્યા.

157
00:08:07,540 --> 00:08:14,220
અથવા સમકક્ષ, એન 2 પર ઓછા 2 પર n ચોરસ.

158
00:08:14,220 --> 00:08:18,860
જ્યારે અનંત સ્પર્શી રનટાઈમ વિશે વાત, આ n સ્ક્વેર્ડ પદ

159
00:08:18,860 --> 00:08:22,070
છે આ n એ શબ્દ પર પ્રભુત્વ હોય છે.

160
00:08:22,070 --> 00:08:27,850
તેથી પસંદગી સૉર્ટ n સ્ક્વેર્ડ ઓફ ઓ છે.

161
00:08:27,850 --> 00:08:31,460
જણાવ્યું હતું કે અમારા ઉદાહરણમાં, પસંદગી સૉર્ટ કરવા માટે હજુ પણ જરૂરી

162
00:08:31,460 --> 00:08:33,850
તપાસો જો એ સંખ્યા છે કે પહેલેથી જ છટણી કરવામાં આવી હતી

163
00:08:33,850 --> 00:08:35,450
ખસેડવામાં આવશે જરૂર છે.

164
00:08:35,450 --> 00:08:38,929
જેથી અર્થ એ થાય કે જો અમે પહેલાથી જ પસંદગી સૉર્ટ ચાલી હતી

165
00:08:38,929 --> 00:08:43,070
યાદી છટણી, તેને તરીકે પગલાંઓ જ નંબર જરૂરી છે

166
00:08:43,070 --> 00:08:46,340
છો જ્યારે સંપૂર્ણપણે ક્રમમાંગોઠવાયેલનથી યાદી પર દોડે છે.

167
00:08:46,340 --> 00:08:51,470
તેથી પસંદગી સૉર્ટ એક શ્રેષ્ઠ સ્ક્વેર્ડ n ના કેસ કામગીરી ધરાવે છે,

168
00:08:51,470 --> 00:08:56,820
જે અમે ઓમેગા સ્ક્વેર્ડ n સાથે પ્રતિનિધિત્વ કરે છે.

169
00:08:56,820 --> 00:08:58,600
અને તે પસંદગી સૉર્ટ માટે છે.

170
00:08:58,600 --> 00:09:00,630
જસ્ટ ઘણા એલ્ગોરિધમ્સ અમે કરી શકો છો એક

171
00:09:00,630 --> 00:09:02,390
એક યાદી સૉર્ટ વાપરો.

172
00:09:02,390 --> 00:09:05,910
મારું નામ ટોમી છે, અને આ cs50 છે.