ஒரு நிரலாக்க முறை குயிக்சார்ட்

1960 ஆம் ஆண்டில், கே ஏ ஹோர், தகவல் விரைவான வரிசையாக்கம் ஒரு முறை உருவாக்கப்பட்டது மிகவும் பிரபலமானார். இன்று பரவலாக, நிரலாக்க பயன்படுத்தப்படுகிறது அது நேர்மறை பண்புகள் ஏராளமானவற்றை அளிக்க வைத்திருப்பதால்: அது பொதுவான நிகழ்வுகளிலான பயன்படுத்த முடியும், அது பட்டியல்கள் பல்வேறு வகையான இணக்கமானது மற்றும் செயல்படுத்துவது எளிதாக கூடுதல் நினைவகத்தில் ஒரு சிறிய அதிகரிப்பு தேவைப்படுகிறது. பயன்படுத்தி மேற்கொள்ளப்படும் பணிகள் தவறுகள் நிறைய அனுமதித்தது, சற்றே நிலையற்றதாக: ஆனால் இது உள்ளது குயிக்சார்ட், குறைபாடாகும்.

எனினும், அது அதிகமும் ஆய்வு பதிப்பாகும். முதல் கட்டணம் Hoare பின்னர், பல அதன் அடர்ந்த ஆய்வு செய்ய. பெரிய அடிப்படை அனுபவ சாட்சியங்களின் மூலம் ஆதரித்தது இது வேலை, செலவிடும் நேரத்தை கண்டறியும் தத்துவார்த்த கேள்விகள் தேதி நிறுவப்பட்டது. அடிப்படை அல்காரிதமாவது மற்றும் அதிகரித்த வேகம் மேம்படுத்த உண்மையான திட்டங்களும் முன்வைக்கப்படவில்லை.

குயிக்சார்ட் அது எல்லா இடங்களிலும் காணலாம், மிகவும் பொதுவானது. அதன் அடிப்படையில் முறை TList.Sort, அனைத்து பதிப்புகள் (தவிர 1) டெல்பி, நேரம் நூலகம் செயல்பாடு அது சி, qsort முடிக்க ++ எடுத்து தற்போது செயல்படுத்தப்படுகிறது.

செயல்படும் அடிப்படை கொள்கை ஒரு "பிளவை" என முறைப்படுத்தலாம். இது இரண்டு குழுக்களாக பட்டியலில் உடைத்து ஏற்படுவதாகவும் மற்றும் தன்னை மூலம் ஒவ்வொரு பாகத்திற்கும் வரிசையாக்கப்பட்டன. ஒரு அடிப்படை உறுப்பு தீர்மானிக்கப்படுகிறது மற்றும் ஒப்பீட்டளவில் அவரது முழு பட்டியலில் மாற்றியமைக்கப்பட்டிருக்கிறது காட்டுகிறது; அதாவது அதிக கவனம் பின்வரும் ஏற்படும் போது பிரித்தெடுத்தல் செயல்பாட்டின், பணம் என்று வேண்டும் பின்வருமாறு. வேட்பாளர்கள் ஒரு குழு இடது கட்டப்பட்ட மதிப்பு மற்ற அனைத்து பரிமாற்ற விதிகள் விட குறைவாக உள்ளது. அது வரிசைப்படுத்தப்பட்ட பட்டியலில் முக்கிய உறுப்பு அதன் உரிமையுள்ள இடத்தில் உள்ளது என்று மாறிவிடும். அடுத்த கட்ட - அடித்தளம் ஆகியவை தொடர்புடைய உறுப்புகள் இருபுறமும் ஒரு சவால் சூத்திர வரிசையாக்கம் செயல்பாடுகளை. அது வரிசைப்படுத்தப்பட்ட வேண்டும், செயல்முறை வேலை பட்டியலில் ஒரே ஒரு உறுப்பு கொண்டிருக்கிறது மட்டுமே முடிவடைகிறது. இவ்வாறு, ஒரு விரைவான வகையான ஒரு நிரலாக்க செயல்பாடு மாஸ்டர் பொருட்டு, அது தேவையான கீழ் நிலை வழிமுறைகள் செயல்களையும் நீ வேண்டும்: அ) அடிப்படை உறுப்பினராக தேர்வு; ஆ) மிகவும் பயனுள்ள வரிசைமாற்றத்தை பட்டியலை சிறிய மற்றும் பெரிய மதிப்புகள் இரண்டு பெட்டிகள் தயாரிக்க.

முதல் கொள்கைகளை பற்றியும் தெரிந்துகொள்ள. அடிப்படை உறுப்பினராக தேர்ந்தெடுக்கும் போது, வெறுமனே சராசரி பட்டியலில் இருந்து தெரிவு செய்யப்பட வேண்டும். பின்னர் உடைந்துள்ளது இரண்டு சம பகுதிகளாக பிரிக்கப்பட்டுள்ளது. வெறும் கணக்கிட சராசரி மதிப்பு பட்டியலில் மிகவும் கடினம், எனவே கூட மிகவேகமான வரிசையாக்கப் இந்த கால்குலஸ் பக்க தவிர்க்கப்பட்டு விடுகிறது. ஆனால் அதிகபட்ச அல்லது குறைந்தபட்ச மதிப்பு அடிப்படை உறுப்பு தேர்வு - கூட சிறந்த விருப்பத்தை. வழக்கில் ஒரு போன்ற உறுதியை காலியாக பட்டியல்கள் உத்தரவாதம் நீக்கப்படும், இரண்டாவது முழு உருவாக்குகிறது. எனவே அடிப்படை உறுப்பினராக சராசரி நெருக்கமாக இருக்கிறது என்று ஒரு தேர்வு வேண்டும் என்று, ஆனால் அதிகபட்ச மற்றும் குறைந்தபட்ச மீது முடிவுக்கு.

ஒரு தேர்வு உறுதி செய்த பின்பு, நீங்கள் சிதைவு வழிமுறை தொடர முடியும். இந்த உள் சுழல்கள் விரைவான வகையான என்று அழைக்கப்படும். எல்லாம் இரண்டு ரேபிட் அணுகல் குறியீடுகளின் அடிப்படையில் கட்டப்பட்டுள்ளது: முதல் வலமிருந்து இருந்து, மாறாக, வலது, இரண்டாவது இடமிருந்து கூறுகள் மேல் போக. நடவடிக்கையானது செயல்படுத்தல் வலது பிகின்ஸ்: குறியீட்டு பட்டியலில் மற்றும் முக்கிய அனைத்து மதிப்புகள் ஒப்பிட்டு. உறுப்பு அடிப்படை குறைவாக அல்லது சமமாக இருக்கும் போது சுழற்சி முடிந்தது. என்று ஒரு ஒப்பீடு உள்ளது மற்றும் குறியீட்டு மதிப்பு குறைகிறது உள்ளது. இடது புறம் வேலை குறைவாக அல்லது அதற்குச் சமமாக மதிப்பு உயர்ந்த முடிந்ததும். இங்கே, ஒப்பீடு மதிப்பு அதிகரிக்கிறது.

குயிக்சார்ட் சூட்சுமமாக பார்டிஷனிங் வழிமுறையின் இந்த கட்டத்தில், இரண்டு சூழ்நிலைகளில் ஏற்படலாம். முதல் இடது குறியீட்டு வலது விட குறைவாக இருப்பது. இந்த பிழை குறிக்கிறது, அது எந்த பட்டியலில் குறிப்பிட்டு விமர்சித்திருந்தார் உறுப்புகள் தவறான முறையில் உள்ளன. வெளியீடு - தங்கள் இடங்களில் மாற்ற. நிரலை இருவரும் சமமாக அல்லது கடந்து போது இரண்டாவது நிலைமை உள்ளது. இந்த பட்டியலில் ஒரு வெற்றிகரமான பிரிப்பு குறிக்கிறது அதாவது, வேலை இப்போது நிறைவடைந்தது.