1
00:00:00,000 --> 00:00:02,826
>> [संगीत बजाना]

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> डौग लॉयड: तो प्रविष्टि तरह एक और है
एल्गोरिथ्म हम एक सरणी से सुलझाने के लिए उपयोग कर सकते हैं।

4
00:00:09,370 --> 00:00:12,350
इस एल्गोरिथ्म के पीछे विचार
अपने सॉर्ट सरणी का निर्माण होता है

5
00:00:12,350 --> 00:00:19,670
जगह में, से बाहर तत्वों के स्थानांतरण
तुम जाओ के रूप में जिस तरह से, जगह बनाने के लिए।

6
00:00:19,670 --> 00:00:22,240
यह थोड़ा अलग है
चयन प्रकार या बुलबुला से

7
00:00:22,240 --> 00:00:25,460
प्रकार, उदाहरण के लिए, जहां
हम स्थानों समायोजित कर रहे हैं,

8
00:00:25,460 --> 00:00:26,910
जहां हम स्वैप कर रहे हैं।

9
00:00:26,910 --> 00:00:29,760
>> इस मामले में हम वास्तव में क्या कर रहे हैं
कर रही रपट तत्व है

10
00:00:29,760 --> 00:00:31,390
से अधिक है, जिस तरह से बाहर।

11
00:00:31,390 --> 00:00:34,030
इस एल्गोरिथ्म कैसे करता है
स्यूडोकोड में काम करते हैं?

12
00:00:34,030 --> 00:00:37,646
खैर बस मनमाने ढंग से कहना है कि चलो
सरणी के पहले तत्व हल है।

13
00:00:37,646 --> 00:00:38,770
हम यह जगह में निर्माण कर रहे हैं।

14
00:00:38,770 --> 00:00:42,660
>> हम लोग एक बार में एक ही तत्व जाना कर रहे हैं और
इसे बनाने के लिए, और इसलिए पहली बात हम देखते हैं

15
00:00:42,660 --> 00:00:43,890
एक एक तत्व सरणी है।

16
00:00:43,890 --> 00:00:47,720
और परिभाषा के द्वारा, एक से एक
तत्व सरणी हल है।

17
00:00:47,720 --> 00:00:50,850
>> तो फिर हम इस प्रक्रिया को दोहराना होगा until--
हम निम्नलिखित प्रक्रिया दोहराता हूँ

18
00:00:50,850 --> 00:00:52,900
तत्वों के सभी हल कर रहे हैं जब तक।

19
00:00:52,900 --> 00:00:57,770
अगले अवर्गीकृत तत्व को देखो और
सॉर्ट हिस्से में डालें,

20
00:00:57,770 --> 00:01:01,209
अपेक्षित संख्या स्थानांतरण द्वारा
जिस तरह से बाहर के तत्वों की।

21
00:01:01,209 --> 00:01:03,750
उम्मीद है कि इस दृश्य
आप है कि क्या वास्तव में देखने में मदद मिलेगी

22
00:01:03,750 --> 00:01:05,980
प्रविष्टि प्रकार के साथ चल रहा है।

23
00:01:05,980 --> 00:01:08,010
>> तो फिर, हमारे यहाँ है
पूरे अवर्गीकृत सरणी,

24
00:01:08,010 --> 00:01:10,970
तत्वों के सभी लाल रंग में संकेत दिया।

25
00:01:10,970 --> 00:01:13,320
और चलो का पालन करते हैं
हमारे स्यूडोकोड के कदम।

26
00:01:13,320 --> 00:01:16,970
हम ऐसा पहली बात, हम कहते है
सरणी के पहले तत्व, हल।

27
00:01:16,970 --> 00:01:20,920
तो हम बस कहने वाला हो
पांच, अब आप हल कर रहे हैं।

28
00:01:20,920 --> 00:01:24,570
>> तो फिर हम अगले को देखो
सरणी के अवर्गीकृत तत्व

29
00:01:24,570 --> 00:01:27,610
और हम उस सम्मिलित करना चाहते हैं
छाँटे गए हिस्से में,

30
00:01:27,610 --> 00:01:29,750
तत्वों पर स्थानांतरण द्वारा।

31
00:01:29,750 --> 00:01:33,470
तो अगले दो अवर्गीकृत है
सरणी के तत्व।

32
00:01:33,470 --> 00:01:36,250
जाहिर है कि यह पहले अंतर्गत आता है
पांच, तो हम क्या करने वाले हैं

33
00:01:36,250 --> 00:01:41,580
एक तरह से एक दूसरे के लिए एक तरफ दो पकड़ रहा है,
पर पांच बदलाव, और उसके बाद दो डालें

34
00:01:41,580 --> 00:01:43,210
पाँच से पहले, जहां जाना चाहिए।

35
00:01:43,210 --> 00:01:45,280
और अब हम दो हल है कि कह सकते हैं।

36
00:01:45,280 --> 00:01:48,400
>> आप देख सकते हैं तो, जैसा कि हम अब तक केवल है
सरणी के दो तत्वों को देखा।

37
00:01:48,400 --> 00:01:50,600
हम कम से देखा नहीं है
पर सभी बाकी है, लेकिन हम है

38
00:01:50,600 --> 00:01:54,582
उन दो तत्वों द्वारा हल मिल गया
स्थानांतरण तंत्र का तरीका है।

39
00:01:54,582 --> 00:01:56,410
>> तो हम फिर से इस प्रक्रिया को दोहराने।

40
00:01:56,410 --> 00:01:58,850
अगले अवर्गीकृत को देखो
तत्व, यह एक है।

41
00:01:58,850 --> 00:02:04,010
, एक दूसरे के लिए है कि एक तरफ पकड़ चलो
पर सब कुछ बदलाव, और एक डाल

42
00:02:04,010 --> 00:02:05,570
जहां यह जाना चाहिए।

43
00:02:05,570 --> 00:02:08,110
>> फिर, फिर भी, हम ही कभी किया है
एक, दो, और पांच को देखा।

44
00:02:08,110 --> 00:02:12,480
हम आ रहा है और क्या नहीं पता है,
लेकिन हम उन तीन तत्वों हल है।

45
00:02:12,480 --> 00:02:16,030
>> अगले अवर्गीकृत तत्व है
तीन, इसलिए हम यह सेट अलग कर देंगे।

46
00:02:16,030 --> 00:02:18,200
हम पर शिफ्ट करेंगे क्या हम
है, जो इस समय की जरूरत है

47
00:02:18,200 --> 00:02:21,820
पिछले के रूप में सब कुछ नहीं है
दो मामलों में, यह सिर्फ पांच है।

48
00:02:21,820 --> 00:02:25,440
और फिर हम में तीन रहना होगा,
दो और पांच के बीच।

49
00:02:25,440 --> 00:02:27,849
>> छह अवर्गीकृत बगल में है
सरणी के लिए तत्व।

50
00:02:27,849 --> 00:02:31,140
और वास्तव में छह इसलिए, पांच से अधिक है
हम भी किसी से अदला-बदली करने की ज़रूरत नहीं है।

51
00:02:31,140 --> 00:02:35,710
हम सिर्फ सही पर करने के लिए छह हमले कर सकते हैं
छाँटे गए भाग के अंत।

52
00:02:35,710 --> 00:02:38,270
>> अन्त में, चार है
पिछले अवर्गीकृत तत्व।

53
00:02:38,270 --> 00:02:42,060
इसलिए हम यह सेट अलग कर देंगे, के साथ बदलाव
तत्वों हम, पर बदलाव की जरूरत

54
00:02:42,060 --> 00:02:43,780
जहां यह है और फिर चार डाल दिया।

55
00:02:43,780 --> 00:02:46,400
और अब, देखो हम प्रकार है
सभी तत्वों की।

56
00:02:46,400 --> 00:02:48,150
प्रविष्टि के साथ नोटिस
तरह, हम नहीं था

57
00:02:48,150 --> 00:02:50,240
आगे और पीछे सरणी पार जाने के लिए।

58
00:02:50,240 --> 00:02:54,720
हम केवल सरणी पार चला गया
एक समय है, और हम चीजों को स्थानांतरित कर दिया

59
00:02:54,720 --> 00:02:59,870
हम पहले से ही क्रम में, का सामना करना पड़ा था कि
नए तत्वों के लिए जगह बनाने के लिए।

60
00:02:59,870 --> 00:03:02,820
>> तो क्या सबसे खराब मामला है
प्रविष्टि प्रकार के साथ परिदृश्य?

61
00:03:02,820 --> 00:03:05,090
सबसे खराब स्थिति में,
सरणी रिवर्स क्रम में है।

62
00:03:05,090 --> 00:03:11,180
आप n तत्वों की प्रत्येक पारी के लिए है
n पदों के लिए, हर बार हम

63
00:03:11,180 --> 00:03:12,880
एक प्रविष्टि बनाते हैं।

64
00:03:12,880 --> 00:03:15,720
यही कारण है कि स्थानांतरण का एक बहुत कुछ है।

65
00:03:15,720 --> 00:03:18,014
>> सबसे अच्छा मामले में,
सरणी पूरी तरह से हल है।

66
00:03:18,014 --> 00:03:20,680
और एक तरह से क्या हुआ जैसे
उदाहरण में पांच और छह के साथ

67
00:03:20,680 --> 00:03:23,779
हम सिर्फ यह पर हमले कर सकता है, जहां
किसी भी स्थानांतरण करने के लिए बिना,

68
00:03:23,779 --> 00:03:24,820
हम अनिवार्य है कि क्या करना चाहते हैं।

69
00:03:24,820 --> 00:03:27,560
>> आप कल्पना करें कि अगर हमारे
सरणी, छह के माध्यम से एक था

70
00:03:27,560 --> 00:03:29,900
हम द्वारा बंद शुरू होगा
एक घोषणा के हल है।

71
00:03:29,900 --> 00:03:33,300
दो तो हम सिर्फ यह कर सकते हैं एक के बाद आता है
एक और दो के अनुसार क्रमबद्ध हैं, ठीक है, ठीक है, कहते हैं।

72
00:03:33,300 --> 00:03:36,190
तीन ठीक है, तो बाद दो आता है,
एक और दो और तीन के अनुसार क्रमबद्ध हैं।

73
00:03:36,190 --> 00:03:39,590
>> हम हम कर रहे हैं, किसी भी स्वैप नहीं बना रहे हैं
सिर्फ इस मनमाना लाइन चलती

74
00:03:39,590 --> 00:03:42,460
हम जाने के रूप में के बीच हल और अवर्गीकृत।

75
00:03:42,460 --> 00:03:46,646
के रूप में प्रभावी रूप से हम उदाहरण में किया था,
हम आगे बढ़ने के रूप में, नीले तत्वों बदल रहे हैं।

76
00:03:46,646 --> 00:03:48,270
तो सबसे ज्यादा मामले क्रम तो, क्या बात है?

77
00:03:48,270 --> 00:03:51,854
हम में से प्रत्येक के लिए शिफ्ट करने के लिए है, तो याद रखें
n तत्वों संभवतः एन पदों,

78
00:03:51,854 --> 00:03:54,020
उम्मीद है कि आप देता है
सबसे खराब स्थिति है कि एक विचार

79
00:03:54,020 --> 00:03:57,770
क्रम n के बड़ी हे चुकता है।

80
00:03:57,770 --> 00:04:00,220
>> सरणी पूरी तरह से है
हल, सब हमें क्या करना है

81
00:04:00,220 --> 00:04:04,480
हर एक तत्व में लग रहा है
एक बार, और फिर हम कर रहे हैं।

82
00:04:04,480 --> 00:04:08,440
तो सबसे अच्छा मामले में, यह n के ओमेगा है।

83
00:04:08,440 --> 00:04:09,490
>> मैं डौग लॉयड हूँ।

84
00:04:09,490 --> 00:04:11,760
इस CS50 है।

85
00:04:11,760 --> 00:04:13,119