1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [નિવેશ સૉર્ટ કરો]

2
00:00:02,290 --> 00:00:04,240
[ટોમી MacWilliam] [હાર્વર્ડ યુનિવર્સિટી]

3
00:00:04,240 --> 00:00:07,290
[આ CS50.TV છે]

4
00:00:07,290 --> 00:00:13,060
ચાલો નિવેશ સૉર્ટ પર એક નજર, નંબરો યાદી લેતા અને તેમને સોર્ટિંગ કરવા માટે એક એલ્ગોરિધમ લો.

5
00:00:13,060 --> 00:00:18,300
એક એલ્ગોરિધમ, યાદ રાખો કે, માત્ર એક કાર્ય પૂર્ણ કરવા માટે પ્રક્રિયા પગલું દ્વારા પગલું છે.

6
00:00:18,300 --> 00:00:23,640
નિવેશ સૉર્ટ પાછળનો મૂળ વિચાર, બે વિભાગોમાં વિભાજિત અમારા યાદી છે,

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

8
00:00:26,580 --> 00:00:29,290
>> અલગોરિધમ દરેક પગલે, એક નંબર ખસેડવામાં આવે

9
00:00:29,290 --> 00:00:32,439
આ ક્રમમાંગોઠવાયેલનથી ભાગ ના છટણી ભાગ

10
00:00:32,439 --> 00:00:35,680
છેવટે સુધી સમગ્ર યાદીમાં સૉર્ટ થાય છે.

11
00:00:35,680 --> 00:00:43,340
23, 42, 4, 16, 8, અને 15 - અહીં છ ક્રમમાંગોઠવાયેલનથી સંખ્યાની યાદી છે.

12
00:00:43,340 --> 00:00:47,680
કારણ કે આ નંબરો તમામ ચડતા ક્રમમાં ન હોય તો, તેઓ ક્રમમાંગોઠવાયેલનથી કરી રહ્યાં છો.

13
00:00:47,680 --> 00:00:53,890
કારણ કે આપણે હજુ સુધી વર્ગીકરણ નથી શરૂ કર્યું છે, અમે બધા છ ઘટકો અમારા ક્રમમાંગોઠવાયેલનથી ભાગ ધ્યાનમાં રાખીશું.

14
00:00:53,890 --> 00:00:59,270
>> એકવાર અમે સૉર્ટ શરૂ કરવા માટે, અમે આ છટણી નંબરો આ ડાબી મૂકીશું.

15
00:00:59,270 --> 00:01:03,600
તેથી, ચાલો 23, અમારા યાદીમાં પ્રથમ તત્વ સાથે શરુ થાય છે.

16
00:01:03,600 --> 00:01:06,930
અમે અમારા છટણી ભાગ કોઇ પણ તત્વો હજુ સુધી નથી,

17
00:01:06,930 --> 00:01:12,460
તેથી આપણે માત્ર 23 વિચારણા કરવા માટે અને અમારા છટણી ભાગ ના પ્રારંભ ઓવરને છે.

18
00:01:12,460 --> 00:01:16,510
હવે, અમારા છટણી ભાગ એક નંબર, 23 હોય છે,

19
00:01:16,510 --> 00:01:20,260
અને અમારા ક્રમમાંગોઠવાયેલનથી ભાગ આ પાંચ નંબરો છે.

20
00:01:20,260 --> 00:01:27,320
ચાલો હવે અમારી ક્રમમાંગોઠવાયેલનથી ભાગ, 42 માં સોર્ટ ભાગ માં આગામી નંબર દાખલ કરો.

21
00:01:27,320 --> 00:01:35,930
>> આમ કરવા માટે, અમે 23 માટે 42 તુલના કરવાની જરૂર પડશે - અમારા છટણી ભાગ માં માત્ર તત્વ અત્યાર સુધી.

22
00:01:35,930 --> 00:01:41,980
બેતાલીસ 23 કરતા વધારે હોય છે, તેથી અમે ફક્ત અંતે 42 ઉમેરી શકો છો

23
00:01:41,980 --> 00:01:45,420
યાદીમાં છટણી ભાગ છે. સરસ!

24
00:01:45,420 --> 00:01:51,850
હવે અમારા છટણી ભાગ બે ઘટકો હોય છે, અને અમારા ક્રમમાંગોઠવાયેલનથી ભાગ ચાર તત્વો ધરાવે છે.

25
00:01:51,850 --> 00:01:57,200
તેથી, ચાલો હવે 4 માટે ખસેડવા માટે, ક્રમમાંગોઠવાયેલનથી ભાગ આગામી તત્વ.

26
00:01:57,200 --> 00:02:00,230
તેથી, જ્યાં આ છટણી ભાગ મૂકવામાં આવવો જોઈએ?

27
00:02:00,230 --> 00:02:04,220
>> યાદ રાખો, અમે ક્રમમાં આ નંબર મૂકવા માંગો છો

28
00:02:04,220 --> 00:02:08,680
તેથી અમારા છટણી ભાગ યોગ્ય રીતે બધી સમયે છટણી રહે છે.

29
00:02:08,680 --> 00:02:14,380
જો અમે 42 ના અધિકાર માટે 4 મૂકો, તો પછી અમારી યાદી દોષિત હશે.

30
00:02:14,380 --> 00:02:18,380
તેથી, ચાલો અમારા સૉર્ટ ભાગમાં જમણે થી ડાબે ખસેડવા ચાલુ રાખો.

31
00:02:18,380 --> 00:02:23,260
આપણે ખસેડવા, ચાલો એક સ્થાન નીચે દરેક નંબર પાળી નવા નંબર માટે જગ્યા કરી શકાય.

32
00:02:25,440 --> 00:02:31,740
ઠીક, 4 પણ 23 કરતા ઓછી છે, તેથી અમે તેને અહીં મૂકો ક્યાં કરી શકે છે.

33
00:02:31,740 --> 00:02:34,480
ચાલો એવા 23 અધિકાર એક જ જગ્યાએ ખસેડો.

34
00:02:36,500 --> 00:02:43,120
>> તેનો અર્થ એ કે અમે છટણી ભાગ પ્રથમ સ્લોટ માં 4 મૂકવા માંગો છો.

35
00:02:43,120 --> 00:02:46,300
નોંધ કેવી રીતે યાદી આ જગ્યા પહેલાથી જ ખાલી,

36
00:02:46,300 --> 00:02:51,120
કારણ કે અમે છટણી કરવામાં તત્વો ખસેડીને કરી છે ડાઉન તરીકે અમે તેમને આવી.

37
00:02:51,120 --> 00:02:52,740
અધિકાર છે. તેથી, અમે હાફવે ત્યાં છો.

38
00:02:52,740 --> 00:02:57,990
ચાલો આ છટણી ભાગ માં 16 ના દાખલ કરીને અમારી અલ્ગોરિધમનો ચાલુ રાખો.

39
00:02:59,260 --> 00:03:03,820
સોળ ઓછા 42 કરતાં, તેથી આપણે જમણી 42 પાળી.

40
00:03:05,700 --> 00:03:10,190
સોળ પણ ઓછા 23 કરતાં, તેથી આપણે પણ તે તત્વ પાળી.

41
00:03:11,790 --> 00:03:20,820
>> હવે, 16 4 કરતા વધારે છે. તેથી, લાગે છે કે અમે 4 અને 23 વચ્ચે 16 એ દાખલ કરવા માંગો છો.

42
00:03:20,820 --> 00:03:24,620
જ્યારે યાદીમાં છટણી ભાગ મારફતે જમણેથી ડાબી તરફ સ્થળાંતર,

43
00:03:24,620 --> 00:03:29,160
4 પ્રથમ નંબર આપણે જોયું છે કે આ સંખ્યા કરતા ઓછી છે

44
00:03:29,160 --> 00:03:31,540
અમે દાખલ કરવાનો પ્રયાસ કરી રહ્યાં છો.

45
00:03:31,540 --> 00:03:35,820
તેથી, હવે અમે આ ખાલી સ્લોટ માં 16 દાખલ કરી શકો છો,

46
00:03:35,820 --> 00:03:40,520
જે, યાદ રાખો, અમે ફરતા તત્વો દ્વારા સૉર્ટ ભાગમાં પર બનાવેલ

47
00:03:40,520 --> 00:03:43,340
અમે તેમને આવી.

48
00:03:43,340 --> 00:03:47,900
>> અધિકાર છે. હવે, અમે ચાર છટણી તત્વો અને બે ક્રમમાંગોઠવાયેલનથી તત્વો હોય છે.

49
00:03:47,900 --> 00:03:51,600
તેથી, ચાલો આ છટણી ભાગ માં 8 ના ખસેડો.

50
00:03:51,600 --> 00:03:55,010
આઠ 42 કરતાં ઓછી છે.

51
00:03:55,010 --> 00:03:56,940
આઠ 23 કરતાં ઓછી છે.

52
00:03:56,940 --> 00:04:00,230
અને 8 16 કરતાં ઓછી છે.

53
00:04:00,230 --> 00:04:03,110
પરંતુ 8 4 કરતા વધારે છે.

54
00:04:03,110 --> 00:04:07,280
તેથી, અમે 4 અને 16 વચ્ચે 8 ના સામેલ કરવા માંગો છો.

55
00:04:09,070 --> 00:04:13,650
15 ના - અને હવે અમે માત્ર એક વધુ બાકી તત્વ સૉર્ટ કરવા માટે હોય છે.

56
00:04:13,950 --> 00:04:16,589
પંદર 42 કરતાં ઓછી છે,

57
00:04:16,589 --> 00:04:19,130
પંદર 23 કરતાં ઓછી છે.

58
00:04:19,130 --> 00:04:21,750
અને 15 16 કરતા પણ ઓછી છે.

59
00:04:21,750 --> 00:04:24,810
પરંતુ 15 8 કરતા વધારે છે.

60
00:04:24,810 --> 00:04:27,440
>> તેથી, અહીં છે જ્યાં અમે અમારી અંતિમ નિવેશ બનાવવા માંગો છો.

61
00:04:28,770 --> 00:04:30,330
અને અમે પૂર્ણ કરી લીધું.

62
00:04:30,330 --> 00:04:33,540
અમે ક્રમમાંગોઠવાયેલનથી ભાગ કોઇ અધિક તત્વો હોય છે,

63
00:04:33,540 --> 00:04:36,670
અને અમારા છટણી ભાગ યોગ્ય ક્રમમાં છે.

64
00:04:36,670 --> 00:04:40,270
આ સંખ્યામાં માંથી નાનું સૌથી મોટી આદેશ આપ્યો છે.

65
00:04:40,270 --> 00:04:44,330
તેથી, ચાલો કેટલાક સ્યુડોકોડનો કે પગલાંઓ અમે કરવામાં વર્ણવે પર એક નજર.

66
00:04:46,760 --> 00:04:51,740
>> 1 વાક્ય પર, અમે જોઈ શકો છો કે અમે ઉપર યાદીમાં દરેક તત્વ ફરી વળવું જરૂર પડશે

67
00:04:51,740 --> 00:04:57,060
પ્રથમ, તે સિવાય આ ક્રમમાંગોઠવાયેલનથી ભાગ પ્રથમ તત્વ થી ખાલી થઈ જશે

68
00:04:57,060 --> 00:05:00,220
આ છટણી ભાગ પ્રથમ તત્વ.

69
00:05:00,220 --> 00:05:06,320
2 રેખાઓ અને 3 પર, અમે અમારી ક્રમમાંગોઠવાયેલનથી ભાગમાં વર્તમાન સ્થળ ટ્રૅક રાખી રહ્યાં છે.

70
00:05:06,320 --> 00:05:10,450
તત્વ સંખ્યા અમે હાલમાં છટણી ભાગ તરફ વળી રહ્યા છે રજૂ કરે છે,

71
00:05:10,450 --> 00:05:15,600
અને એ જ ક્રમમાંગોઠવાયેલનથી ભાગ અમારા ઇન્ડેક્સ રજૂ કરે છે.

72
00:05:15,600 --> 00:05:20,980
>> 4 વાક્ય પર, અમે છટણી જમણેથી ડાબી ભાગ વારો કરી રહ્યાં છો.

73
00:05:20,980 --> 00:05:26,010
અમે તત્વ એકવાર અમારી વર્તમાન સ્થિતિ ડાબી વારો રોકવા માંગો છો

74
00:05:26,010 --> 00:05:30,050
તત્વ અમે દાખલ પ્રયાસ કરી રહ્યા છો તેના કરતાં ઓછી છે.

75
00:05:30,050 --> 00:05:35,600
5 રેખા પર, અમે દરેક તત્વ અમે જમણી એક જગ્યા મળે સ્થળાંતર કરી રહ્યા છો.

76
00:05:35,600 --> 00:05:40,950
તે રીતે, અમે સ્પષ્ટ દાખલ જગ્યા છે જ્યારે અમે પ્રથમ તત્વ મળશે

77
00:05:40,950 --> 00:05:44,080
તત્વ અમે ખસેડીએ છીએ કરતાં ઓછો હોય છે.

78
00:05:44,080 --> 00:05:50,800
6 વાક્ય પર, અમે અમારી કાઉન્ટર અપડેટ કરી રહ્યા છો તે માટે છટણી ભાગ દ્વારા છોડી ખસેડવા ચાલુ રાખો.

79
00:05:50,800 --> 00:05:56,860
છેલ્લે, 7 વાક્ય પર, અમે યાદીમાં છટણી ભાગ માં તત્વ દાખલ કરી રહ્યા છો.

80
00:05:56,860 --> 00:06:00,020
>> અમે જાણીએ છીએ કે તે સ્થિતિમાં જ દાખલ ઠીક છે,

81
00:06:00,020 --> 00:06:05,360
કારણ કે અમે પહેલાથી જ તત્વ છે કે જે ત્યાં જમણી એક જગ્યા હોવી ઉપયોગ ખસેડી દીધું છે.

82
00:06:05,360 --> 00:06:09,460
યાદ રાખો, આપણે અધિકાર ના છટણી ભાગ મારફતે ડાબી તરફ સ્થળાંતર કરી રહ્યાં છો,

83
00:06:09,460 --> 00:06:13,960
પરંતુ અમે ડાબી જમણી ક્રમમાંગોઠવાયેલનથી ભાગ દ્વારા ફરતા રહ્યા છો.

84
00:06:13,960 --> 00:06:19,090
અધિકાર છે. ચાલો હવે લાંબા કેવી રીતે ચાલી રહ્યું છે કે અલ્ગોરિધમનો લીધો પર એક નજર.

85
00:06:19,090 --> 00:06:25,300
અમે પ્રથમ પ્રશ્ન પૂછો લાંબા તે કેવી રીતે માટે આ અલ્ગોરિધમનો ખરાબ કેસ ચલાવવા માટે લે પડશે.

86
00:06:25,300 --> 00:06:29,040
યાદ છે કે અમે મોટા ઓ નોટેશનમાં સાથે આ ચાલી રહેલ સમય દર્શાવે છે.

87
00:06:32,530 --> 00:06:38,500
ક્રમમાં અમારા સૂચિ સૉર્ટ કરવા માટે, અમારે પર ક્રમમાંગોઠવાયેલનથી ભાગ માં તત્વો ફરી વળવું હતી,

88
00:06:38,500 --> 00:06:43,430
અને તે તત્વોના છટણી ભાગ તમામ તત્વો પર સંભવિત, દરેક માટે.

89
00:06:43,430 --> 00:06:47,950
તર્ક, એક ઓ કામગીરી (n ^ 2) જેવી આ ધ્વનિઓ.

90
00:06:47,950 --> 00:06:51,840
>> અમારા સ્યુડોકોડનો અંતે છીએ, અમે એક બીજા લૂપ અંદર નેસ્ટ લૂપ છે,

91
00:06:51,840 --> 00:06:55,290
જે ખરેખર એક ઓ કામગીરી (n ^ 2) જેવી લાગે છે.

92
00:06:55,290 --> 00:07:01,590
જો કે, યાદીના છટણી ભાગ ખૂબ જ અંત સુધી સમગ્ર યાદીમાં શામેલ નથી નહોતો.

93
00:07:01,590 --> 00:07:06,920
તેમ છતાં, અમે સંભવિત છટણી ભાગ ખૂબ શરૂઆતમાં નવું તત્વ સામેલ કરી શકે છે

94
00:07:06,920 --> 00:07:09,320
અલગોરિધમ દરેક ઇટરેશન પર,

95
00:07:09,320 --> 00:07:14,500
જેનો અર્થ છે કે અમે દરેક તત્વ પર છટણી ભાગ હાલમાં જોવા હોય તો.

96
00:07:14,500 --> 00:07:20,090
તેથી, તેનો અર્થ એ કે અમે સંભવિત બીજો તત્વ માટે એક સરખામણી કરવા માટે કરી શકે છે,

97
00:07:20,090 --> 00:07:24,660
ત્રીજા તત્વ માટે બે સરખામણીઓ, અને તેથી પર.

98
00:07:24,660 --> 00:07:32,480
તેથી, પગલાંઓ કુલ સંખ્યા પૂર્ણાંકોના 1 થી 1 બાદ યાદી લંબાઈના સરવાળો છે.

99
00:07:32,480 --> 00:07:35,240
અમે એક શ્રેઢી સાથે આ પ્રતિનિધિત્વ કરી શકે છે.

100
00:07:41,170 --> 00:07:47,270
>> અમે summations માં અહીં ન જાય, પરંતુ તે તારણ છે કે જે આ શ્રેઢી સમાન છે

101
00:07:47,270 --> 00:07:57,900
2 ઉપર છે, જે સમકક્ષ ^ 2/2 n છે - (1 એન) - એન / 2 એન.

102
00:07:57,900 --> 00:08:00,800
જ્યારે અનંત સ્પર્શી રનટાઈમ વિશે વાત,

103
00:08:00,800 --> 00:08:05,170
આ n ^ 2 પદ માટે આ n એ શબ્દ પર પ્રભુત્વ રહ્યું છે.

104
00:08:05,170 --> 00:08:11,430
તેથી, નિવેશ સૉર્ટ મોટા ઓ (n ^ 2) છે.

105
00:08:11,430 --> 00:08:16,150
જો અમે પહેલાથી જ છટણી યાદી પર દાખલ સૉર્ટ ચાલી હતી.

106
00:08:16,150 --> 00:08:20,960
તે કિસ્સામાં, અમે ફક્ત અપ છટણી ડાબેથી જમણે ભાગ બિલ્ડ છો.

107
00:08:20,960 --> 00:08:25,050
તેથી, અમે માત્ર n પગલાંઓ ઓર્ડર કરવાની જરૂર પડશે.

108
00:08:25,050 --> 00:08:29,740
>> એટલે કે નિવેશ સૉર્ટ n ના પ્રભાવ સૌથી કેસ છે,

109
00:08:29,740 --> 00:08:34,130
જે અમે Ω (એન) સાથે પ્રતિનિધિત્વ કરે છે.

110
00:08:34,130 --> 00:08:36,190
અને તે નિવેશ સૉર્ટ માટે છે,

111
00:08:36,190 --> 00:08:40,429
માત્ર એક જ અનેક અલગોરિથમ્સ અમે યાદી સૉર્ટ વાપરી શકો છો.

112
00:08:40,429 --> 00:08:43,210
મારું નામ ટોમી છે, અને આ CS50 છે.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
ઓહ, તમે હમણાં બંધ ન કરી શકો છો કે એકવાર તે શરૂ થાય છે.

115
00:09:01,620 --> 00:09:04,760
ઓહ, અમે તે હતી - >> બૂમ!