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
కాబట్టి, యొక్క మేము ప్రదర్శించారు సోపానాలను వర్ణిస్తుంది కొన్ని pseudocode పరిశీలించి అనుమతిస్తుంది.

66
00:04:46,760 --> 00:04:51,740
>> పంక్తి 1 న, మేము జాబితాలో ప్రతి మూలకం పైగా iterate చేయాలి అని చూడగలరు

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
మరియు j క్రమబద్ధీకరించనిది భాగంలోకి మా ఇండెక్స్ సూచిస్తుంది.

72
00:05:15,600 --> 00:05:20,980
>> లైన్ 4 న, కుడి నుండి ఎడమ క్రమబద్ధీకరించబడతాయి భాగం ద్వారా iterating చేస్తున్నారు.

73
00:05:20,980 --> 00:05:26,010
మేము మా ప్రస్తుత స్థితి ఎడమ మూలకం ఒకసారి iterating ఆపివేయాలనుకుంటున్నారా

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
>> మేము, అది స్థానం j ఇన్సర్ట్ తప్పు అని తెలుసు

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
మేము బిగ్ O సంజ్ఞామానం ఈ నడుస్తున్న సమయంలో ప్రాతినిధ్యం గుర్తుచేసుకున్నారు.

87
00:06:32,530 --> 00:06:38,500
మా జాబితా క్రమం చేయడానికి, మేము, క్రమబద్ధీకరించనిది భాగంలో అంశాలను పైగా iterate వచ్చింది

88
00:06:38,500 --> 00:06:43,430
మరియు శక్తివంతంగా క్రమబద్ధీకరించబడతాయి భాగం అన్ని మూలకాల కంటే ఆ అంశాలను ప్రతి కోసం.

89
00:06:43,430 --> 00:06:47,950
Intuitively, ఒక O (n ^ 2) ఆపరేషన్ వంటి ఈ శబ్దాలు.

90
00:06:47,950 --> 00:06:51,840
>> మా pseudocode వద్ద గురించి, మేము మరో లూప్ లోపల యున్న ఒక లూప్ కలిగి

91
00:06:51,840 --> 00:06:55,290
ఇది నిజానికి ఒక O (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
n / 2 - సమానమైన n ^ 2/2 ఇది 2 పైగా - n (1 n).

102
00:07:57,900 --> 00:08:00,800
Asymptotic runtime గురించి మాట్లాడుతున్నప్పుడు,

103
00:08:00,800 --> 00:08:05,170
ఈ n ^ 2 పదం ఈ పదం n ఆధిపత్యం అన్నారు.

104
00:08:05,170 --> 00:08:11,430
కాబట్టి, చొప్పించడం విధమైన బిగ్ O (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
ఇది మేము Ω (n) తో సూచిస్తాయి.

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
ఓహ్, ఆ చేశాడు - >> బూమ్!