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
एक क्रमबद्ध भाग और एक unsorted भाग.

8
00:00:26,580 --> 00:00:29,290
>> एल्गोरिथ्म के हर कदम पर ले जाया जाता है, एक संख्या

9
00:00:29,290 --> 00:00:32,439
unsorted भाग से हल भाग

10
00:00:32,439 --> 00:00:35,680
अंततः जब तक पूरे सूची हल है.

11
00:00:35,680 --> 00:00:43,340
23, 42, 4, 16, 8, और 15 - यहाँ छह unsorted संख्या की सूची है.

12
00:00:43,340 --> 00:00:47,680
चूंकि ये संख्याएं सब आरोही क्रम में नहीं हैं, वे unsorted कर रहे हैं.

13
00:00:47,680 --> 00:00:53,890
चूंकि हम अभी तक छँटाई शुरू नहीं किया है, हम सभी छह तत्व हमारी unsorted भाग पर विचार करेंगे.

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
और हमारे unsorted हिस्सा इन पांच नंबर है.

20
00:01:20,260 --> 00:01:27,320
चलो अब हमारे unsorted भाग, 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
अब हमारे क्रमबद्ध भाग दो तत्व है, और हमारे unsorted भाग चार तत्व है.

25
00:01:51,850 --> 00:01:57,200
तो, चलो अब 4 के लिए ले जाने के लिए, unsorted भाग में अगले तत्व.

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
>> इसका मतलब है कि हम क्रमबद्ध हिस्से में 1 स्लॉट में 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 1 संख्या हमने देखा है कि संख्या से कम है

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
>> सही सभी. अब, हम चार क्रमबद्ध तत्वों और दो unsorted तत्वों है.

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
हम unsorted भाग में कोई अधिक तत्व है,

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
तो, चलो कुछ pseudocode है कि कदम हम सिर्फ प्रदर्शन का वर्णन पर एक नज़र रखना.

66
00:04:46,760 --> 00:04:51,740
>> लाइन 1 में, हम देख सकते हैं कि हम पर सूची में प्रत्येक तत्व पुनरावृति करने की आवश्यकता होगी

67
00:04:51,740 --> 00:04:57,060
1 को छोड़कर, unsorted भाग में पहला तत्व के बाद से बस हो जाएगा

68
00:04:57,060 --> 00:05:00,220
क्रमबद्ध भाग में पहला तत्व.

69
00:05:00,220 --> 00:05:06,320
लाइनों 2 और 3 में, हम हमारे unsorted हिस्से में वर्तमान जगह का ट्रैक रख रहे हैं.

70
00:05:06,320 --> 00:05:10,450
तत्व संख्या का प्रतिनिधित्व करता है हम वर्तमान में क्रमबद्ध भाग में बढ़ रहे हैं,

71
00:05:10,450 --> 00:05:15,600
और जम्मू unsorted भाग में हमारे सूचकांक का प्रतिनिधित्व करता है.

72
00:05:15,600 --> 00:05:20,980
>> 4 लाइन पर, हम क्रमबद्ध दाईं से बाईं ओर भाग के माध्यम से iterating रहे हैं.

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
लेकिन हम बाएं से दाएं unsorted भाग के माध्यम से आगे बढ़ रहे हैं.

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
आदेश में हमारी सूची को सॉर्ट करने के लिए, हम unsorted भाग में तत्वों पर पुनरावृति था,

88
00:06:38,500 --> 00:06:43,430
और उन तत्वों के संभावित क्रमबद्ध भाग में सभी तत्वों पर, प्रत्येक के लिए.

89
00:06:43,430 --> 00:06:47,950
Intuitively, एक हे आपरेशन (n ^ 2) की तरह लग रहा है.

90
00:06:47,950 --> 00:06:51,840
>> हमारे pseudocode को देखते हुए, हम एक दूसरे पाश अंदर नेस्टेड पाश है,

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
3 तत्व के लिए दो तुलना, और इतने पर.

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 एन) n / 2 n.

102
00:07:57,900 --> 00:08:00,800
जब asymptotic क्रम के बारे में बात कर रही है,

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
ओह, हम किया है कि - >> बूम!