ஹால்விங் மாநாடு
ஒரு பட்டியலில் உள்ள உறுப்புகளின் எண்ணிக்கை சமமாக இருக்கும்போது, பட்டியலை பாதியாகக் குறைப்பது என்பது பட்டியலின் உண்மையான முதல் பாதி முதல் பாதி, மற்றும் பட்டியலின் இரண்டாவது பாதி இரண்டாவது பாதி. முழு பட்டியலின் நடுத்தர (நடுத்தர) உறுப்பு, முதல் பட்டியலின் கடைசி உறுப்பு. இதன் பொருள் நடுத்தர குறியீடானது நீளம் / 2 - 1 ஆகும், ஏனெனில் குறியீட்டு எண்ணிக்கை பூஜ்ஜியத்திலிருந்து தொடங்குகிறது. நீளம் என்பது பட்டியலில் உள்ள உறுப்புகளின் எண்ணிக்கை. உதாரணமாக, உறுப்புகளின் எண்ணிக்கை 8 ஆக இருந்தால், பட்டியலின் முதல் பாதியில் 4 உறுப்புகளும், இரண்டாவது பாதியில் 4 உறுப்புகளும் உள்ளன. அது நல்லது. குறியீட்டு எண்ணிக்கை 0 இலிருந்து தொடங்குவதால், நடுத்தர குறியீடு 3 = 8 /2 - 1 ஆகும்.
பட்டியல் அல்லது துணைப் பட்டியலில் உள்ள தனிமங்களின் எண்ணிக்கை ஒற்றைப்படை இருக்கும்போது வழக்கைப் பற்றி என்ன? தொடக்கத்தில், நீளம் இன்னும் 2 ஆல் வகுக்கப்படுகிறது. குறியீட்டு எண்ணிக்கை பூஜ்ஜியத்திலிருந்து தொடங்குகிறது. நடுத்தர குறியீடானது நீளம் / 2 - 1/2 வழங்கப்படுகிறது. இது மாநாட்டின் மூலம், இடைக்காலமாக கருதப்படுகிறது. உதாரணமாக, ஒரு பட்டியலில் உள்ள உறுப்புகளின் எண்ணிக்கை 5 ஆக இருந்தால், நடுத்தர குறியீடு 2 = 5/2 - 1/2 ஆகும். மேலும், பட்டியலின் முதல் பாதியில் மூன்று கூறுகளும் இரண்டாம் பாதியில் இரண்டு கூறுகளும் உள்ளன. முழு பட்டியலின் நடுத்தர உறுப்பு குறியீட்டு எண் 2 இல் மூன்றாவது உறுப்பு ஆகும், இது நடுத்தர குறியீடாகும், ஏனெனில் குறியீட்டு எண்ணிக்கை 0 இலிருந்து தொடங்குகிறது.
இந்த வழியில் பிரிவு முழு எண் கணிதத்திற்கு ஒரு எடுத்துக்காட்டு.
மூன்று மதிப்புகளின் சராசரி
கேள்வி: வரிசையின் சராசரி என்ன:
சி பி ஏ
தீர்வு:
பட்டியலை ஏறுவரிசையில் வரிசைப்படுத்துங்கள்:
ஏ பி சி
நடுத்தர கால, பி, சராசரி. இது மற்ற இரண்டு அளவுகளுக்கு இடையில் இருக்கும் அளவு.
ஒரு பட்டியலில் சராசரி தேடுவது அந்த மாதிரி இல்லை. எடுத்துக்காட்டாக, வரிசைப்படுத்தப்படாத 19 உறுப்புகளின் பட்டியலில், முதல் உறுப்பு, நடுத்தர உறுப்பு மற்றும் கடைசி உறுப்புக்கான சராசரி தேவைப்படலாம். இந்த மூன்று மதிப்புகள் ஏறுவரிசையில் இருக்காது; எனவே, அவற்றின் குறியீடுகள் கணக்கில் எடுத்துக்கொள்ளப்பட வேண்டும்.
விரைவான வரிசைப்படுத்தலுடன், முழு பட்டியல் மற்றும் துணைப் பட்டியல்களுக்கான சராசரி தேவைப்படுகிறது. ஒரு பட்டியலில் (வரிசை) இடைவெளியில் உள்ள மூன்று மதிப்புகளின் சராசரியைத் தேடும் சூடோகோட்:
நடுவில்: =.(குறைந்த+உயர்) / 2.என்றால்அர்[நடுவில்] <அர்[குறைந்த]
இடமாற்று[குறைந்த]உடன்[நடுவில்]
என்றால்அர்[உயர்] <அர்[குறைந்த]
இடமாற்று[குறைந்த]உடன்[உயர்]
என்றால்அர்[நடுவில்] <அர்[உயர்]
இடமாற்று[நடுவில்]உடன்[உயர்]
மையம்: =அர்[உயர்]
அர் என்ற சொல்லுக்கு வரிசை என்று பொருள். இந்த குறியீடு பிரிவு இடைநிலை தேடுகிறது மற்றும் சில வரிசையாக்கத்தையும் செய்கிறது. இந்த குறியீடு பிரிவு எளிமையானதாக தோன்றுகிறது, ஆனால் இது மிகவும் குழப்பமானதாக இருக்கும். எனவே, பின்வரும் விளக்கத்திற்கு கவனம் செலுத்துங்கள்:
இந்த டுடோரியலில் வரிசைப்படுத்துவது ஒரு பட்டியலை உருவாக்கும், அங்கு முதல் மதிப்பு மிகச்சிறிய மதிப்பு, மற்றும் கடைசி மதிப்பு மிகப்பெரிய மதிப்பு. எழுத்துக்களுடன், A என்பது Z ஐ விட குறைவாக உள்ளது.
இங்கே, மையம் அதன் விளைவாக வரும் சராசரி. பட்டியல் என்பது பட்டியல் அல்லது துணைப் பட்டியலின் குறைந்த குறியீடாகும் (குறைந்த மதிப்புக்கு அவசியமில்லை); பட்டியல் அல்லது துணைப் பட்டியலின் உயர்ந்த குறியீடானது உயர்ந்தது (மிக உயர்ந்த மதிப்புக்கு அவசியமில்லை), மற்றும் நடுத்தரமானது வழக்கமான நடுத்தர குறியீடாகும் (முழு பட்டியலின் நடுத்தர மதிப்புக்கு அவசியமில்லை).
எனவே, பெறப்பட வேண்டிய சராசரி குறைந்த குறியீட்டின் மதிப்பு, நடுத்தர குறியீட்டின் மதிப்பு மற்றும் உயர்ந்த குறியீட்டின் மதிப்பு ஆகியவற்றுக்கு இடையே உள்ளது.
குறியீட்டில், வழக்கமான நடுத்தர குறியீடு முதலில் பெறப்படுகிறது. இந்த தொடக்கத்தில், பட்டியல் வரிசைப்படுத்தப்படவில்லை. மூன்று மதிப்புகளின் ஏறுவரிசையில் ஒப்பீடு மற்றும் சில மறுசீரமைப்பு ஒரே நேரத்தில் நடக்க வேண்டும். முதல் if- அறிக்கை குறைந்த குறியீட்டுக்கான மதிப்பை மற்றும் நடுத்தர குறியீட்டின் மதிப்பை ஒப்பிடுகிறது. நடுத்தர குறியீடானது குறைந்த குறியீட்டை விட குறைவாக இருந்தால், இரண்டு மதிப்புகளும் இடங்களை மாற்றுகின்றன. இது வரிசைப்படுத்தத் தொடங்குகிறது மற்றும் பட்டியல் அல்லது துணைப் பட்டியலில் உள்ள மதிப்புகளின் அமைப்பை மாற்றுகிறது. இரண்டாவது if- அறிக்கை மிக உயர்ந்த குறியீட்டிற்கான மதிப்பை ஒப்பிடுகிறது மற்றும் குறைந்த குறியீட்டின் மதிப்பை ஒப்பிடுகிறது. மிக உயர்ந்த குறியீடானது குறைந்த குறியீட்டை விட குறைவாக இருந்தால், இரண்டு மதிப்புகளும் இடங்களை மாற்றுகின்றன. இது சில வரிசைப்படுத்தல் மற்றும் பட்டியல் அல்லது துணை பட்டியலில் உள்ள மதிப்புகளின் ஏற்பாட்டை மாற்றுகிறது. மூன்றாவது if- அறிக்கை நடுத்தர குறியீட்டுக்கான மதிப்பை ஒப்பிடுகிறது மற்றும் உயர்ந்த குறியீட்டின் மதிப்பை ஒப்பிடுகிறது. உயர்ந்த குறியீடானது நடுத்தர குறியீட்டை விட குறைவாக இருந்தால், இரண்டு மதிப்புகளும் இடங்களை மாற்றுகின்றன. சில வரிசைப்படுத்தல் அல்லது மறுசீரமைப்பும் இங்கு நிகழலாம். இந்த மூன்றாவது if- நிபந்தனை முந்தைய இரண்டைப் போல் இல்லை.
இந்த மூன்று இடமாற்றங்களின் முடிவில், கேள்விக்குரிய மூன்று மதிப்புகளின் நடுத்தர மதிப்பு A [உயர்] ஆக இருக்கும், அதன் அசல் உள்ளடக்கம் குறியீடு பிரிவில் மாற்றப்பட்டிருக்கலாம். எடுத்துக்காட்டாக, வரிசைப்படுத்தப்படாத வரிசையைக் கவனியுங்கள்:
சி பி ஏ
சராசரி பி என்பது எங்களுக்கு ஏற்கனவே தெரியும். இருப்பினும், இது நிரூபிக்கப்பட வேண்டும். மேலே உள்ள குறியீட்டுப் பிரிவைப் பயன்படுத்தி இந்த மூன்று மதிப்புகளின் சராசரியைப் பெறுவதே இங்கு நோக்கம். முதல் if- அறிக்கை B மற்றும் C. ஐ ஒப்பிடுகையில் B C ஐ விட குறைவாக இருந்தால், B மற்றும் C இன் நிலைகள் மாற்றப்பட வேண்டும். B C ஐ விட குறைவாக உள்ளது, எனவே புதிய ஏற்பாடு ஆகிறது:
பி சி ஏ
கவனிக்கவும், குறைந்த குறியீட்டு மற்றும் நடுத்தர குறியீட்டுக்கான மதிப்புகள் மாறிவிட்டன. இரண்டாவது if- அறிக்கை A மற்றும் B. உடன் ஒப்பிடுகையில் A B ஐ விட குறைவாக இருந்தால், A மற்றும் B இன் நிலைகளை மாற்ற வேண்டும். A B ஐ விட குறைவாக உள்ளது, எனவே புதிய ஏற்பாடு ஆகிறது:
ஏ சி பி
கவனிக்கவும், உயர்ந்த குறியீட்டு மற்றும் குறைந்த குறியீட்டின் மதிப்புகள் மாறிவிட்டன. மூன்றாவது if- அறிக்கை C மற்றும் B. ஐ ஒப்பிடுகையில் C B ஐ விட குறைவாக இருந்தால், C மற்றும் B இன் நிலைகளை மாற்ற வேண்டும். சி B ஐ விட குறைவாக இல்லை, எனவே இடமாற்றம் எதுவும் நடக்காது. புதிய ஏற்பாடு முந்தையதைப் போலவே உள்ளது, அதாவது:
ஏ சி பி
B என்பது சராசரி, அதாவது A எனவே, மையப்புள்ளி பட்டியல் அல்லது துணைப் பட்டியலின் தீவிர முடிவில் பிறக்கிறது.
இடமாற்று செயல்பாடு
விரைவு வரிசைப்படுத்தலுக்குத் தேவைப்படும் மற்றொரு அம்சம் இடமாற்று செயல்பாடு ஆகும். பரிமாற்ற செயல்பாடு, இரண்டு மாறிகளின் மதிப்புகளை பரிமாறிக்கொள்ளும். இடமாற்ற செயல்பாட்டிற்கான போலி குறியீடு:
இடமாற்றத்தை வரையறுக்கவும்(எக்ஸ்,மற்றும்)தற்காலிக: =எக்ஸ்
எக்ஸ்: =மற்றும்
மற்றும்: =தற்காலிக
இங்கே, x மற்றும் y என்பது உண்மையான மதிப்புகளைக் குறிக்கிறது, நகல்களை அல்ல.
இந்த கட்டுரையில் வரிசைப்படுத்துவது ஒரு பட்டியலை உருவாக்கும், அங்கு முதல் மதிப்பு மிகச்சிறிய மதிப்பு, மற்றும் கடைசி மதிப்பு மிகப்பெரிய மதிப்பு.
கட்டுரை உள்ளடக்கம்
- விரைவு வரிசைமுறை அல்காரிதம்
- ஒரு பகிர்வு போலி குறியீடு
- விரைவு வரிசையின் விளக்கம்
- ஜாவா கோடிங்
- முடிவுரை
விரைவு வரிசைமுறை அல்காரிதம்
வரிசைப்படுத்தப்படாத பட்டியலை வரிசைப்படுத்துவதற்கான சாதாரண வழி முதல் இரண்டு மதிப்புகளைக் கருத்தில் கொள்வதாகும். அவை ஒழுங்காக இல்லை என்றால், அவற்றை ஒழுங்குபடுத்துங்கள். அடுத்து, முதல் மூன்று மதிப்புகளைக் கவனியுங்கள். மூன்றாவது மதிப்பு எங்கு பொருந்துகிறது என்பதைப் பார்க்க முதல் இரண்டை ஸ்கேன் செய்து அதை சரியாகப் பொருத்தவும். பின்னர், முதல் நான்கு மதிப்புகளைக் கருதுங்கள். நான்காவது மதிப்பு எங்கு பொருந்துகிறது என்பதைப் பார்க்க முதல் மூன்று மதிப்புகளை ஸ்கேன் செய்து சரியான முறையில் பொருத்தவும். முழு பட்டியலும் வரிசைப்படுத்தப்படும் வரை இந்த நடைமுறையைத் தொடரவும்.
கம்ப்யூட்டர் புரோகிராமிங் பேச்சுவழக்கில், ப்ரூட்-ஃபோர்ஸ் வரிசை என்றும் அழைக்கப்படும் இந்த செயல்முறை மிகவும் மெதுவாக உள்ளது. விரைவு வரிசைமுறை வழிமுறை மிக வேகமான செயல்முறையுடன் வருகிறது.
குவிக்சார்ட் வழிமுறையின் படிகள் பின்வருமாறு:
- வரிசைப்படுத்தப்படாத பட்டியலில் வரிசைப்படுத்த குறைந்தது 2 எண்கள் உள்ளனவா என்பதை உறுதிப்படுத்தவும்.
- பிவோட் எனப்படும் பட்டியலுக்கு மதிப்பிடப்பட்ட மைய மதிப்பைப் பெறுங்கள். சராசரி, மேலே விவரிக்கப்பட்டுள்ளபடி, மையத்தைப் பெறுவதற்கான ஒரு வழியாகும். வெவ்வேறு வழிகளில் அவற்றின் நன்மைகள் மற்றும் தீமைகள் உள்ளன. - பிறகு பார்க்கலாம்.
- பட்டியலைப் பிரிக்கவும். இதன் பொருள், பட்டியலில் மையத்தை வைக்கவும். அந்த வகையில், இடதுபுறத்தில் உள்ள அனைத்து உறுப்புகளும் பிவோட் மதிப்பை விட குறைவாக இருக்கும், மேலும் வலதுபுறத்தில் உள்ள அனைத்து உறுப்புகளும் பிவோட் மதிப்பை விட அதிகமாகவோ அல்லது சமமாகவோ இருக்கும். பகிர்வுக்கு பல்வேறு வழிகள் உள்ளன. ஒவ்வொரு பகிர்வு முறையும் அதன் நன்மைகள் மற்றும் தீமைகளுடன் வருகிறது. பிரித்தல் என்பது பிரித்து வெல்லும் முன்மாதிரியாக பிரிக்கிறது.
- முழு பட்டியல் வரிசைப்படுத்தப்படும் வரை வெளிவரும் புதிய துணைப் பட்டியல் ஜோடிகளுக்கு 1, 2 மற்றும் 3 படிகளை மீண்டும் செய்யவும். இது பிரித்து வெல்லும் முன்மாதிரியில் ஜெயிக்கிறது.
விரைவு வரிசைப்படுத்தல் சூடோகோட்:
அல்காரிதம் குவிக்சர்ட்(அர்,குறைந்த,உயர்)இருக்கிறதுஎன்றால்குறைந்த<அப்போது உயர்
மையம்(குறைந்த,உயர்)
ப: =பகிர்வு(அர்,குறைந்த,உயர்)
குவிக்சார்ட்(அர்,குறைந்த,ப- 1)
குவிக்சார்ட்(அர்,ப+ 1,உயர்)
ஒரு பகிர்வு போலி குறியீடு
இந்த டுடோரியலில் பயன்படுத்தப்படும் பகிர்வு சூடோகோட்:
அல்காரிதம் பகிர்வு(அர்,குறைந்த,உயர்)இருக்கிறதுமையம்: =அர்[உயர்]
நான்: =குறைந்த
ஜெ: =உயர்
செய்
செய்
++நான்
போது(அர்[நான்] <மையம்)
செய்
-ஜெ
போது(அர்[ஜெ] >மையம்)
என்றால் (நான்<ஜெ)
இடமாற்று[நான்]உடன்[ஜெ]
போது(நான்<ஜெ)
இடமாற்று[நான்]உடன்[உயர்]
திரும்பநான்
கீழே உள்ள விரைவு வரிசை விளக்கத்தில், இந்த குறியீடு பயன்படுத்தப்படுகிறது:
விரைவு வரிசையின் விளக்கம்
அகரவரிசை எழுத்துக்களின் பின்வரும் வரிசைப்படுத்தப்படாத பட்டியலை (வரிசை) கவனியுங்கள்:
Q W E R T Y U I O P
ஆய்வு மூலம், வரிசைப்படுத்தப்பட்ட பட்டியல்:
E I O P Q R T U W Y
வரிசைப்படுத்தப்பட்ட பட்டியலில் இருந்து, மேலே உள்ள அல்காரிதம் மற்றும் சூடோகோட் பிரிவுகளைப் பயன்படுத்தி, வரிசைப்படுத்தப்பட்ட பட்டியல் இப்போது நிரூபிக்கப்படும்:
Q W E R T Y U I O P
முதல் மையம் arr [0] = Q, arr [4] = T, மற்றும் arr [9] = P இலிருந்து தீர்மானிக்கப்படுகிறது, மேலும் Q ஆக அடையாளம் காணப்பட்டு பட்டியலின் தீவிர வலதுபுறத்தில் வைக்கப்படுகிறது. எனவே, எந்த முக்கிய செயல்பாட்டு வரிசைப்படுத்தலுடனும் பட்டியல் ஆகிறது:
P W E R T Y U I O Q
தற்போதைய மையப்பகுதி கே. பிவோட் செயல்முறை சில சிறிய வரிசையாக்கங்களை செய்து முதல் இடத்தில் பி வைத்தது. இதன் விளைவாக பட்டியலை மறுசீரமைக்க வேண்டும் (பகிர்வு), அதாவது, இடதுபுறத்தில் உள்ள அனைத்து உறுப்புகளும் மதிப்பில் சிறியதாக இருக்கும், பின்னர் பிவோட் மற்றும் பிவோட்டின் வலதுபுறத்தில் உள்ள அனைத்து உறுப்புகளும் பிவோட்டுக்கு சமமாகவோ அல்லது அதிகமாகவோ இருக்கும். கணினி ஆய்வு மூலம் பகிர்வு செய்ய முடியாது. எனவே, இது குறியீடுகள் மற்றும் மேலே உள்ள பகிர்வு வழிமுறையைப் பயன்படுத்துகிறது.
குறைந்த மற்றும் உயர் குறியீடுகள் இப்போது 0 மற்றும் 9. ஆகையால், கணினி ஒரு குறியீட்டை அடையும் வரை குறியீட்டு 0 இலிருந்து ஸ்கேன் செய்வதன் மூலம் தொடங்கும், அதன் மதிப்பு பிவோட்டுக்கு சமமாக அல்லது அதிகமாக இருக்கும் மற்றும் தற்காலிகமாக அங்கேயே நின்றுவிடும். இது உயர் (வலது) முனையிலிருந்து, குறியீட்டு 9, கீழே வரும், ஸ்கேன் செய்யும், அது ஒரு குறியீட்டை அடையும் வரை அதன் மதிப்பை விட குறைவாக அல்லது சமமாக இருக்கும் மற்றும் தற்காலிகமாக அங்கு நிறுத்தப்படும். இதன் பொருள் நிறுத்தத்தின் இரண்டு நிலைகள். நான், அதிகரிக்கும் குறியீட்டு மாறியானது, குறையும் குறியீட்டு மாறியை விட சமமாகவோ அல்லது அதிகமாகவோ இல்லை என்றால், j உயர்வில் இருந்து இருந்தால், இந்த இரண்டு மதிப்புகளும் மாற்றப்படும். தற்போதைய சூழ்நிலையில், இரு முனைகளிலிருந்தும் ஸ்கேன் செய்வது W மற்றும் O இல் நிறுத்தப்பட்டது. அதனால் பட்டியல் ஆகிறது:
P O E R T Y U I W Q
முன்னுரிமை இன்னும் கே. எதிர் திசைகளில் ஸ்கேனிங் தொடர்கிறது மற்றும் அதன்படி நிறுத்தப்படும். நான் இன்னும் j க்கு சமமாகவோ அல்லது அதிகமாகவோ இல்லை என்றால், இரண்டு முனைகளிலிருந்தும் ஸ்கேன் செய்வது நிறுத்தப்பட்ட இரண்டு மதிப்புகள் மாற்றப்படும். இந்த முறை, இரு முனைகளிலிருந்தும் ஸ்கேன் செய்வது R மற்றும் I இல் நிறுத்தப்பட்டது. எனவே, பட்டியலின் ஏற்பாடு ஆகிறது:
P O E I T Y U R W Q
முன்னுரிமை இன்னும் கே. எதிர் திசைகளில் ஸ்கேனிங் தொடர்கிறது மற்றும் அதன்படி நிறுத்தப்படும். நான் j க்கு சமமாகவோ அல்லது அதிகமாகவோ இல்லை என்றால், ஸ்கேனிங் நிறுத்தப்பட்ட இரண்டு மதிப்புகள் மாற்றப்படும். இந்த முறை, இரு முனைகளிலிருந்தும் ஸ்கேன் செய்வது T க்கு i மற்றும் i க்கு j. i மற்றும் j சந்தித்தது அல்லது கடந்துவிட்டது. எனவே, இடமாற்றம் செய்ய முடியாது. பட்டியல் அப்படியே உள்ளது:
P O E I T Y U R W Q
இந்த கட்டத்தில், மையம், கே, வரிசைப்படுத்துவதில் அதன் இறுதி நிலையில் வைக்கப்பட வேண்டும். இது arr [i] ஐ arr [high] உடன் மாற்றுவது, T மற்றும் Q ஐ மாற்றுவதன் மூலம் செய்யப்படுகிறது. பட்டியல் ஆகிறது:
P O E I Q Y U R W T
இந்த கட்டத்தில், முழு பட்டியலுக்கான பகிர்வு முடிந்தது. பிவோட் = க்யூ அதன் பங்கைக் கொண்டுள்ளது. இப்போது மூன்று துணைப் பட்டியல்கள் உள்ளன, அவை:
P O E I Q Y U R W T
பகிர்வு என்பது முன்மாதிரியில் பிரிவு மற்றும் வெற்றி (வரிசைப்படுத்துதல்) ஆகும். கே அதன் சரியான வரிசைப்படுத்தல் நிலையில் உள்ளது. Q இன் இடதுபுறத்தில் உள்ள ஒவ்வொரு உறுப்பும் Q ஐ விடச் சிறியது, மற்றும் Q இன் வலதுபுறத்தில் உள்ள ஒவ்வொரு உறுப்பும் Q ஐ விட பெரியது. இருப்பினும், இடது பட்டியல் இன்னும் வரிசைப்படுத்தப்படவில்லை; சரியான பட்டியல் இன்னும் வரிசைப்படுத்தப்படவில்லை. இடது துணைப் பட்டியலையும் வலது துணைப் பட்டியலையும் வரிசைப்படுத்த முழு விரைவு வரிசைச் செயல்பாட்டையும் திரும்பத் திரும்ப அழைக்க வேண்டும். விரைவு வரிசையின் இந்த நினைவூட்டல் தொடர வேண்டும்; முழு அசல் பட்டியலும் முழுமையாக வரிசைப்படுத்தப்படும் வரை புதிய துணைப் பட்டியல்கள் உருவாகும். விரைவு வரிசை செயல்பாட்டின் ஒவ்வொரு நினைவுகூரலுக்கும், தொடர்புடைய வலது துணைப் பட்டியலைச் சேர்ப்பதற்கு முன், முதலில் இடது துணைப் பட்டியல் கவனிக்கப்படுகிறது. ஒவ்வொரு துணைப் பட்டியலுக்கும் ஒரு புதிய மையம் பெறப்பட வேண்டும்.
துணைப் பட்டியலுக்கு:
பி ஓ ஈ ஐ
P, O மற்றும் I க்கான மையம் (சராசரி) தீர்மானிக்கப்படுகிறது. முன்னுரிமை ஓ. 4-1] = arr [3], நான் முந்தைய பகிர்வில் இருந்து இறுதி மைய குறியீடாக இருக்கிறேன். பிவோட் () செயல்பாடு அழைக்கப்பட்ட பிறகு, புதிய பிவோட் மதிப்பு, பிவோட் = ஓ. பிவோட் செயல்பாட்டிற்கும் பிவோட் மதிப்புக்கும் இடையில் குழப்பமடைய வேண்டாம். பிவோட் செயல்பாடு சில சிறிய வரிசையாக்கங்களைச் செய்யலாம் மற்றும் துணைப் பட்டியலின் தீவிர வலதுபுறத்தில் மையத்தை வைக்கலாம். இந்த துணை பட்டியல் ஆகிறது,
ஐ பி ஈ ஓ
இந்த திட்டத்தின் மூலம், மையம் எப்போதும் துணைப் பட்டியல் அல்லது அதன் செயல்பாட்டு அழைப்புக்குப் பிறகு பட்டியலின் வலது முனையில் முடிவடையும். இரண்டு முனைகளிலிருந்தும் ஸ்கேனிங் ஆர் [0] மற்றும் ஆர் [3] இல் தொடங்கி i மற்றும் j சந்திப்பு அல்லது குறுக்கு வரை. ஒப்பீடு பிவோட் = ஓ.
நான் ஈ பி ஓ
இரு முனைகளிலிருந்தும் ஸ்கேனிங் தொடர்கிறது, மேலும் புதிய நிறுத்தங்கள் P க்கு i மற்றும் E க்கு j. இப்போது நானும் j யும் சந்தித்தோம் அல்லது கடந்துவிட்டோம். எனவே துணைப் பட்டியல் அப்படியே உள்ளது:
நான் ஈ பி ஓ
பிவோட் அதன் இறுதி நிலையில் வைக்கப்படும்போது ஒரு துணைப் பட்டியல் அல்லது பட்டியலின் பகிர்வு முடிவடைகிறது. எனவே, arr [i] மற்றும் arr [high] க்கான புதிய மதிப்புகள் மாற்றப்பட்டுள்ளன. அதாவது, பி மற்றும் ஓ மாற்றப்பட்டது. புதிய துணை பட்டியல் ஆகிறது:
ஐ ஈ ஓ பி
O இப்போது முழு பட்டியலுக்கும் அதன் இறுதி நிலையில் உள்ளது. ஒரு மையமாக அதன் பங்கு முடிந்தது. துணைப் பட்டியல் தற்போது மேலும் மூன்று பட்டியல்களாகப் பிரிக்கப்பட்டுள்ளது, அவை:
ஐ ஈ ஓ பி
இந்த கட்டத்தில், முதல் வலது துணைப் பட்டியலின் விரைவு வரிசைமுறை அழைக்கப்பட வேண்டும். எனினும், அது அழைக்கப்படாது. அதற்குப் பதிலாக, அது குறிப்பிடப்பட்டு முன்பதிவு செய்யப்படும், பின்னர் அழைக்கப்படும். பகிர்வு செயல்பாட்டின் அறிக்கைகள் செயல்படுத்தப்படும் போது, செயல்பாட்டின் மேலிருந்து, இடது துணைப் பட்டியலுக்கான விரைவு வரிசைமுறை இப்போது அழைக்கப்பட வேண்டும் (பிவோட் () அழைக்கப்பட்ட பிறகு). இது பட்டியலுக்கு அழைக்கப்படும்:
நான் ஈ
இது I மற்றும் E இன் சராசரி தேடுவதன் மூலம் தொடங்கும். , I. இருப்பினும், மேலே உள்ள பிவோட் சூடோகோட் ஈ என பிவோட்டை தீர்மானிக்கும். இந்த பிழை இங்கு நிகழ்கிறது, ஏனெனில் மேலே உள்ள சூடோக்கோட் இரண்டு கூறுகளுக்கு அல்ல. கீழே உள்ள செயல்பாட்டில், குறியீட்டில் சில சரிசெய்தல் உள்ளது. துணை பட்டியல் ஆகிறது,
ஈ நான்
பிவோட் எப்போதும் துணைப் பட்டியல் அல்லது அதன் செயல்பாட்டு அழைப்புக்குப் பிறகு பட்டியலின் வலது முனையில் முடிவடையும். இரண்டு முனைகளிலிருந்தும் ஸ்கேனிங் என்பது ஆர் [0] மற்றும் அர் [1] இலிருந்து தொடங்கி i மற்றும் j சந்திப்பு அல்லது குறுக்கு வரை. ஒப்பீடு pivot = I உடன் செய்யப்படுகிறது. முதல் மற்றும் ஒரே நிறுத்தங்கள் I மற்றும் E: I க்கு I மற்றும் E க்கு j. இப்போது நானும் j யும் சந்தித்தோம் அல்லது கடந்துவிட்டோம். எனவே, துணைப் பட்டியல் அப்படியே உள்ளது:
ஈ நான்
பிவோட் அதன் இறுதி நிலையில் வைக்கப்படும்போது ஒரு துணைப் பட்டியல் அல்லது பட்டியலின் பகிர்வு முடிவடைகிறது. எனவே, arr [i] மற்றும் arr [high] க்கான புதிய மதிப்புகள் மாற்றப்பட்டுள்ளன. அது இங்கே நடக்கும், அர் [i] = I மற்றும் arr [high] = I. எனவே, அதே மதிப்பு தன்னுடன் மாற்றப்படுகிறது. புதிய துணை பட்டியல் ஆகிறது:
ஈ நான்
நான் இப்போது முழு பட்டியலுக்கும் அதன் இறுதி நிலையில் இருக்கிறேன். ஒரு மையமாக அதன் பங்கு முடிந்தது. துணைப் பட்டியல் இப்போது மேலும் இரண்டு பட்டியல்களாகப் பிரிக்கப்பட்டுள்ளது, அதாவது,
ஈ நான்
இப்போது, இதுவரையில் முன்னுரிமைகள் Q, O மற்றும் I. பிவோட்கள் அவற்றின் இறுதி நிலைகளில் முடிவடைகின்றன. மேலே உள்ள பி போன்ற ஒரு தனிமத்தின் துணைப் பட்டியலும் அதன் இறுதி நிலையில் முடிகிறது.
இந்த கட்டத்தில், முதல் இடது துணை பட்டியல் முற்றிலும் வரிசைப்படுத்தப்பட்டுள்ளது. வரிசைப்படுத்தும் செயல்முறை இப்போது உள்ளது:
E I O P Q Y U R W T
முதல் வலது துணை பட்டியல்:
Y U R W T
இன்னும் வரிசைப்படுத்த வேண்டும்.
முதல் வலது துணைப் பட்டியலை வெல்வது
முதல் வலது துணைப் பட்டியலுக்கான விரைவு வரிசை அழைப்பு கவனிக்கப்பட்டு, செயல்படுத்தப்படுவதற்குப் பதிலாக ஒதுக்கப்பட்டது என்பதை நினைவில் கொள்ளவும். இந்த கட்டத்தில், அது செயல்படுத்தப்படும். மேலும், புதிய ஆரர் [லோ] = ஆர்ஆர் [5] = அர் [QPivotIndex+1], மற்றும் புதிய ஆர் [உயர்] அர் [9] ஆக உள்ளது. முதல் இடது துணைப் பட்டியலுக்கு நடந்த அதே போன்ற செயல்களின் தொகுப்பு இங்கே நடக்கும். இந்த முதல் வலது துணைப் பட்டியல் வரிசைப்படுத்தப்பட்டுள்ளது:
ஆர் டி யு டபிள்யு ஒய்
அசல் வரிசைப்படுத்தப்படாத பட்டியல் வரிசைப்படுத்தப்பட்டுள்ளது:
E I O P Q R T U W Y
ஜாவா கோடிங்
ஜாவாவில் அல்காரிதம் வைப்பது மேலே உள்ள அனைத்து சூடோகோட் பிரிவுகளையும் ஒரு வகுப்பில் ஜாவா முறைகளில் வைப்பது. வகுப்பில் வரிசைப்படுத்தப்படாத வரிசையுடன் குவிக்சார்ட் () செயல்பாட்டை அழைக்கும் ஒரு முக்கிய () முறை இருக்க வேண்டும் என்பதை மறந்துவிடாதீர்கள்.
மையம் () முறை
ஜாவா பிவோட் () முறை, மதிப்பை வழங்கும், பின்வருமாறு இருக்க வேண்டும்:
வெற்றிடம்மையம்(கரிஅர்[], intகுறைந்த, intஉயர்) {intநடுவில்= (குறைந்த+உயர்) / 2;
என்றால் (அர்[நடுவில்] <அர்[குறைந்த])
இடமாற்றம்(அர்,குறைந்த,நடுவில்);
என்றால் (அர்[உயர்] <அர்[குறைந்த])
இடமாற்றம்(அர்,குறைந்த,உயர்);
என்றால் ((உயர்-குறைந்த) > 2) {
என்றால் (அர்[நடுவில்] <அர்[உயர்])
இடமாற்றம்(அர்,நடுவில்,உயர்);
}
}
இடமாற்று () முறை
இடமாற்று () முறை இருக்க வேண்டும்:
வெற்றிடம்இடமாற்றம்(கரிஅர்[], intஎக்ஸ், intமற்றும்) {கரிதற்காலிக=அர்[எக்ஸ்];
அர்[எக்ஸ்] =அர்[மற்றும்];
அர்[மற்றும்] =தற்காலிக;
}
குவிக்சார்ட் () முறை
குவிக்சார்ட் () முறை இருக்க வேண்டும்:
வெற்றிடம்குவிக்சார்ட்(கரிஅர்[], intகுறைந்த, intஉயர்) {என்றால் (குறைந்த<உயர்) {
மையம்(அர்,குறைந்த,உயர்);
intப=பகிர்வு(அர்,குறைந்த,உயர்);
குவிக்சார்ட்(அர்,குறைந்த,ப- 1);
குவிக்சார்ட்(அர்,ப+ 1,உயர்);
}
}
பகிர்வு () முறை
பகிர்வு () முறை இருக்க வேண்டும்:
intபகிர்வு(கரிஅர்[], intகுறைந்த, intஉயர்) {கரிமையம்=அர்[உயர்];
intநான்=குறைந்த;
intஜெ=உயர்;
செய் {
செய்
++நான்;
போது(அர்[நான்] <மையம்);
செய்
-ஜெ;
போது(அர்[ஜெ] >மையம்);
என்றால் (நான்<ஜெ)
இடமாற்றம்(அர்,நான்,ஜெ);
}போது(நான்<ஜெ);
இடமாற்றம்(அர்,நான்,உயர்);
திரும்பநான்;
}
முக்கிய () முறை
முக்கிய () முறை இருக்க முடியும்:
பொதுநிலையான வெற்றிடம்முக்கிய(லேசான கயிறு[]வாதிடுகிறார்) {கரிஅர்[] = {'கே', 'IN', 'மற்றும்', 'ஆர்', 'டி', 'மற்றும்', 'யு', 'நான்', 'அல்லது', 'பி'};
வகுப்பு விரைவு வரிசை= புதியவகுப்பு();
விரைவு வரிசைகுவிக்சார்ட்(அர், 0, 9);
அமைப்பு.வெளியே.println('வரிசைப்படுத்தப்பட்ட கூறுகள்:');
க்கான(intநான்=0;நான்<10;நான்++) {
அமைப்பு.வெளியே.அச்சு(அர்[நான்]);அமைப்பு.வெளியே.அச்சு('');
}
அமைப்பு.வெளியே.println();
}
மேலே உள்ள அனைத்து முறைகளையும் ஒரே வகுப்பில் சேர்க்கலாம்.
முடிவுரை
விரைவு வரிசைப்படுத்தல் என்பது பிரித்தல் மற்றும் வெல்லும் முன்னுதாரணத்தைப் பயன்படுத்தும் ஒரு வரிசைப்படுத்தும் வழிமுறையாகும். இது வரிசைப்படுத்தப்படாத பட்டியலை இரண்டு அல்லது மூன்று துணைப் பட்டியல்களாகப் பிரிப்பதன் மூலம் தொடங்குகிறது. இந்த டுடோரியலில், விரைவு வரிசை ஒரு பட்டியலை மூன்று துணைப் பட்டியல்களாகப் பிரித்துள்ளது: இடது துணைப் பட்டியல், ஒற்றை தனிமத்தின் நடுத்தரப் பட்டியல் மற்றும் சரியான துணைப் பட்டியல். விரைவு வரிசையில் வெல்வது என்பது ஒரு முக்கிய மதிப்பைப் பயன்படுத்தி, வரிசைப்படுத்தும் போது ஒரு பட்டியல் அல்லது துணைப் பட்டியலைப் பிரித்தல் ஆகும். இந்த டுடோரியல் ஜாவா கணினி மொழியில் விரைவு வரிசைப்படுத்தலின் ஒரு செயல்பாட்டை விளக்கியுள்ளது.
எழுத்தாளர் பற்றி
கிரிசாந்தஸ் ஃபோர்ச்சா
முதல் கொள்கைகள் மற்றும் தொடர்புடைய தொடர்களிலிருந்து கணித ஒருங்கிணைப்பை கண்டுபிடித்தவர். எலக்ட்ரானிக்ஸ் மற்றும் கணினி மென்பொருளில் நிபுணத்துவம் பெற்ற தொழில்நுட்பக் கல்வியில் முதுகலை பட்டம். பிஎஸ்சி எலக்ட்ரானிக்ஸ். கம்ப்யூட்டிங் மற்றும் டெலிகம்யூனிகேஷனில் முதுநிலை மட்டத்தில் எனக்கு அறிவும் அனுபவமும் உள்ளது. 20,000 எழுத்தாளர்களில், நான் devarticles.com இல் 37 வது சிறந்த எழுத்தாளராக இருந்தேன். நான் 10 ஆண்டுகளுக்கும் மேலாக இந்தத் துறைகளில் பணியாற்றி வருகிறேன்.
அனைத்து இடுகைகளையும் பார்க்கவும்தொடர்புடைய லினக்ஸ் குறிப்பு இடுகைகள்
- ஜாவாவில் சரங்களை ஒப்பிடுதல்
- ஜாவாவில் ஹாஷ்மேப்பை எவ்வாறு பயன்படுத்துவது
- ஜாவாவில் விரைவான வரிசை விளக்கப்பட்டது
- ஜாவாவில் பைனரி மரம் முன்கூட்டிய ஆர்டர்
- ஜாவாவில் வரிசைப்படுத்தல் விளக்கப்பட்டது
- ஜாவாவில் ஸ்கேனரை எவ்வாறு பயன்படுத்துவது
- ஜாவா கோப்பில் எழுதுங்கள்