1
00:00:00,000 --> 00:00:03,360
>> [సంగీతాన్ని]

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
డౌ LLOYD: అన్ని కుడి, కాబట్టి
బబుల్ సార్ట్ ఒక అల్గోరిథం

4
00:00:06,730 --> 00:00:08,730
మీరు మూలకాల ఒక సమితి క్రమం ఉపయోగించవచ్చు.

5
00:00:08,730 --> 00:00:10,850
యొక్క ఇది ఎలా పనిచేస్తుంది పరిశీలించి లెట్.

6
00:00:10,850 --> 00:00:13,240
>> సో ప్రాథమిక ఆలోచన వెనుక
బబుల్ సార్ట్ ఈ ఉంది.

7
00:00:13,240 --> 00:00:17,340
మేము సాధారణంగా అధిక తరలించడానికి కావలసిన
సాధారణంగా కుడి విలువైన అంశాలు,

8
00:00:17,340 --> 00:00:20,340
మరియు సాధారణంగా విలువైన అంశాలు తగ్గిస్తుంది
ఎడమ, మేము ఆశించిన విధంగానే.

9
00:00:20,340 --> 00:00:23,256
మేము తక్కువ విషయాలు వద్ద ఉండాలనుకుంటున్నాను
ప్రారంభంలో, మరియు అధిక విషయాల

10
00:00:23,256 --> 00:00:24,970
చివరిలో ఉండాలి.

11
00:00:24,970 --> 00:00:26,130
>> మేము ఎలా చేయాలి?

12
00:00:26,130 --> 00:00:28,040
బాగా pseudocode కోడ్ లో,
మేము చేసుకుందాం చెప్పగల్గినవి

13
00:00:28,040 --> 00:00:30,320
కాని సున్నా విలువ ఒక స్వాప్ కౌంటర్ సెట్.

14
00:00:30,320 --> 00:00:32,570
మేము రెండవ అలా ఎందుకు చూస్తారు.

15
00:00:32,570 --> 00:00:36,090
మరియు తర్వాత మేము క్రింది పునరావృతం
స్వాప్ కౌంటర్ 0 వరకు ప్రక్రియ

16
00:00:36,090 --> 00:00:39,910
లేదా మేము అస్సలు మార్పిడులు చేయటం వరకు.

17
00:00:39,910 --> 00:00:43,170
>> స్వాప్ కౌంటర్ రీసెట్
0 ఇది ఇప్పటికే 0 కాదు.

18
00:00:43,170 --> 00:00:46,420
అప్పుడు ప్రతి చూడండి
అంశాల ప్రక్కనే జంట.

19
00:00:46,420 --> 00:00:49,550
ఆ రెండు అంశాలు ఉంటే
కాదు క్రమంలో వాటిని మార్పిడి,

20
00:00:49,550 --> 00:00:51,620
మరియు స్వాప్ కౌంటర్ 1 జోడించండి.

21
00:00:51,620 --> 00:00:53,870
మీరు గురించి ఆలోచిస్తూ ఉంటే
ఈ మీరు ఊహించడానికి ముందు,

22
00:00:53,870 --> 00:00:57,471
ఈ తక్కువ తరలించడానికి ఉంటుంది గమనించే
ఎడమ విలువైన అంశాలు

23
00:00:57,471 --> 00:01:00,720
మరియు అధిక, కుడి అంశాలు విలువైన
ప్రభావవంతంగా మేము చేయాలనుకుంటున్నారా ఏమి,

24
00:01:00,720 --> 00:01:03,940
ఇది ఆ సమూహాలకు తరలించడానికి ఉంది
ఆ విధంగా అంశాల.

25
00:01:03,940 --> 00:01:07,035
ఎలా ఈ ఊహించడానికి లెట్
మా శ్రేణి ఉపయోగించి చూడండి ఉండవచ్చు

26
00:01:07,035 --> 00:01:10,504
మేము పరీక్షించడానికి ఉపయోగించిన
ఈ అల్గోరిథంలు బయటకు.

27
00:01:10,504 --> 00:01:13,420
మేము మళ్ళీ ఇక్కడ ఒక క్రమబద్ధీకరించనిది శ్రేణి కలిగి
అన్ని మూలకాల ద్వారా సూచించిన

28
00:01:13,420 --> 00:01:14,840
ఎరుపు లో ఉండటం.

29
00:01:14,840 --> 00:01:17,970
నేను నా స్వాప్ కౌంటర్ సెట్
ఒక సున్నా విలువ.

30
00:01:17,970 --> 00:01:20,610
నేను ఏకపక్ష ఎంచుకున్నాడు
ప్రతికూల 1 కలిగి అది 0 కాదు.

31
00:01:20,610 --> 00:01:23,840
మేము ఈ విధానాన్ని పునరుక్తి చేయడానికి కావలసిన
స్వాప్ కౌంటర్ వరకు 0.

32
00:01:23,840 --> 00:01:26,540
నా స్వాప్ సెట్ ఎందుకు ఈ ఉంది
కొన్ని కాని సున్నా విలువను కౌంటర్,

33
00:01:26,540 --> 00:01:29,400
లేకపోతే ఎందుకంటే
స్వాప్ కౌంటర్ 0 ఉంటుంది.

34
00:01:29,400 --> 00:01:31,610
మేము కూడా ప్రారంభం కాదు
అల్గోరిథం యొక్క ప్రక్రియ.

35
00:01:31,610 --> 00:01:33,610
మరలా, దశలను are--
స్వాప్ కౌంటర్ రీసెట్

36
00:01:33,610 --> 00:01:37,900
0, ఆపై ప్రతి ప్రక్కనే చూడండి
యుగ్మము, మరియు వారు క్రమంలో బయటకు అయితే,

37
00:01:37,900 --> 00:01:40,514
వాటిని మార్పిడి మరియు 1 జోడించండి
స్వాప్ కౌంటర్.

38
00:01:40,514 --> 00:01:41,680
కాబట్టి యొక్క ఈ ప్రక్రియను ప్రారంభించడానికి వీలు.

39
00:01:41,680 --> 00:01:44,430
కాబట్టి మేము మొదటి విషయం ఉంది
మేము, 0 స్వాప్ కౌంటర్ సెట్

40
00:01:44,430 --> 00:01:46,660
ఆపై మేము చూడటం మొదలు
ప్రతి ప్రక్కనే జత వద్ద.

41
00:01:46,660 --> 00:01:49,140
>> కాబట్టి మేము మొదటి 5 మరియు 2 చూడటం మొదలు.

42
00:01:49,140 --> 00:01:52,410
మేము వారు బయటకు ఉన్నాయని చూడండి
ఆర్డర్ మరియు కాబట్టి మేము వాటిని మార్పిడి.

43
00:01:52,410 --> 00:01:53,830
మరియు మేము స్వాప్ కౌంటర్ 1 జోడించండి.

44
00:01:53,830 --> 00:01:57,860
కాబట్టి ఇప్పుడు మా swap కౌంటర్ 1,
మరియు 2 మరియు 5 మొగ్గు చేశారు.

45
00:01:57,860 --> 00:01:59,370
ఇప్పుడు మేము మళ్ళీ విధానాన్ని పునరుక్తి.

46
00:01:59,370 --> 00:02:03,540
>> మేము తదుపరి ప్రక్కనే జత చూడండి,
5 మరియు వారు కూడా క్రమం లేదు 1 కలిగి,

47
00:02:03,540 --> 00:02:06,960
కాబట్టి మేము వాటిని మార్పిడి మరియు జోడించడానికి
స్వాప్ కౌంటర్ 1.

48
00:02:06,960 --> 00:02:08,900
అప్పుడు మేము 5 మరియు 3 వద్ద చూడండి.

49
00:02:08,900 --> 00:02:13,830
వారు క్రమం ఉంటాయి, కాబట్టి మేము స్వాప్
వాటిని మరియు మేము స్వాప్ కౌంటర్ 1 జోడించండి.

50
00:02:13,830 --> 00:02:15,550
అప్పుడు మేము 5 మరియు 6 చూడండి.

51
00:02:15,550 --> 00:02:18,630
వారు క్రమంలో ఉన్నారు, కాబట్టి మేము నిజానికి లేదు
ఏదైనా ఈ సమయం మార్పిడి అవసరం.

52
00:02:18,630 --> 00:02:20,250
అప్పుడు మేము 6 మరియు 4 చూడండి.

53
00:02:20,250 --> 00:02:24,920
వారు క్రమం కూడా ఉన్నాము, కాబట్టి మేము స్వాప్
వాటిని మరియు మేము స్వాప్ కౌంటర్ 1 జోడించండి.

54
00:02:24,920 --> 00:02:26,230
>> ఇప్పుడు జరిగిన ఏమి గమనిస్తారు.

55
00:02:26,230 --> 00:02:29,514
మేము చివర 6 అన్ని మార్గం తరలించారు.

56
00:02:29,514 --> 00:02:32,180
ఎంపిక విధమైన లో, మీరు చేసిన ఉంటే
ఆ వీడియో చూసిన, మేము చేసినది ఉంది

57
00:02:32,180 --> 00:02:35,290
మేము కదిలే ఇచ్చాను
భవనం లో చిన్న అంశాలు

58
00:02:35,290 --> 00:02:39,640
నుండి తప్పనిసరిగా క్రమబద్ధీకరించబడతాయి శ్రేణి
అతిపెద్ద అతిచిన్న ఎడమ.

59
00:02:39,640 --> 00:02:43,200
బబుల్ సార్ట్ సందర్భంలో, మేము అయితే
ఈ ప్రత్యేక అల్గోరిథం క్రింది,

60
00:02:43,200 --> 00:02:46,720
మేము నిజానికి కడుతున్నట్లు చూడాలని
కుడి నుండి క్రమబద్ధీకరించబడతాయి శ్రేణి

61
00:02:46,720 --> 00:02:49,100
అతిచిన్న, అతిపెద్ద ఎడమ.

62
00:02:49,100 --> 00:02:53,840
మేము సమర్థవంతంగా 6, bubbled చేశారు
అతిపెద్ద విలువ, చివర అన్ని మార్గం.

63
00:02:53,840 --> 00:02:56,165
>> అందువలన మేము ఇప్పుడు ప్రకటించవచ్చు
ఆ క్రమబద్ధీకరించబడింది ఆ,

64
00:02:56,165 --> 00:02:59,130
మరియు భవిష్యత్తులో iterations--
అర్రే ద్వారా వెళుతున్న మళ్ళీ

65
00:02:59,130 --> 00:03:01,280
మేము ఇకపై 6 పరిగణలోకి లేదు.

66
00:03:01,280 --> 00:03:03,850
మేము మాత్రమే పరిగణించాలి
క్రమబద్ధీకరించనిది అంశాలను

67
00:03:03,850 --> 00:03:06,299
మేము ప్రక్కనే ఉన్న జతల శోధిస్తున్న.

68
00:03:06,299 --> 00:03:08,340
కాబట్టి మేము ఒక ముగించిన
బబుల్ సార్ట్ గుండా.

69
00:03:08,340 --> 00:03:11,941
కాబట్టి ఇప్పుడు మేము ప్రశ్న తిరిగి వెళ్ళు
స్వాప్ కౌంటర్ 0 వరకు పునరావృతం.

70
00:03:11,941 --> 00:03:13,690
బాగా స్వాప్ కౌంటర్
4, కాబట్టి మేము వెళుతున్న

71
00:03:13,690 --> 00:03:15,410
మళ్ళీ ఈ పద్ధతిని పునరావృతం ఉంచేందుకు.

72
00:03:15,410 --> 00:03:19,180
>> మేము స్వాప్ కౌంటర్ రీసెట్ చూడాలని
0, మరియు ప్రతి ప్రక్కనే జత చూడండి.

73
00:03:19,180 --> 00:03:21,890
కాబట్టి మేము వారు ఉన్నారు 1 కలిగి 2 ప్రారంభం మరియు
ఆర్డర్ బయటకు, కాబట్టి మేము వాటిని మార్పిడి

74
00:03:21,890 --> 00:03:23,620
మరియు మేము స్వాప్ కౌంటర్ 1 జోడించండి.

75
00:03:23,620 --> 00:03:25,490
2 మరియు 3, వారు క్రమంలో ఉన్నారు.

76
00:03:25,490 --> 00:03:27,060
మేము ఏమీ చేయాల్సిన అవసరం లేదు.

77
00:03:27,060 --> 00:03:28,420
3 మరియు 5 క్రమంలో ఉంటాయి.

78
00:03:28,420 --> 00:03:30,150
మేము అక్కడ చేయవలసిన అవసరం లేదు.

79
00:03:30,150 --> 00:03:32,515
>> 5 మరియు 4, వారు బయటకు ఉంటాయి
ఆర్డర్ ఆఫ్, అందువలన మేము

80
00:03:32,515 --> 00:03:35,130
వాటిని మార్పిడి మరియు జోడించడానికి అవసరం
స్వాప్ కౌంటర్ 1.

81
00:03:35,130 --> 00:03:38,880
ఇప్పుడు మేము 5 తరలించారు
తరువాతి అతిపెద్ద మూలకం,

82
00:03:38,880 --> 00:03:40,920
క్రమబద్ధీకరించనిది భాగం యొక్క చివర.

83
00:03:40,920 --> 00:03:44,360
కాబట్టి మేము ఇప్పుడు ఆ కాల్ చేయవచ్చు
క్రమబద్ధీకరించబడతాయి భాగం భాగం.

84
00:03:44,360 --> 00:03:47,180
>> ఇప్పుడు మీరు శోధిస్తున్న
స్క్రీన్ మరియు బహుశా వర్తమాన,

85
00:03:47,180 --> 00:03:50,130
, నేను శ్రేణి వంటి
ప్రస్తుతం క్రమబద్ధీకరించబడింది.

86
00:03:50,130 --> 00:03:51,820
కానీ మేము ఇంకా ఆ నిరూపించలేదు.

87
00:03:51,820 --> 00:03:54,359
మేము ఒక హామీ లేదు
అది క్రమబద్ధీకరించబడతాయి.

88
00:03:54,359 --> 00:03:56,900
కానీ ఈ పేరు మార్పుగా చెప్పవచ్చు
కౌంటర్ తెరపైకి వచ్చిన జరగబోతోంది.

89
00:03:56,900 --> 00:03:59,060
>> కాబట్టి మేము ఒక పాస్ పూర్తి చేసిన.

90
00:03:59,060 --> 00:04:00,357
స్వాప్ కౌంటర్ 2.

91
00:04:00,357 --> 00:04:02,190
కాబట్టి మేము పునరుక్తి చూడాలని
మళ్లీ ఈ ప్రక్రియ,

92
00:04:02,190 --> 00:04:04,290
స్వాప్ కౌంటర్ 0 వరకు పునరావృతం.

93
00:04:04,290 --> 00:04:05,550
0 స్వాప్ కౌంటర్ రీసెట్.

94
00:04:05,550 --> 00:04:06,820
కాబట్టి మేము అది రీసెట్ చేస్తాము.

95
00:04:06,820 --> 00:04:09,810
>> ఇప్పుడు ప్రతి ప్రక్కనే జత చూడండి.

96
00:04:09,810 --> 00:04:11,880
ఆ క్రమంలో 1 మరియు 2.

97
00:04:11,880 --> 00:04:13,590
2 మరియు 3 క్రమంలో ఉంటాయి.

98
00:04:13,590 --> 00:04:15,010
3 మరియు 4 క్రమంలో ఉంటాయి.

99
00:04:15,010 --> 00:04:19,250
కాబట్టి ఈ సమయంలో, మేము పూర్తి చేసిన గమనిస్తారు
ప్రతి ప్రక్కనే జంట చూడటం,

100
00:04:19,250 --> 00:04:22,530
కానీ స్వాప్ కౌంటర్ ఇప్పటికీ 0.

101
00:04:22,530 --> 00:04:25,520
>> మేము మారడానికి లేకపోతే
ఏ అంశాలు, అవి అప్పుడు

102
00:04:25,520 --> 00:04:28,340
ద్వారా క్రమంలో ఉండాలి
ఈ ప్రక్రియలో ఉండటం.

103
00:04:28,340 --> 00:04:32,000
కాబట్టి అన్నిరకాల సామర్థ్యం,
మేము కంప్యూటర్ శాస్త్రవేత్తలు ప్రేమ,

104
00:04:32,000 --> 00:04:35,560
మేము ఇప్పుడు ప్రకటించవచ్చు ఉంది
మొత్త తప్పక

105
00:04:35,560 --> 00:04:38,160
మేము లేదు ఎందుకంటే వేరు
ఏ అంశాలు మారడానికి.

106
00:04:38,160 --> 00:04:40,380
అతను చాలా మంచిది.

107
00:04:40,380 --> 00:04:43,260
>> సో వాట్ చెత్త కేస్
బబుల్ సార్ట్ తో దృష్టాంతంలో?

108
00:04:43,260 --> 00:04:46,240
చెత్త సందర్భంలో శ్రేణి
పూర్తిగా రివర్స్ క్రమంలో,

109
00:04:46,240 --> 00:04:49,870
అందువలన మేము ప్రతి రంగం కలిగి
పెద్ద అంశాలు అన్ని

110
00:04:49,870 --> 00:04:51,780
శ్రేణి అంతటా మార్గం.

111
00:04:51,780 --> 00:04:55,350
మరియు మేము సమర్థవంతంగా కూడా కలిగి
బబుల్ చిన్న అన్ని మూలకాలు తిరిగి

112
00:04:55,350 --> 00:04:57,050
చాలా శ్రేణి అంతటా అన్ని మార్గం.

113
00:04:57,050 --> 00:05:01,950
సో n మూలకాల ప్రతి తరలించడానికి ఉంది
ఇతర n మూలకాలు అన్ని అంతటా.

114
00:05:01,950 --> 00:05:04,102
కాబట్టి ఆ చెత్త దృష్టాంతంలో ఉంది.

115
00:05:04,102 --> 00:05:05,810
ఉత్తమ సందర్భంలో
దృష్టాంతంలో అయితే, ఈ

116
00:05:05,810 --> 00:05:07,880
ఎంపిక విధమైన నుండి కొద్దిగా భిన్నంగా.

117
00:05:07,880 --> 00:05:10,040
అర్రే ఇప్పటికే ఉంది
మేము వెళ్ళేటప్పుడు క్రమబద్ధీకరించబడింది.

118
00:05:10,040 --> 00:05:12,550
మేము ఏ చేసుకోవాలి లేదు
మొదటి పయనంలో మార్పిడులు.

119
00:05:12,550 --> 00:05:14,940
కాబట్టి మేము చూడండి ఉంటుంది
తక్కువ అంశాలను, కుడి?

120
00:05:14,940 --> 00:05:18,580
మేము ఈ పునరావృతం లేదు
పైగా అనేకసార్లు ప్రాసెస్.

121
00:05:18,580 --> 00:05:19,540
>> కాబట్టి ఆ అర్థం ఏమిటి?

122
00:05:19,540 --> 00:05:22,390
సో వాట్ చెత్త దృష్టాంత వార్తలు
బబుల్ సార్ట్ కోసం, మరియు ఏమి

123
00:05:22,390 --> 00:05:25,330
బబుల్ సార్ట్ ఉత్తమ దృష్టాంత?

124
00:05:25,330 --> 00:05:27,770
మీరు ఈ అంచనా తెలుసా?

125
00:05:27,770 --> 00:05:32,420
చెత్త సందర్భంలో మీరు iterate ఉంటుంది
అన్ని n మూలకాలు n సార్లు అంతటా.

126
00:05:32,420 --> 00:05:34,220
కాబట్టి చెత్త సందర్భంలో స్క్వేర్డ్ n.

127
00:05:34,220 --> 00:05:36,550
>> అర్రే సంపూర్ణ ఉంటే
క్రమబద్ధీకరించబడతాయి అయితే, మీరు మాత్రమే

128
00:05:36,550 --> 00:05:38,580
ప్రతి వద్ద చూడండి కలిగి
ఒకసారి అంశాలు యొక్క.

129
00:05:38,580 --> 00:05:42,670
మరియు స్వాప్ కౌంటర్ ఇప్పటికీ 0 ఉంటే,
మీరు ఈ శ్రేణి క్రమబద్ధీకరించబడింది చెప్పగలను.

130
00:05:42,670 --> 00:05:45,780
కాబట్టి ఉత్తమ సందర్భంలో, ఈ
ఎంపిక కంటే వాస్తవానికి మంచి

131
00:05:45,780 --> 00:05:49,230
విధమైన n యొక్క ఒమేగా ఉంది.

132
00:05:49,230 --> 00:05:50,270
>> నేను డౌ లాయిడ్ ఉన్నాను.

133
00:05:50,270 --> 00:05:52,140
ఈ CS50 ఉంది.

134
00:05:52,140 --> 00:05:54,382