1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [బబుల్ సార్ట్]

2
00:00:02,840 --> 00:00:04,560
[JACKSON STEINKAMP హార్వర్డ్ విశ్వవిద్యాలయం]

3
00:00:04,560 --> 00:00:07,500
[ఈ CS50 IS. CS50TV]

4
00:00:08,000 --> 00:00:11,730
బబుల్ సార్ట్ వేరు అల్గోరిథం యొక్క ఒక ఉదాహరణ -

5
00:00:11,730 --> 00:00:14,460
ఆ, మూలకాల ఒక సమితి లో క్రమీకరించడానికి ప్రక్రియ

6
00:00:14,460 --> 00:00:15,840
ఆరోహణ లేదా అవరోహణ క్రమంలో.

7
00:00:15,840 --> 00:00:18,710
మీరు ఒక అర్రే క్రమం కోరుకుంటే ఉదాహరణకు, సంఖ్యలు ఉంటాయి

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], బబుల్ సార్ట్ ఒక సరైన అమలు చేరాడు

9
00:00:23,060 --> 00:00:26,260
పేర్చిన అమరిక [2, 3, 5, 9] క్రమంలో.

10
00:00:26,260 --> 00:00:28,850
ఇప్పుడు నేను అల్గోరిథం ఎలా పనిచేస్తుంది pseudocode వివరించండి వెళుతున్న.

11
00:00:28,850 --> 00:00:34,000
>> 3, 2, 9, 6, మరియు 5 - లెట్ యొక్క మేము 5 పూర్ణాంకాల యొక్క జాబితా క్రమబద్ధీకరించేందుకు చేస్తున్నారు అనుకోండి.

12
00:00:34,000 --> 00:00:37,650
అల్గోరిథం, మొదటి రెండు అంశాలను 3 మరియు 2 చూడటం ద్వారా మొదలవుతుంది

13
00:00:37,650 --> 00:00:40,850
వారు పరస్పర ఆర్డర్ బయటకు అయితే తనిఖీ.

14
00:00:40,850 --> 00:00:43,150
అవి - 3 2 కంటే ఎక్కువ.

15
00:00:43,150 --> 00:00:45,190
ఆరోహణ క్రమంలో, అవి చుట్టూ ఇతర మార్గం ఉండాలి.

16
00:00:45,190 --> 00:00:46,610
కాబట్టి, మేము వాటిని మార్పిడి.

17
00:00:46,610 --> 00:00:49,760
[2, 3, 9, 6, 5]: ఇప్పుడు జాబితా ఈ కనిపిస్తోంది.

18
00:00:49,760 --> 00:00:52,450
>> తరువాత, మేము రెండవ మరియు మూడవ అంశాలు, 3 మరియు 9 చూడండి.

19
00:00:52,450 --> 00:00:55,770
వారు పరస్పర సరైన క్రమంలో ఉన్నారు.

20
00:00:55,770 --> 00:00:58,800
అల్గారిథమ్ వాటికి స్వాప్ లేదు 9 కంటే తక్కువగా ఉంటుంది, 3.

21
00:00:58,800 --> 00:01:01,900
తరువాత, మేము 9 మరియు 6 చూడండి. వారు క్రమం లేదు.

22
00:01:01,900 --> 00:01:04,260
>> అందుకే, ఈ 9 6 కంటే ఎక్కువగా ఉంటుంది ఎందుకంటే వాటిని మార్పిడి అవసరం.

23
00:01:04,260 --> 00:01:08,840
చివరగా, మేము గత రెండు పూర్ణాంకాల, 9 మరియు 5 చూడండి.

24
00:01:08,840 --> 00:01:10,850
వారు క్రమం లేదు, కాబట్టి వారు మార్చుకున్నారు ఉండాలి.

25
00:01:10,850 --> 00:01:13,360
జాబితా ద్వారా మొదటి పూర్తి పాస్ తరువాత,

26
00:01:13,360 --> 00:01:17,140
[2, 3, 6, 5, 9]: ఈ కనిపిస్తోంది.

27
00:01:17,140 --> 00:01:19,690
చెడు లేదు. ఇది దాదాపు క్రమబద్ధీకరించబడతాయి యొక్క.

28
00:01:19,690 --> 00:01:22,450
కాని మనము దానిని పూర్తిగా క్రమబద్ధీకరించబడతాయి పొందడం మళ్లీ జాబితా ద్వారా అమలు చేయాలి.

29
00:01:22,450 --> 00:01:29,250
రెండు 3 కంటే తక్కువ, కాబట్టి మేము వాటిని మార్చవద్దు.

30
00:01:29,250 --> 00:01:31,700
>> మూడు 6 కంటే తక్కువ, కాబట్టి మేము వాటిని మార్చవద్దు.

31
00:01:31,700 --> 00:01:35,500
ఆరు 5 కంటే ఎక్కువగా ఉంటుంది. మేము మార్చుకున్నారు.

32
00:01:35,500 --> 00:01:38,460
ఆరు 9 కంటే తక్కువగా ఉంది. మేము మార్చవద్దు.

33
00:01:38,460 --> 00:01:42,170
ద్వారా రెండవ పాస్ తర్వాత, ఈ కనిపిస్తోంది: [2, 3, 5, 6, 9]. పర్ఫెక్ట్.

34
00:01:42,170 --> 00:01:44,680
ఇప్పుడు, pseudocode రచన యొక్క అనుమతిస్తాయి.

35
00:01:44,680 --> 00:01:48,450
సాధారణంగా, జాబితాలో ప్రతి మూలకం కోసం, మేము దాన్ని చూడవలసిన అవసరం

36
00:01:48,450 --> 00:01:50,060
మరియు నేరుగా దాని కుడి మూలకం.

37
00:01:50,060 --> 00:01:53,420
వారు క్రమం యొక్క పరస్పర వెలుపల ఉంటే - ఆ, ఉంటే ఎడమవైపు మూలకం

38
00:01:53,420 --> 00:01:56,810
కుడివైపు ఒకటి కంటే ఎక్కువ ఉంటుంది - మేము రెండు అంశాలను మార్పిడి చేయాలి.

39
00:01:56,810 --> 00:02:01,270
>> మేము జాబితాలో ప్రతి మూలకం కోసం దీన్ని, మరియు మేము ద్వారా ఒక పాస్ చేసిన.

40
00:02:01,270 --> 00:02:05,160
ఇప్పుడు మేము జాబితా నిర్ధారించడానికి ఉత్తీర్ణత ద్వారా తగినంత సార్లు లేదు

41
00:02:05,160 --> 00:02:06,480
పూర్తిగా, సరిగ్గా క్రమబద్ధీకరించబడింది.

42
00:02:06,480 --> 00:02:08,889
కానీ మేము జాబితా గుండా ఎన్ని సార్లు ఉన్నాయి

43
00:02:08,889 --> 00:02:10,400
మేము పూర్తి చేసిన హామీ?

44
00:02:10,400 --> 00:02:14,730
మేము పూర్తిగా వెనక్కి జాబితా ఉంటే సరే, చెత్త దృష్టాంత ఉంది.

45
00:02:14,730 --> 00:02:17,840
అప్పుడు సంఖ్య సమానంగా ఉత్తీర్ణత throughs అనేక పడుతుంది

46
00:02:17,840 --> 00:02:19,730
అంశాలను n-1 యొక్క.

47
00:02:19,730 --> 00:02:24,720
ఈ intuitively సమంజసం అనిపించుకోదు ఉంటే, ఒక సాధారణ విషయం యొక్క ఆలోచన - జాబితా [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> ఈ క్రమం సరిగా ఒక ఉత్తీర్ణత ద్వారా తీసుకోవాలని అన్నారు.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - విషయంలో, 3 అంశాలతో వెనుకకు క్రమబద్ధీకరించబడతాయి ఉంది

50
00:02:33,060 --> 00:02:34,830
ఇది విధమైన 2 నిద్రావస్థ తీసుకోవాలని చెప్పారు.

51
00:02:34,830 --> 00:02:37,980
ఒక పునరుక్తి తర్వాత, [, 3 1 2] ఉంది.

52
00:02:37,980 --> 00:02:39,550
రెండవ దిగుబడి క్రమబద్ధీకరించబడతాయి శ్రేణి [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
కాబట్టి మీరు, మీరు సాధారణంగా, అర్రే ద్వారా వెళ్ళడానికి లేదు తెలుసు

54
00:02:43,350 --> 00:02:46,790
n శ్రేణి లోని ఎలిమెంట్స్ సంఖ్య n-1 టైమ్స్, కంటే ఎక్కువ.

55
00:02:47,090 --> 00:02:50,470
అతిపెద్ద అంశాలను 'బుడగ అప్' ఉంటాయి ఎందుకంటే ఇది బబుల్ సార్ట్ అని

56
00:02:50,470 --> 00:02:51,950
అందంగా త్వరగా కుడివైపు.

57
00:02:51,950 --> 00:02:53,980
నిజానికి, ఈ అల్గోరిథం ఆసక్తికరమైన ప్రవర్తన కలిగి ఉంది.

58
00:02:53,980 --> 00:02:57,410
>> మొత్త ద్వారా m నిద్రావస్థ తర్వాత,

59
00:02:57,410 --> 00:02:59,000
కుడివైపు m అంశాలను హామీ

60
00:02:59,000 --> 00:03:01,000
వాటి సరైన స్థానంలో వేరు చేయడానికి.

61
00:03:01,000 --> 00:03:02,280
మీరు, మీ కోసం ఈ చూడాలనుకుంటే

62
00:03:02,280 --> 00:03:05,500
మేము పూర్తిగా వెనక్కి జాబితా [9, 6, 5, 3, 2] ఇది ప్రయత్నించవచ్చు.

63
00:03:05,500 --> 00:03:08,220
మొత్తం జాబితా ద్వారా ఒక పాస్ తరువాత,

64
00:03:08,220 --> 00:03:09,220
[రచన ధ్వని]

65
00:03:09,220 --> 00:03:18,790
[6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]

66
00:03:18,790 --> 00:03:21,250
కుడివైపు మూలకం 9 దాని సరైన స్థానంలో ఉంది.

67
00:03:21,250 --> 00:03:24,760
ఉత్తీర్ణత ద్వారా రెండవ తరువాత, 6 'bubbled అప్' ఉంటుంది

68
00:03:24,760 --> 00:03:26,220
రెండవ స్థానంలో కుడివైపు.

69
00:03:26,220 --> 00:03:28,840
6 మరియు 9 - - కుడి రెండు అంశాలను వాటి సరైన ప్రదేశాలలో ఉంటుంది

70
00:03:28,840 --> 00:03:30,580
మొదటి రెండు ఉత్తీర్ణత throughs తర్వాత.

71
00:03:30,580 --> 00:03:32,590
>> కాబట్టి, మేము ఎలా అల్గోరిథం ఆప్టిమైజ్ చేయడానికి ఈ ఉపయోగించవచ్చు?

72
00:03:32,590 --> 00:03:34,850
Well, అర్రే ద్వారా ఒక పునరుక్తి తర్వాత

73
00:03:34,850 --> 00:03:37,690
మేము నిజంగా కుడివైపు మూలకం తనిఖీ లేదు

74
00:03:37,690 --> 00:03:39,200
మేము తెలిసిన ఎందుకంటే క్రమబద్ధీకరించబడతాయి యొక్క.

75
00:03:39,200 --> 00:03:43,050
రెండు నిద్రావస్థ తర్వాత, మేము కుడివైపు రెండు అంశాలను ఉంచడం ఉన్నాయి ఖచ్చితంగా తెలుసు.

76
00:03:43,050 --> 00:03:48,260
కాబట్టి, సాధారణంగా, పూర్తి శ్రేణి ద్వారా k నిద్రావస్థ తర్వాత,

77
00:03:48,260 --> 00:03:51,550
మేము తెలిసిన నుండి చివరి k అంశాలను తనిఖీ రిడన్డెంట్

78
00:03:51,550 --> 00:03:52,360
వారు ఇప్పటికే సరైన స్థానంలో ఉన్నాము.

79
00:03:52,360 --> 00:03:54,870
>> మీరు n మూలకాల శ్రేణిని క్రమబద్ధీకరించేందుకు చేసిన అయితే,

80
00:03:54,870 --> 00:03:57,870
మొదటి మళ్ళా న - you'll అన్ని మూలకాల క్రమం ఉంటుంది - మొదటి n-0.

81
00:03:57,870 --> 00:04:04,170
రెండవ పునరుక్తి, మీరు అన్ని మూలకాల కానీ గత చూడండి ఉంటుంది -

82
00:04:04,170 --> 00:04:07,090
n-1 మొదటి.

83
00:04:07,090 --> 00:04:10,520
మరో ఆప్టిమైజేషన్ జాబితా ఇప్పటికే క్రమబద్ధీకరించబడింది లేదో తనిఖీ చేయడానికి కావచ్చు

84
00:04:10,520 --> 00:04:11,710
ప్రతి పునరావృతం తరువాత.

85
00:04:11,710 --> 00:04:13,900
ఇది ఇప్పటికే క్రమబద్ధీకరించబడతాయి అయితే, మేము ఏ నిద్రావస్థ తయారు లేదు

86
00:04:13,900 --> 00:04:15,310
జాబితా ద్వారా.

87
00:04:15,310 --> 00:04:16,220
దీన్ని మేము ఎలా చేయగలరు?

88
00:04:16,220 --> 00:04:19,360
Well, మేము ఒక జాబితా యొక్క ఉత్తీర్ణత ద్వారా ఏ మార్పిడులు చేయటం లేదు ఉంటే,

89
00:04:19,360 --> 00:04:22,350
అది మేము ఏదైనా మార్పిడి ఎందుకంటే జాబితా ఇప్పటికే క్రమబద్ధీకరించబడతాయి అని స్పష్టమవుతుంది.

90
00:04:22,350 --> 00:04:24,160
కాబట్టి మేము ఖచ్చితంగా మళ్ళీ క్రమం లేదు.

91
00:04:24,160 --> 00:04:27,960
>> బహుశా మీకు 'వర్గీకరించరు' అనే జెండా వేరియబుల్ ప్రారంభించడం కాలేదు

92
00:04:27,960 --> 00:04:30,990
మీరు ఏ అంశాలు మారడానికి ఉంటే తప్పుడు మరియు నిజమైన దానిని మార్చడానికి

93
00:04:30,990 --> 00:04:32,290
అర్రే ద్వారా ఒక పునరుక్తి.

94
00:04:32,290 --> 00:04:35,350
లేదా ఇదే విధంగా, మీరు ఎలా అనేక మార్పిడులు లెక్కించడానికి ఒక కౌంటర్ తయారు

95
00:04:35,350 --> 00:04:37,040
ఏ మళ్ళా న.

96
00:04:37,040 --> 00:04:40,040
ఒక పునరావృతం తరువాత, మీరు అంశాలను ఏ స్వాప్ లేదు ఉంటే,

97
00:04:40,040 --> 00:04:41,780
మీరు జాబితా ఇప్పటికే క్రమబద్ధీకరించబడింది మరియు మీరు పూర్తి చేసిన తెలుసు.

98
00:04:41,780 --> 00:04:44,090
బబుల్ సార్ట్, ఇతర సార్టింగ్ అల్గోరిథంలు వంటి ఉంటుంది

99
00:04:44,090 --> 00:04:46,960
ఒక క్రమం పద్ధతి ఏ అంశాలకు పని tweaked.

100
00:04:46,960 --> 00:04:50,610
>> మీరు చెప్పే విధంగా ఉన్నాయి రెండు అంశాలను ఇచ్చిన, ఉంటే మొదటి ఒక

101
00:04:50,610 --> 00:04:53,770
సమానంగా లేదా రెండవ కంటే తక్కువ, కంటే ఎక్కువగా ఉంటుంది.

102
00:04:53,770 --> 00:04:56,870
ఉదాహరణకు, మీరు ఈ విధంగా అక్షరాలు క్రమం కాలేదు

103
00:04:56,870 --> 00:05:00,520
ఒక <బి, బి <సి, మొదలైనవి ఆ

104
00:05:00,520 --> 00:05:03,830
ఆదివారం సోమవారం కంటే తక్కువ ఉన్న లేదా మీరు వారం రోజులు క్రమం కాలేదు

105
00:05:03,830 --> 00:05:05,110
ఇది మంగళవారం కంటే తక్కువగా ఉంది.

106
00:05:05,110 --> 00:05:09,630
>> ఏ ఎంతో చక్కగా లేదా ఫాస్ట్ సార్టింగ్ అల్గోరిథం అర్థం ద్వారా బబుల్ సార్ట్ ఉంది.

107
00:05:09,630 --> 00:05:12,370
ఘోరమైన-runtime కేసు n యొక్క బిగ్ O ఉంది ²

108
00:05:12,370 --> 00:05:14,810
మీరు జాబితా ద్వారా n నిద్రావస్థ తయారు చేసుకోవాలి ఎందుకంటే

109
00:05:14,810 --> 00:05:18,430
ప్రతి ఉత్తీర్ణత ద్వారా అన్ని n మూలకాలు తనిఖీ, nxn = n ².

110
00:05:18,430 --> 00:05:22,730
ఈ అమలు సమయం అంశాల సంఖ్య మీరు, పెరుగుదల క్రమబద్ధీకరించేందుకు చేస్తున్న అర్థం

111
00:05:22,730 --> 00:05:24,330
రన్ టైం quadratically పెంచుతుంది.

112
00:05:24,330 --> 00:05:27,330
>> కానీ సామర్ధ్యం మీ ప్రోగ్రామ్ యొక్క ఒక ప్రధాన సమస్యగా లేకపోతే

113
00:05:27,330 --> 00:05:29,550
లేదా మీరు మాత్రమే అంశాలు చిన్న సంఖ్య క్రమబద్ధీకరించేందుకు చేస్తుంటే,

114
00:05:29,550 --> 00:05:31,660
మీరు బబుల్ సార్ట్ ఉపయోగపడే ఎందుకంటే

115
00:05:31,660 --> 00:05:33,360
అది అర్థం సరళమైన క్రమబద్ధీకరించేందుకు యాంత్రిక పద్ధతులు ఒకటి

116
00:05:33,360 --> 00:05:34,250
మరియు కోడ్.

117
00:05:34,250 --> 00:05:37,270
ఇది కూడా ఒక సైద్ధాంతిక అనువాదం తో అనుభవాన్ని పొందడానికి ఒక గొప్ప మార్గం

118
00:05:37,270 --> 00:05:40,220
అసలు పనితీరును కోడ్ లోకి అల్గోరిథం.

119
00:05:40,220 --> 00:05:43,000
అయితే, అది మీరు బబుల్ సార్ట్ ఉంది. చూడటం ధన్యవాదాలు.

120
00:05:43,000 --> 00:05:44,000
CS50.TV