1
00:00:00,000 --> 00:00:07,270

2
00:00:07,270 --> 00:00:10,390
>> MARK GROZEN-SMITH హాయ్, నేను మార్క్ రెడీ
-స్మిత్ Grozen, మరియు ఈ Quicksort ఉంది.

3
00:00:10,390 --> 00:00:13,520
కేవలం చొప్పించడం విధమైన మరియు బబుల్ వంటి
విధమైన, Quicksort కోసం ఒక అల్గోరిథం

4
00:00:13,520 --> 00:00:15,720
జాబితా లేదా విషయాలు వ్యూహం క్రమబద్ధీకరించేందుకు.

5
00:00:15,720 --> 00:00:19,080
సాధారణంగా, యొక్క ఊహించుకోవటం తెలియజేయండి ఆ
విషయాలు కేవలం పూర్ణ, కానీ

6
00:00:19,080 --> 00:00:22,060
Quicksort కోసం పనిచేస్తుంది తెలుసు
కేవలం ఎక్కువమంది.

7
00:00:22,060 --> 00:00:24,720
శీఘ్రప్రారంభ ఒక బిట్ మరింత క్లిష్టంగా ఉంటుంది
కంటే చొప్పించడం లేదా బుడగ, కానీ ఉంది

8
00:00:24,720 --> 00:00:27,560
ఆ చాలా సమర్థవంతంగా
చాలా సందర్భాలలో.

9
00:00:27,560 --> 00:00:28,150
తను.

10
00:00:28,150 --> 00:00:30,760
అతను కేవలం "చెప్పడానికి తెలుసా
కేసులు, "కాదు" అన్ని "?

11
00:00:30,760 --> 00:00:31,710
ఆసక్తికరంగా, ఏ.

12
00:00:31,710 --> 00:00:33,560
అన్ని సందర్భాలలో ఒకటే.

13
00:00:33,560 --> 00:00:36,650
ఈ వివరాలు గురించి ఆందోళన లేదు మీరు ఉంటే
ఇంకా పెద్ద O సంజ్ఞామానం చూసిన, కానీ లేదు

14
00:00:36,650 --> 00:00:39,730
Quicksort ఒక O (n స్క్వేర్డ్) అల్గోరిథం
ఘోరంగా, కేవలం వంటి

15
00:00:39,730 --> 00:00:41,430
చొప్పించడం లేదా బబుల్ సార్ట్.

16
00:00:41,430 --> 00:00:44,950
అయితే, ఇది సాధారణంగా మరింత పనిచేస్తుంది
పాత అనలాగ్ m అల్గోరిథం వంటి.

17
00:00:44,950 --> 00:00:45,750
ఎందుకు?

18
00:00:45,750 --> 00:00:46,810
మేము తరువాత ఆ పొందుతారు.

19
00:00:46,810 --> 00:00:49,610
కానీ ఇప్పుడు కోసం, యొక్క కేవలం నేర్చుకుందాము
Quicksort ఎలా పని.

20
00:00:49,610 --> 00:00:53,080
>> కాబట్టి యొక్క ఈ Quicksorting నడవడానికి వీలు
చిన్న నుండి పూర్ణాంకాల శ్రేణి

21
00:00:53,080 --> 00:00:54,260
అతిపెద్ద.

22
00:00:54,260 --> 00:01:00,110
ఇక్కడ మేము, పూర్ణ 6 కలిగి
5, 1, 3, 8, 4, 7, 9, మరియు 2.

23
00:01:00,110 --> 00:01:03,480
మొదటి, మేము చివరి మూలకం యొక్క ఎంచుకోండి
ఈ శ్రేణి - ఈ సందర్భంలో, రెండు -

24
00:01:03,480 --> 00:01:06,870
మరియు ఆ "ఇరుసు." కాల్ తరువాత, మేము
రెండు విషయాలు చూడండి మొదలుపెట్టిన -

25
00:01:06,870 --> 00:01:10,220
ఒక, నేను చూడండి చేస్తాము అత్యల్ప ఇండెక్స్,
హక్కు ఉండిపోయారు వంటి

26
00:01:10,220 --> 00:01:13,970
గోడ, మరియు, రెండు, ఎడమవైపున
నేను "ప్రస్తుత పిలుస్తాను ఇది మూలకం,

27
00:01:13,970 --> 00:01:17,260
మూలకం. "మనం చేయబోతున్నామని ఉంది
ఇతర అన్ని ఇతర మూలకాలను, చూడండి

28
00:01:17,260 --> 00:01:20,930
ఇరుసు కంటే, మరియు అన్ని అంశాలు ఉంచారు
ఇరుసు కంటే చిన్న

29
00:01:20,930 --> 00:01:24,140
గోడ వదిలి మరియు అన్ని
ఇరుసు కంటే పెద్ద

30
00:01:24,140 --> 00:01:25,570
గోడ యొక్క కుడి.

31
00:01:25,570 --> 00:01:29,560
అప్పుడు, చివరకు, మేము ఇరుసు డ్రాప్ చేస్తాము
కుడి మధ్య ఉంచండి ఆ గోడపై

32
00:01:29,560 --> 00:01:32,970
ఇది కంటే చిన్న అన్ని సంఖ్యలు
మరియు అన్ని సంఖ్యలు.

33
00:01:32,970 --> 00:01:34,460
>> కాబట్టి యొక్క ఆ తెలియజేసేలా.

34
00:01:34,460 --> 00:01:38,540
2 ఎంచుకొని, గోడ చాలు
ప్రారంభమై, 6 "ప్రస్తుత కాల్

35
00:01:38,540 --> 00:01:41,590
మూలకం. "కాబట్టి మేము వద్ద చూడవచ్చు
మా ప్రస్తుత మూలకం, 6.

36
00:01:41,590 --> 00:01:44,200
మరియు అది కంటే పెద్ద నుండి
2, మేము అక్కడ వదిలి

37
00:01:44,200 --> 00:01:45,610
గోడ యొక్క కుడి.

38
00:01:45,610 --> 00:01:48,980
అప్పుడు, మేము వంటి 5 చూడండి కొనసాగండి మా
ప్రస్తుత మూలకం మరియు చూసే ఈ

39
00:01:48,980 --> 00:01:51,840
, మళ్ళీ, 'స్టయిల్ కంటే పెద్ద, కాబట్టి మేము
అది కుడి ఉన్న వదిలి

40
00:01:51,840 --> 00:01:53,190
గోడ వైపు.

41
00:01:53,190 --> 00:01:53,880
మేము కొనసాగండి.

42
00:01:53,880 --> 00:01:56,750
మా ప్రస్తుత అంశం
ఇప్పుడు 1, - ఓహ్.

43
00:01:56,750 --> 00:01:58,030
ఈ ఆడేది.

44
00:01:58,030 --> 00:02:00,890
ప్రస్తుత మూలకం ఇప్పుడు తక్కువైతే
ఇరుసు, కాబట్టి మేము ఉంచండి మీరు

45
00:02:00,890 --> 00:02:02,570
గోడ ఎడమ.

46
00:02:02,570 --> 00:02:06,555
ఇది చేయుటకు, యొక్క కేవలం వెళతాను
అత్యల్ప ఇండెక్స్ తో ప్రస్తుత మూలకం

47
00:02:06,555 --> 00:02:07,970
గోడ యొక్క కుడి కూర్చొని.

48
00:02:07,970 --> 00:02:14,050

49
00:02:14,050 --> 00:02:17,570
ఇప్పుడు, మేము ఒక ఇండెక్స్ అప్ గోడ తరలించడానికి
కాబట్టి 1 ఎడమవైపు

50
00:02:17,570 --> 00:02:19,750
ఇప్పుడు గోడ వైపు.

51
00:02:19,750 --> 00:02:20,310
>> వేచి.

52
00:02:20,310 --> 00:02:23,450
నేను ఎలిమెంట్ కలపాలి
గోడ కుడివైపు, నేను కాదు?

53
00:02:23,450 --> 00:02:23,890
చింతించకండి.

54
00:02:23,890 --> 00:02:24,930
ఆ మంచిది.

55
00:02:24,930 --> 00:02:27,570
మేము ఇప్పుడు కోసం పట్టించుకోనట్లు మాత్రమే విషయం
అని అన్ని ఈ అంశాలను

56
00:02:27,570 --> 00:02:29,570
గోడ యొక్క కుడి పెద్దవిగా ఉంటాయి
ఇరుసు కంటే.

57
00:02:29,570 --> 00:02:31,760
సరైన క్రమంలో ఇంకా భావించబడుతుంది.

58
00:02:31,760 --> 00:02:33,200
>> ఇప్పుడు, తిరిగి అమర్చిన.

59
00:02:33,200 --> 00:02:35,840
కాబట్టి మేము చూడటం కొనసాగుతుంది
వీటి.

60
00:02:35,840 --> 00:02:39,075
ఈ సందర్భంలో, మనం ఉన్నాయి చూడండి
కంటే ఇతర అంశాలు తక్కువ

61
00:02:39,075 --> 00:02:42,100
ఇరుసు, కాబట్టి మేము వాటిని అన్ని వదిలి
గోడ కుడివైపు.

62
00:02:42,100 --> 00:02:45,980
చివరకు, మేము ప్రస్తుత మూలకం ను
మరియు అది స్టయిల్ చూడండి.

63
00:02:45,980 --> 00:02:48,830
ఇప్పుడు, రెండు అర్థం
శ్రేణి, మొదటిది యొక్క విభాగాలు

64
00:02:48,830 --> 00:02:51,820
ఇరుసు మీద మరియు ఎడమ వైపు చిన్న
గోడ, మరియు రెండవ జీవి యొక్క

65
00:02:51,820 --> 00:02:54,500
ఇరుసు కంటే పెద్ద
గోడ కుడివైపు.

66
00:02:54,500 --> 00:02:57,040
మేము మధ్య ఇరుసు మూలకం ఉంచేందుకు ఉంటుంది
రెండు, ఆపై మేము తెలుసు ఉంటాం

67
00:02:57,040 --> 00:03:01,000
ఇరుసు దాని కుడి అని
చివరి క్రమబద్ధీకరించబడతాయి స్థానంలో.

68
00:03:01,000 --> 00:03:04,980
కాబట్టి మేము మొదటి మూలకం మారడం
ఇరుసు గోడ కుడివైపు,

69
00:03:04,980 --> 00:03:06,410
మరియు మేము తెలిసిన ఇరుసు యొక్క
దాని కుడి స్థానంలో.

70
00:03:06,410 --> 00:03:11,130

71
00:03:11,130 --> 00:03:15,650
>> మేము అప్పుడు కోసం ఈ విధానాన్ని పునరుక్తి
subarrays వదిలి మరియు ఇరుసు కుడి.

72
00:03:15,650 --> 00:03:18,700
గత subarray మాత్రమే ఉంటుంది ఎందుకంటే
మూలకం పొడవుగా, మేము ఇప్పటికే తెలుసు

73
00:03:18,700 --> 00:03:22,480
క్రమబద్ధీకరించబడతాయి ఎలా మీరు బయటకు ఉంటుంది ఎందుకంటే
మీరు ఒకే ఒక అయితే ఆర్డర్?

74
00:03:22,480 --> 00:03:28,860
Subarray కుడివైపు, మేము
ఇరుసు గోడ 5, మరియు చూడండి

75
00:03:28,860 --> 00:03:32,250
కేవలం 6 వదిలేస్తే.

76
00:03:32,250 --> 00:03:34,970
మరియు ప్రస్తుత మూలకం కూడా
6 వంటి మొదలవుతుంది.

77
00:03:34,970 --> 00:03:36,200
కాబట్టి 6 5 కంటే ఎక్కువ.

78
00:03:36,200 --> 00:03:38,590
దానిపై ఉన్న మేము వదిలి
గోడ యొక్క కుడి వైపు.

79
00:03:38,590 --> 00:03:41,060
ఇప్పుడు, వెళ్లడానికి, 3 5 కంటే తక్కువ.

80
00:03:41,060 --> 00:03:44,160
కాబట్టి మేము మొదటి మూలకం తో స్విచ్
గోడ సరైన.

81
00:03:44,160 --> 00:03:47,944

82
00:03:47,944 --> 00:03:50,750
ఇప్పుడు నేను ఒక గోడ అప్ తరలించబడింది.

83
00:03:50,750 --> 00:03:53,010
ఇప్పుడు, 8 వెళ్ళేముందు.

84
00:03:53,010 --> 00:03:56,480
8, 5 కంటే ఎక్కువ
అందువలన మేము వదిలి.

85
00:03:56,480 --> 00:03:58,720
4 కంటే తక్కువ 5, కాబట్టి మేము ఇది మారడం.

86
00:03:58,720 --> 00:04:02,950

87
00:04:02,950 --> 00:04:03,570
మరియు.

88
00:04:03,570 --> 00:04:04,820
మరియు.

89
00:04:04,820 --> 00:04:10,190

90
00:04:10,190 --> 00:04:13,670
>> మేము విధానాన్ని పునరుక్తి ప్రతి సమయం
యెరే యొక్క ఎడమ మరియు కుడి వైపులా. మేము

91
00:04:13,670 --> 00:04:17,010
ఒక ఇరుసు ఎంచుకోండి మరియు పోలికలు చేయండి
మరియు ఎడమ మరొక స్థాయి సృష్టించడానికి మరియు

92
00:04:17,010 --> 00:04:18,240
కుడి subarrays.

93
00:04:18,240 --> 00:04:21,500
ఈ పునరావృత కాల్ వరకు కొనసాగుతుంది
మేము చేసిన ఉన్నప్పుడు ముగింపు చేరుకోవడానికి

94
00:04:21,500 --> 00:04:25,290
లోకి మొత్తం శ్రేణి విభజించబడుతుంది
పొడవు 1 కేవలం subarrays.

95
00:04:25,290 --> 00:04:28,060
అక్కడ నుండి, మేము శ్రేణి క్రమబద్ధీకరించబడింది తెలుసు
ప్రతి మూలకం కలిగి, వద్ద

96
00:04:28,060 --> 00:04:29,330
కొన్ని పాయింట్, ఒక ఇరుసు ఉంది.

97
00:04:29,330 --> 00:04:32,720
ఇతర మాటలలో, ప్రతి మూలకం కోసం, అన్ని
ఎడమ సంఖ్యలు తక్కువ ఉంటాయి

98
00:04:32,720 --> 00:04:36,420
విలువలు మరియు అన్ని సంఖ్యలు
కుడి ఎక్కువ విలువలు కలిగి.

99
00:04:36,420 --> 00:04:38,980
>> ఈ పద్ధతి బాగా పనిచేస్తుంది ఉంటే
ఎంపిక ఇరుసు విలువ ఉంది

100
00:04:38,980 --> 00:04:41,930
సుమారు మధ్యలో
జాబితాలో విలువలు పరిధి.

101
00:04:41,930 --> 00:04:45,630
మేము తరలించడానికి తర్వాత ఈ, అర్థం
అనేక గురించి చుట్టూ అంశాలను,

102
00:04:45,630 --> 00:04:48,390
ఇరుసు ఎడమవైపున అంశాలు
కుడి ఉన్నాయి.

103
00:04:48,390 --> 00:04:52,380
మరియు యొక్క విభజన మరియు జయించటానికి ప్రకృతి
Quicksort అల్గోరిథం తర్వాత తీసుకుంటారు

104
00:04:52,380 --> 00:04:53,850
పూర్తి ప్రయోజనం.

105
00:04:53,850 --> 00:04:57,500
ఈ O ఒక runtime సృష్టిస్తుంది (n లాగ్ n,)
మేము n మైనస్ 1 n ఎందుకంటే

106
00:04:57,500 --> 00:05:01,640
ప్రతి తరం మరియు లాగ్ న పోలికలు
మేము జాబితా విభజించడానికి కలిగి n ఎందుకంటే

107
00:05:01,640 --> 00:05:03,210
n సార్లు లాగ్.

108
00:05:03,210 --> 00:05:06,160
అయితే, చెత్త సందర్భాలలో, ఈ
క్రమసూత్ర పద్ధతి నిజానికి O (n ఉంటుంది

109
00:05:06,160 --> 00:05:09,850
స్క్వేర్డ్.) ప్రతి తరం మీద ఊహించు,
ఇరుసు కేవలం నిర్మాణము

110
00:05:09,850 --> 00:05:12,520
చిన్న లేదా పెద్ద
మేము క్రమబద్ధీకరించేందుకు చేస్తున్నారు సంఖ్యలు.

111
00:05:12,520 --> 00:05:15,870
ఈ జాబితా విడగొట్టి అర్థం
సార్లు మరియు మేకింగ్ n మైనస్ 1 n

112
00:05:15,870 --> 00:05:17,690
పోలికలు ప్రతి సమయం.

113
00:05:17,690 --> 00:05:20,490
అందువలన, n ఓ స్క్వేర్డ్.

114
00:05:20,490 --> 00:05:22,000
>> మేము ఎలా పద్ధతి మెరుగుపరచడానికి?

115
00:05:22,000 --> 00:05:25,100
పద్ధతి మెరుగుపరిచే మంచి మార్గం
సంభావ్యత అణిచివేసేందుకు ఆ

116
00:05:25,100 --> 00:05:28,150
రన్టైమ్ ఎప్పుడైనా ఉంది
n ఓ స్క్వేర్డ్.

117
00:05:28,150 --> 00:05:31,860
ఈ చెత్త, చెత్త దృష్టాంతంలో గుర్తుంచుకో
మాత్రమే జరుగుతుంది ఉన్నప్పుడు

118
00:05:31,860 --> 00:05:35,320
ఎంపిక ఇరుసు ఎల్లప్పుడూ అత్యధిక ఉంది
లేదా శ్రేణి లో తక్కువ విలువ.

119
00:05:35,320 --> 00:05:38,630
ఈ జరిగే అవకాశం తక్కువ నిర్ధారించడానికి,
మేము ద్వారా ఇరుసు వెదుక్కోవచ్చు

120
00:05:38,630 --> 00:05:42,610
బహుళ అంశాలు మరియు ఎంచుకోవడం
సగటు విలువలను.

121
00:05:42,610 --> 00:05:44,650
>> నా పేరు, మార్క్ Grozen-స్మిత్ ఉంది
మరియు ఈ CS50 ఉంది.

122
00:05:44,650 --> 00:05:47,790

123
00:05:47,790 --> 00:05:50,930
>> సాధారణంగా, యొక్క ఊహించుకోవటం తెలియజేయండి ఆ
విషయాలు కేవలం పూర్ణ, కానీ

124
00:05:50,930 --> 00:05:51,970
ఆ Quicksert తెలుసు -

125
00:05:51,970 --> 00:05:53,160
Quicksert?

126
00:05:53,160 --> 00:05:55,200
క్షమించాలి.

127
00:05:55,200 --> 00:06:02,000
>> ఇక్కడ మేము పూర్ణాంకాల కలిగి
6, 5, 1, 3, 8, 4, 9.

128
00:06:02,000 --> 00:06:03,200
>> SPEAKER 1: రియల్లీ?

129
00:06:03,200 --> 00:06:04,850
>> SPEAKER 2: అక్కడ స్టాప్ లేదు.

130
00:06:04,850 --> 00:06:06,100
>> SPEAKER 1: రియల్లీ?

131
00:06:06,100 --> 00:06:08,491