வரிசையாக்கப் படிமுறை

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

வெளியீடானது குறைவல்லாத வரிசையில் இருத்தல் வேண்டும் (ஒவ்வொரு தனிமமும் முந்தைய தனிமங்களைக் காட்டிலும் சிறிய அளவில் இருத்தல் கூடாது);
வெளியீடானது உள்ளீட்டிலிருந்து வரிசை மாறியோ அல்லது மறு வரிசையிலோ இருக்கலாம்.

1956 ஆம் ஆண்டிற்கு முன்பாக குமிழி வரிசையாக்கம் பல்வேறு அறிஞர்களால் ஆராயப்பட்டது.^[1] பலரும் அதை ஒரு தீர்க்கப்பட்ட பிரச்சனையாகவே கருதினார்கள், இருப்பினும் புதிய வரிசையாக்கப் படிமுறைகள் இன்னமும் கண்டுபிடிக்கப்பட்டு வருகின்றன (உதாரணமாக, 2004 ஆம் ஆண்டில் நூலக வரிசையாக்கம் முதன் முதலில் கண்டறியப்பட்டது). வரிசையாக்கப் படிமுறைகள் ஆரம்பத்தில் கணிப்பொறி அறிவியல் வகுப்புகளில் பரவலாய் பயன்படுத்தப்பட்டன.

வகைப்படுத்துதல்

கணிப்பொறி அறிவியலில் பயன்படும் வரிசையாக்கப் படிமுறைகள் பின்வருவனவற்றைப் பொருத்து வகைப்படுத்தப்படுகின்றது:

தனிமங்களின் சிக்கலான (மோசமான, சராசரி மற்றும் சிறந்த நடத்தை) ஒப்பீடுகள் (பட்டியலின் அளவைப் பொருத்தது) $\left(n\right)$ , வரிசையாக்கப் படிமுறைகளின் சிறந்த நடத்தை ${\mathcal {O}}\left(n\log n\right)$ மற்றும் மோசமான நடத்தை ${\mathcal {O}}\left(n^{2}\right)$ (பிக் ஓ குறிமானத்தைப் பார்க்கவும்), வரிசையாக்கத்திற்கான குறைபாடற்ற நடத்தை ${\mathcal {O}}\left(n\right)$ , மற்றும் ஒப்பீட்டு வரிசையாக்கங்கள். மேலும் வரிசையாக்கப் படிமுறை சாவி ஒப்பீட்டு செயல்பாட்டினைச் சுருக்குவதன் மூலம் பட்டியலை அணுகுகிறது என்பதுடன், பெரும்பாலான உள்ளீடுகளுக்கு குறைந்த ${\mathcal {O}}\left(n\log n\right)$ அளவிலான ஒப்பீட்டையே கோருகிறது.
பரிமாற்றத்தின் கணக்கீட்டுச் சிக்கல் (“பொருத்தமான” படிமுறைகளுக்கானது).
நினைவகப் பயன்பாடு (மற்றும் மற்ற கணிப்பொறி மூலாதாரப் பயன்பாடு). சில வரிசையாக்கப் படிமுறைகள் அனைத்தும் “பொருத்தமானதாகும்”. இதன் அர்த்தமானது வரிசையாக்கம் செய்யப்பட்ட உருப்படிகளைக் காட்டிலும் ${\mathcal {O}}(1)$ அல்லது ${\mathcal {O}}(\log n)$ நினைவகத்தையே ஆதரிக்கின்றன என்பதுடன், சில வரிசையாக்கப் படிமுறைகளைப் போல தற்காலிக வரிசையாக்கம் செய்யப்பட்ட தரவுக்காக துணை இடங்களை உருவாக்க அவைகள் விரும்புவதில்லை.
மறுசுழற்சி: வரிசையாக்கப் படிமுறைகளை மறுசுழற்சி அல்லது மறுசுழற்சி அற்றவை என இரண்டு வகைகளாகப் பிரிக்கலாம் (உதாரணமாக சேர்ப்பு வகை), எனினும் சில படிமுறைகள் இந்த வகைகளிலிருந்து மாறுபட்டுக் காணப்படுகின்றன.
நிலைப்புத்தன்மை: நிலையான வரிசையாக்கப் படிமுறைகள் சமமான சாவிகளுடன் கூடிய ஏடுகளின் வரிசையைப் பராமரிக்கிறன (இங்கு மதிப்புகள்). கூடுதல் தகவலுக்காக கீழே பார்க்கவும்.
வரிசையாக்கப் படிமுறைகள் ஒரு ஒப்பீட்டு வகையாக இருக்கலாம் அல்லது இல்லாமலும் இருக்கலாம். ஒரு ஒப்பீட்டு வகை இரண்டு தனிமங்களை ஒப்பீட்டு வினைக்குறியுடன் ஒப்பிடுவதன் மூலம் தரவைப் பரிசோதிக்கிறது.
பொதுவான வழிமுறைகள்: செருகுதல், பரிமாறுதல், தேர்ந்தெடுத்தல், சேர்த்தல், மற்றும் பல. பரிமாற்று வகைகள் குமிழி வகை மற்றும் விரைவு வகை ஆகியவற்றை உள்ளடக்கியது. தேர்ந்தெடுக்கும் வகைகள் குலுக்கி வகை மற்றும் குவியல் வகை ஆகியவற்றை உள்ளடக்கியது.
ஒத்துப்போகும் தன்மை: முன்பே வகைப்படுத்தப்படாத உள்ளீடு ஒருவேளை சென்றுகொண்டிருக்கும் நேரத்தை பாதிக்கலாம் அல்லது பாதிக்காமலும் இருக்கலாம். படிமுறைகள் இதைக் கணக்கில் எடுத்துக்கொள்வது ஒத்துப்போதல் எனப்படும்.

நிலைப்புத்தன்மை

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

(4, 2) (3, 7) (3, 1) (5, 6)

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

(3, 7) (3, 1) (4, 2) (5, 6) (பராமரிக்கப்பட்ட வரிசை) (3, 1) (3, 7) (4, 2) (5, 6) (மாற்றப்பட்ட வரிசை)

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

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

உதாரணம்: மேலே குறிப்பிட்டதைப் போன்று, முழுஎண்ணிலான ஜோடிகளை முதல் தனிமத்தாலும், பின்னர் இரண்டாம் தனிமத்தாலும் வகைப்படுத்தவும்:

(4, 2) (3, 7) (3, 1) (4, 6) (உண்மையில்)

(3, 1) (4, 2) (4, 6) (3, 7) (இரண்டாம் தனிமத்தால் வரிசையாக்கம் செய்யப்பட்ட பின்னர்) (3, 1) (3, 7) (4, 2) (4, 6) (முதல் தனிமத்தால் வரிசையாக்கம் செய்யப்பட்ட பின்னர்)

அதே சமயம்:

(3, 7) (3, 1) (4, 2) (4, 6) (முதல் தனிமத்தால் வரிசையாக்கம் செய்யப்பட்ட பின்னர்) (3, 1) (4, 2) (4, 6) (3, 7) (இரண்டாம் தனிமத்தால் வரிசையாக்கம் செய்யப்பட்ட பின்னர், முதல் தனிமத்தால் வரிசை பிரிக்கப்படுகிறது).

படிமுறைகளின் ஒப்பீடு

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

பெயர்	சராசரி	மோசமானது	நினைவகம்	நிலைப்புத்தன்மை	வழிமுறை	மற்ற குறிப்புகள்
குமிழி வரிசையாக்கம்	02 ! ${\mathcal {}}n^{2}$	03 ! ${\mathcal {}}n^{2}$	01 ! ${\mathcal {}}{1}$	ஆம்		பரிமாற்றம்	நுணுக்கமான குறியீடு
கலப்பு வரிசையாக்கம்		03 !—	03 ! ${\mathcal {}}n^{2}$	01 ! ${\mathcal {}}{1}$	ஆம்		பரிமாற்றம்
வாரி வரிசையாக்கம்		03 !—		04 !—	01 ! ${\mathcal {}}{1}$	இல்லை		பரிமாற்றம்	சிறிய அளவிலான குறியீடு
ஜீனோம் வரிசையாக்கம்		03 !—	03 ! ${\mathcal {}}n^{2}$	01 ! ${\mathcal {}}{1}$	ஆம்		பரிமாற்றம்	நுண்ணிய அளவிலான குறியீடு
தேர்ந்தெடுக்கும் வரிசையாக்கம்	02 ! ${\mathcal {}}n^{2}$	03 ! ${\mathcal {}}n^{2}$	01 ! ${\mathcal {}}{1}$	சார்ந்தது		தேர்ந்தெடுத்தல்	அதன் நிலைப்புத்தன்மை வரையைறைச் சார்ந்ததாகும்.
செருகும் வரிசையாக்கம்	02 ! ${\mathcal {}}n^{2}$	03 ! ${\mathcal {}}n^{2}$	01 ! ${\mathcal {}}{1}$	ஆம்		செருகுதல்	மேலும் சராசரியான நிலையும் கூட ${\mathcal {O}}\left({n+d}\right)$ , d என்பது தலைகீழியின் எண்ணிக்கையாகும்
மறைமுக வரிசையாக்கம்		03 !—	02 ! ${\mathcal {}}{n\log ^{2}n}$	01 ! ${\mathcal {}}{1}$	இல்லை		செருகுதல்	வரிசைப்படுத்துதல்=இடதுபுறமாக
ரும மர வரிசையாக்கம்	01 ! ${\mathcal {}}{n\log n}$	01 ! ${\mathcal {}}{n\log n}$	03 ! ${\mathcal {}}n$	ஆம்		செருகுதல்	தானே சமநிலை செய்துகொள்ளும் தேடும் ரும மரத்தைப் பயன்படுத்தும்போது
நூலக வரிசையாக்கம்	01 ! ${\mathcal {}}{n\log n}$	03 ! ${\mathcal {}}n^{2}$	03 ! ${\mathcal {}}n$	ஆம்		செருகுதல்
சேர்ப்பு வரிசையாக்கம்	01 ! ${\mathcal {}}{n\log n}$	01 ! ${\mathcal {}}{n\log n}$	03 ! ${\mathcal {}}n$	ஆம்		சேர்ப்பு	வரிசைப்படுத்துதல்=இடதுபுறமாக
சரியான சேர்ப்பு வரிசையாக்கம்	01 ! ${\mathcal {}}{n\log n}$	01 ! ${\mathcal {}}{n\log n}$	01 ! ${\mathcal {}}{1}$	சார்ந்தது		சேர்ப்பு	எடுத்துக்காட்டான விளக்கப்படம் இங்கே: [1]; நிலையான பொருத்தமான சேர்ப்பின் அடிப்படையில் நிலையான வரிசையாக்கத்தைப் போல செய்து முடிக்க இயலும்: [2]
குவியல் வரிசையாக்கம்	01 ! ${\mathcal {}}{n\log n}$	01 ! ${\mathcal {}}{n\log n}$	01 ! ${\mathcal {}}{1}$	இல்லை		தேர்ந்தெடுத்தல்
மென்மையான வரிசையாக்கம்		03 !—	01 ! ${\mathcal {}}{n\log n}$	01 ! ${\mathcal {}}{1}$	இல்லை		தேர்ந்தெடுத்தல்	மாற்றியமைக்கும் வரிசைப்படுத்துதல் - ${\mathcal {}}{n}$ ஏற்கனவே தரவு வரிசையாக்கம் செய்யப்பெற்று, ${\mathcal {O}}\left({0}\right)$ பரிமாற்றம் செய்யப்பட்டிருந்தால் ஒப்பீடு பயன்படுத்தப்படுகிறது.
விரைவு வரிசையாக்கம்	01 ! ${\mathcal {O}}\left({n\log n}\right)$	03 ! ${\mathcal {O}}\left(n^{2}\right)$	02 ! ${\mathcal {O}}\left({\log n}\right)$	சார்ந்தது		பிரித்தல்	மையமானது எப்படிக் கையாளப்படுகிறது என்பதன் அடிப்படையில் நிலையான வரிசையாக்கத்தைப் போல செய்து முடிக்க இயலும். எளிமையான ${\mathcal {O}}\left(n\right)$ வேறுபட்ட பயன்பாட்டினாலான இடைவெளி
உள்ளாய்வு வரிசையாக்கம்	01 ! ${\mathcal {O}}\left({n\log n}\right)$	01 ! ${\mathcal {O}}\left({n\log n}\right)$	02 ! ${\mathcal {O}}\left({\log n}\right)$	இல்லை		கலப்பினம்	எஸ்ஜிஐ எஸ்டிஎல் திட்டங்களில் பயன்படுகிறது
நீண்ட வரிசையாக்கம்		03 !—	01 ! ${\mathcal {O}}\left({n\log n}\right)$	03 ! ${\mathcal {O}}\left(n\right)$	இல்லை		செருகுதல் & தேர்ந்தெடுத்தல்	ஓ(n log n ) இற்குள் உள்ள அனைத்து நீண்ட அதிகரிக்கும் துணை வரிசைமுறைகளைக் கண்டறிதல்
திரிக்கும் வரிசையாக்கம்	01 ! ${\mathcal {O}}\left({n\log n}\right)$	03 ! ${\mathcal {O}}\left({n^{2}}\right)$	03 ! ${\mathcal {O}}\left(n\right)$	ஆம்		தேர்ந்தெடுத்தல்
போட்டியிலான வரிசையாக்கம்	01 ! ${\mathcal {O}}\left({n\log n}\right)$	01 ! ${\mathcal {O}}\left({n\log n}\right)$				தேர்ந்தெடுத்தல்

பின்வரும் அட்டவணை ஒப்பீட்டு வரிசையாக்கம் அல்லாத வரிசையாக்கப் படிமுறையை வரையறுக்கிறது. அதே போல, அவைகள் ஒரு குறைந்த பிணைப்பினால் $\Omega \left({n\log n}\right)$ கட்டுப்படுத்தப்படுவது இல்லை. பின்வருவனவற்றுள் n , என்பது வரிசையாக்கம் செய்யப்பட்ட உருப்படிகளின் எண்ணிக்கையைக் குறிக்கிறது, k , என்பது ஒவ்வொரு சாவியின் அளவைக் குறிக்கிறது, மேலும் s , என்பது பயன்படுத்தப்படும் துண்டின் அளவைக் குறிக்கிறது. இவைகளில் பெரும்பாலானவை ஊகத்தின் அடிப்படையிலானவை என்பதுடன், சாவியின் அளவு போதுமான அளவைக் காட்டிலும் பெரியதாக இருந்தால் அனைத்துப் பதிவுகளும் ஒரே அளவிலான சாவியின் மதிப்புகளைக் கொண்டிருக்கும், இதிலிருந்து n << 2^k என்றறியப்படுகிறது, மேலும் << என்பது “மிகவும் சிறியது” என்று பொருள்படும்.

பெயர்	சராசரி	மோசமானது	நிலைப்புத்தன்மை	n << 2^k
தாமதமான வரிசையாக்கம்	${\mathcal {O}}\left({n+2^{k}}\right)$	${\mathcal {O}}\left({n+2^{k}}\right)$	${\mathcal {O}}\left({2^{k}}\right)$	ஆம்	ஆம்
கலன் வரிசையாக்கம்	${\mathcal {O}}\left({n\cdot k}\right)$	${\mathcal {O}}\left({n^{2}\cdot k}\right)$	${\mathcal {O}}\left({n\cdot k}\right)$	ஆம்	இல்லை	அணியின் களத்திலிருந்து பெறப்படும் தனிமங்களைச் சீரான முறையில் வழங்குதல்.
எண்ணும் வரிசையாக்கம்	${\mathcal {O}}\left({n+2^{k}}\right)$	${\mathcal {O}}\left({n+2^{k}}\right)$	${\mathcal {O}}\left({n+2^{k}}\right)$	ஆம்	ஆம்
எல்எஸ்டி தோற்றுவாய் வரிசையாக்கம்	${\mathcal {O}}\left({n\cdot {\frac {k}{s}}}\right)$	${\mathcal {O}}\left({n\cdot {\frac {k}{s}}}\right)$	${\mathcal {O}}\left(n\right)$	ஆம்	இல்லை
எம்எஸ்டி தோற்றுவாய் வரிசையாக்கம்	${\mathcal {O}}\left({n\cdot {\frac {k}{s}}}\right)$	${\mathcal {O}}\left({n\cdot {\frac {k}{s}}\cdot 2^{s}}\right)$	${\mathcal {O}}\left({{\frac {k}{s}}\cdot 2^{s}}\right)$	இல்லை	இல்லை
விரவிய வரிசையாக்கம்	${\mathcal {O}}\left({n\cdot {\frac {k}{s}}}\right)$	${\mathcal {O}}\left({n\cdot \left({{\frac {k}{s}}+s}\right)}\right)$	${\mathcal {O}}\left({{\frac {k}{s}}\cdot 2^{s}}\right)$	இல்லை	இல்லை	கணிதரீதியான வழிமுறையனது n << 2^k இன் ஊகத்தினாலாது, ஆனால் படிமுறைக்கு இது தேவைப்படுவதில்லை.

மிகவும் மோசமான செயல்பாடுகள் அல்லது தனித்தன்மை வாய்ந்த வன்பொருளுக்கான தேவையின் காரணமாக, பின்வரும் அட்டவணை உண்மையான வாழ்க்கைக்குப் பயன்படாத அனுபவமற்ற சில வரிசையாக்கப் படிமுறைகளை வரையறுக்கிறது.

பெயர்	சராசரி	மோசமானது	நிலைப்புத்தன்மை	ஒப்பீடு	மற்ற குறிப்புகள்
அணியிலான வரிசையாக்கம்		குறிப்பு இல்லை	குறிப்பு இல்லை		—		குறிப்பு இல்லை		இல்லை	சிறப்பு வாய்ந்த வன்பொருள் தேவைப்படுகிறது
எளிய அகழிலான வரிசையாக்கம்		${\mathcal {}}n$	${\mathcal {}}n$		${\mathcal {}}{\log n}$	இல்லை		ஆம்	எண்ணிக்கையிலான திருப்பங்களக் கணக்கிடுதல்.
வரிசையாக்க வலைப்பின்னல்கள்	${\mathcal {}}{\log n}$	${\mathcal {}}{\log n}$	${\mathcal {}}{n\cdot \log(n)}$	ஆம்		இல்லை	சுருள்களின் அளவிலான விதி தேவைப்படுகிது ${\mathcal {O}}\left(n\cdot \log(n)\right)$

கணிப்பொறி விஞ்ஞானிகள் காலச் சிக்கலுக்கு ஏற்றார் போல ${\mathcal {O}}\left({n\log n}\right)$ மற்ற சிறந்த வரிசையாக்கப் படிமுறைகளை அளித்தனர்:

ஹேனின் படிமுறை, சாவிகளை வரிசையாக்கம் செய்வதற்காக எல்லைக்குட்பட்டு செயல்படும் ஒரு வரையறுக்கப்பட்ட படிமுறை என்பதுடன், ${\mathcal {O}}\left({n\log \log n}\right)$ காலம் மற்றும் ${\mathcal {O}}\left({n}\right)$ இடைவெளியைப் பயன்படுத்திக்கொள்கிறது.^[2]
தோர்ப்பின் படிமுறை, சாவிகளை வரிசையாக்கம் செய்வதற்காக எல்லைக்குட்படாமல் செயல்படும் ஒரு தொடர்பற்ற படிமுறை என்பதுடன், ${\mathcal {O}}\left({n\log \log n}\right)$ காலம் மற்றும் ${\mathcal {O}}\left({n}\right)$ இடைவெளியைப் பயன்படுத்திக்கொள்கிறது.^[3]
முழு எண்ணிலான வரிசையாக்கப் படிமுறை காலம் மற்றும் ${\mathcal {O}}\left({n}\right)$ இடைவெளியைத் ${\mathcal {O}}\left({n{\sqrt {\log \log n}}}\right)$ தவிர்த்து மற்றதைப் பயன்படுத்திக்கொள்கிறது.^[4]

திறனற்ற/வேடிக்கையான வரிசையாக்கம்

இந்தப் படிமுறைகள் மேலே விவரிக்கப்பட்ட போகோ வரிசையாக்கம் $O(n\cdot n!)$ , உடந்தை வரிசையாக்கம் $O(n^{2.7})$ ஆகியவற்றுடன் ஒப்பிடும்போது மிகவும் மந்தமானதாகும்.

சிறப்பு வாய்ந்த வரிசையாக்கப் படிமுறைகளின் சுருக்கம்

குமிழி வரிசையாக்கம்

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

குமிழி வரிசையாக்கம் என்பது தரவை வரிசையாக்கம் செய்யும் நேரடியான மற்றும் சுலபமான வழிமுறை என்பதுடன், கணிப்பொறி அறிவியலில் பயன்படும் முறையாகும். படிமுறையானது தரவு அமைப்பின் தொடக்கத்தில் ஆரம்பிக்கப்படுகிறது. மேலும் படிமுறை முதல் இரண்டு தனிமங்களை ஒப்பிடுகிறது என்பதுடன், முதல் தனிமம் இரண்டாவது தனிமத்தை விட பெரியதாக இருந்தால், அவைகளை இடமாற்றம் மாற்றுகிறது. அது தரவு அமைப்பின் எல்லை முடியும் வரை ஒவ்வொரு அண்டைத் தனிமங்களின் ஜோடிகளுக்கும் இதைத் தொடர்ந்து செய்கிறது. இந்த நடவடிக்கையானது மீண்டும் முதல் இரண்டு தனிமங்களுடன் தொடங்கி, கடைசிக் கடவில் மாற்றங்கள் ஏற்படாத வரை தொடர்ந்து நடைபெறுகிறது. இந்தப் படிமுறை மிகப்பெரிய அளவில் பயனற்றதாகிறது என்பதுடன்^{[சான்று தேவை]}, சாதாரண உதாரணத்தைத் தவிர, மற்றபடி அரிதாகப் பயன்படுத்தப்படுகிறது. உதாரணமாக, நாம் 100 தனிமங்களைக் கொண்டுள்ளோம் பின்னர் மொத்த எண்ணிக்கையிலான ஒப்பீடானது 10000 ஆகும். வரிசையாக்க நெறிமுறை மற்றும் மாற்றுக் கடவுகளில் திசையை மாற்றுவதன் மூலம் கலவை வரிசையாக்கம் வேலை செய்கிறது. திருத்தப்பட்ட குமிழி வகை வளையத்தின் வழியாக ஒவ்வொரு முறையும் 1 சுருக்கியை நிறுத்துகிறது, ஆகவே 100 தனிமங்களுக்கான ஒப்பீடுகளின் மொத்த எண்ணிக்கை 4950 ஆக இருக்கும்.

குமிழி வரிசையாக்கத்தின் சராசரி மற்றும் மோசமான நிலை இரண்டுமே ஓ(n ²) ஆகும்.

செருகும் வரிசையாக்கம்

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

மறைமுக வரிசையாக்கம்

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

சேர்ப்பு வரிசையாக்கம்

சேர்ப்பு வரிசையாக்கம் ஏற்கனவே வரிசையாக்கம் செய்யப்பட்ட பட்டியல்களைப் புதிய வரிசையாக்கம் செய்யப்பட்ட பட்டியல்களுடன் சேர்க்கும் நடவடிக்கையை மேற்கொள்கிறது. ஒவ்வொரு இரண்டு தனிமங்களை (இங்கு, 1 உடன் 2, பின்னர் 3 உடன் 4...) ஒப்பிடுவது மற்றும் முதல் தனிமம் இரண்டாம் தனிமத்திற்குப் பிறகு வரும்படியாக மாற்றுவது ஆகியவற்றின் மூலம் சேர்ப்பு வரிசையாக்கம் செயல்படுத்தப்படுகிறது. அது பின்னர் ஒவ்வொரு இரண்டு பட்டியல்களின் முடிவை நான்கு பட்டியல்களுடன் சேர்ப்பது, பின்னர் அந்த நான்கு பட்டியல்களின் முடிவுகளை எட்டு பட்டியல்களுடன் சேர்ப்பது போன்ற தொடர்ச்சியான நடவடிக்கைய மேற்கொள்கிறது; கடைசி இரண்டு பட்டியல்கள் இறுதியாக வரிசையாக்கம் செய்யப்பட்ட பட்டியலுடன் சேர்க்கப்படும் வரை இந்த நடவடிக்கைத் தொடர்கிறது. அது படிமுறையின் வரையறையில் இருந்து, மிகப்பெரிய பட்டியல்களை சிறந்த முறையில் அளவீடு செய்கிறது, ஏனெனில் அதன் மிக மோசமான நேர ஓட்டம் ஓ (n log n ) என்று வரையறை செய்யப்படுகிறது. சேர்ப்பு வரிசையாக்கம் சமீபத்தில் அதிக அளவிலான புகழைப்பெற்று காணப்படுகிறது என்பதுடன், பெர்ல்^[5], பைத்தான் (கால வரிசையாக்கத்தைப்^[6] போல), மற்றும் ஜாவா (மேலும் ஜெடிகே7^[7] இன் கால வரிசையாக்கத்தைப் போல பயன்படுகிறது) போன்ற நிரலாக்க மொழிகளில் தரமான வரிசையாக்க நிரலாகப் பயன்படுகிறது.

குவியல் வரிசையாக்கம்

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

விரைவு வரிசையாக்கம்

விரைவு வரிசையாக்கம் பிரிவினைச் செயல்பாட்டில் காணப்படும் பிரிப்பு மற்றும் கட்டுப்பாடான படிமுறையாகும்: அணியைப் பிரிப்பதற்கு, நாம் தேர்ந்தெடுக்கும் தனிமம், மையம் என்றழைக்கப்படுவதுடன், மையத்திற்கு முன்பான அனைத்துச் சிறிய தனிமங்களும் நகர்த்தப்படுகின்றன, மேலும் அதற்குப் பிறகு அனைத்து பெரிய தனிமங்களும் நகர்த்தப்படுகின்றன. நேரியல் நேரம் மற்றும் பொருத்தமான இடத்தில் இது செய்துமுடிக்கப்படுகின்றது. பின்னர் நாம் சிறிய மற்றும் பெரிய இணைப் பட்டியல்களை மறுசுழற்சி முறையில் வரிசையாக்கம் செய்ய வேண்டும். விரைவு வரிசையாக்கத்தின் பயனுள்ள திட்டங்கள் (பொருத்தமான இடத்தில் பிரிப்பது) அனைத்தும் சிக்கலானவை. அது நவீன O(log n ) இடைவெளிப் பயன்பாட்டுடன் இணைந்து மிகவும் புகழ்பெற்ற வரிசையாக்கப் படிமுறைகளில் ஒன்றான விரைவு வரிசையாக்கத்தை உருவாக்குகிறது. விரைவு வரிசையாக்கத்தின் மிகவும் சிக்கலானப் பிரச்சினையானது ஒரு சிறந்த மையத் தனிமத்தைத் தேர்ந்தெடுப்பதாகும்; மையங்களின் தொடர்ந்த மோசமானத் தேர்ந்தெடுப்பு முடிவில் செயல்பாட்டை மிகச்சிறிய O(n ²) அளவில் குறைத்துவிடுகிறது, ஆனால் ஒவ்வொரு நிலையிலும் நாம் சராசரியை மையத்தைப் போலத் தேர்ந்தெடுக்கலாம், பின்னர் அது O(n log n ) இல் செயல்படும். இருந்தபோதும், சராசரியைக் கண்டறிவது வரிசையாக்கம் செய்யப்படாத பட்டியல்களில் நடைபெறும் O(n) நிகழ்வு என்பதுடன், அதன் சொந்த இழப்பீடு சரியான முறையில் கணிக்கப்படுகிறது.

எண்ணும் வரிசையாக்கம்

ஒவ்வொரு உள்ளீடும் நிகழ்தகவுகளின் ஒரு குறிப்பிட்ட அமைப்பைச், S , சார்ந்திருக்கும் போது எண்ணும் வரிசையாக்கம் பயன்படுத்தப்படுகிறது. படிமுறை O(|S | + n ) நேரம் மற்றும் O(|S |) நினைவகத்தில் செயல்படுகிறது என்பதுடன், n என்பது உள்ளீட்டின் நீளம் ஆகும். |S | அளவிலான முழுஎண் அணியை உருவாக்குவது மற்றும் உள்ளீட்டில் S இன் i உறுப்பினைப் கணக்கிடுவதற்கு i சேமிப்பிடத்தைப் பயன்படுத்துவது ஆகிய பணிகளை எண்ணும் வரிசையாக்கம் மேற்கொள்கிறது. ஒவ்வொரு உள்ளீடும் அதற்கான சேமிப்பிட மதிப்பீட்டை உயர்த்துவதன் மூலம் கணக்கிடப்படுகிறது. கணக்கிடும் அணி அனைத்து உள்ளீடுகளை வரிசையாக ஒழுங்குபடுத்துவதன் மூலம் வரிசையாக்கத்தைச் சுருக்குகிறது. இந்த வரிசையாக்கப் படிமுறை அடிக்கடிப் பயன்படுத்தப்படுவதில்லை, ஏனெனில் S அதன் தகுதிக்கேற்ப சிறிய அளவில் இருக்கிறது, ஆனால் அந்தப் படிமுறை மிகவும் வேகமாக இருக்கிறது. நிலையான செயல்பாட்டை அளிப்பதற்கு இதைத் திருத்தம் செய்ய வேண்டியுள்ளது.

கலன் வரிசையாக்கம்

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

தோற்றுவாய் வரிசையாக்கம்

தோற்றுவாய் வரிசையாக்கம் ஒரு படிமுறை என்பதுடன், O(n . k ) இல் k நீளத்திலான மாறா அளவிலான எண்களைப் பிட்டு சரங்களைப் போல வைத்திருப்பதன் மூலம் பட்டியலை வரிசையாக்கம் செய்கிறது. பட்டியலின் வரிசையை ஒரு நிலையான வரிசையாக்கமாகப் பயன்படுத்தும்போது, நாம் முதலில் பட்டியலை மிகச்சிறிய பிட்டினால் வரிசையாக்கம் செய்ய வேண்டும். பின்னர் நாம் அவற்றை வலதுபுறத்தில் இருந்து இடதுபுறமாக அடுத்த பிட்டினால் வரிசையாக்குதல் வேண்டும், மேலும் வரிசையாக்கம் செய்யப்பட்ட பிறகு பட்டியல் நிறைவடையும். பெரும்பாலும், ஒரு பிட்டானது மிகச்சிறிய அளவான '1' அல்லது '0' மதிப்புகளைக் கொண்டிருப்பதிலிருந்து, எண்ணும் வரிசையாக்கப் படிமுறை பிட்டு ரீதியான வரிசையாக்கத்தைச் செய்துமுடிக்கப் பயன்படுகிறது.

பங்கீட்டு வரிசையாக்கம்

பங்கீட்டு வரிசையாக்கம் எந்த ஒரு வரிசையாக்கப் படிமுறையையும் குறிப்பிடுகிறது என்பதுடன், தரவானது அதன் உள்ளீட்டிலிருந்து இடையிலுள்ள பல கட்டமைப்புகளுக்குப் பங்கிடப்பட்டு பின்னர் வெளியீட்டில் திரட்டி வைக்கப்படுகிறது. கலன் வரிசையாக்கத்தைப் பார்க்கவும்.

நினைவகப் பயன்பாட்டின் உருமாதிரிகளும் சுட்டு வரிசையாக்கமும்

வரிசையாக்கம் செய்யும்போது அணியின் அளவானது அதன் முதன்மை நினைவகத்தை நெருங்குகிறது அல்லது விஞ்சுகிறது, ஆகவே (மிகவும் மெதுவாக) வட்டு அல்லது மாற்று இடைவெளி நிச்சயம் பயன்படுத்திக் கொள்ளப்படுகிறது. வரிசையாக்கப் படிமுறையின் நினைவகப் பயன்பாட்டு உருவகம் முக்கியமானதாகிறது, மேலும் ஒரு அணி சுலபமாக ரேமில் சாத்தியமல்லாத வகையில் பொருந்தும் போது, ஒரு படிமுறை முற்றிலும் திறம்பெற்றதாக இருக்க வாய்ப்புள்ளது. இந்தக் குறிப்பில் மொத்த எண்ணிக்கையிலான ஒப்பீடுகள் (கிட்டத்தட்ட) குறைந்த அளவே முக்கியத்துவம் பெறுகிறது, மேலும் வட்டினுள்ளும் மற்றும் வட்டிலிருந்தும் நகலாக்கம் அல்லது மாற்றப்பட்ட நினைவகப் பகுதிகளின் கால எண்ணிக்கை படிமுறையின் தனிச்சிறப்பிலான செயல்பாடுகளை ஆதிக்கம் செய்வதாக உள்ளது. ஆகவே பக்குவமற்ற எண்ணிக்கையிலான ஒப்பீடுகளைக் காட்டிலும் கடவுகளின் எண்ணிக்கை மற்றும் ஓரிடத்திற்குட்பட்ட ஒப்பீடுகள் மிகவும் முக்கியமானதாகிறது. அமைப்புப் பாட்டை வேகத்தில் (அல்லது, மையச் செயலக வேகத்தைப் பற்றுவதற்கு) அருகாமையிலுள்ள தனிமங்களில் ஒன்று மற்றொன்று உடனான ஒப்பீடை மேற்கொள்வதிலிருந்து, வட்டு வேகத்துடன் அமைப்புப் பாட்டை வேகத்தின் ஒப்பீடானது ஏறத்தாழ உடனடியாக மேற்கொள்ளப்படுகிறது.

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

சிக்கலான பதிவுகள் (உறவுநிலைத் தரவுத்தளத்தைப் போல) அனைத்தையும் சிறிய சாவிப் புலத்தின் மூலம் வரிசையாக்கம் செய்யும்போது, மொத்த அணியை வரிசையாக்கம் செய்வதற்குப் பதிலாக, ஒரு சுட்டை அணியில் உருவாக்கிப் பின்னர் அந்தச் சுட்டை வரிசையாக்கம் செய்ய வேண்டும். (மொத்த அணியின் வரிசையாக்கம் செய்யப்பட்ட பதிப்பானது ஒரு கடவுடன் வெளியிடப்படுகிறது என்பதுடன், சுட்டிலிருந்து வாசிக்கப்படுகிறது, ஆனால் வரிசையாக்கம் செய்யப்பட்ட சுட்டு போதுமான அளவு இருப்பதால், இம்முறை பயனற்றதாகிறது.) ஏனெனில் மொத்த அணியைக் காட்டிலும் சுட்டு மிகச்சிறிய அளவில் இருப்பதால், மொத்த அணியும் பொருந்தாத நினைவகத்தில் அது சுலபமாகப் பொருந்துகிறது, அதே சமயம் வட்டு-மாற்றப் பிரச்சினையைத் சரிசெய்கிறது. இந்தச் செயல்முறை சில நேரங்களில் “அடையாள ஒட்டு வரிசையாக்கம்” என்றழைக்கப்படுகிறது.^[8]

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

அமைப்பின் நினைவகத்தை பெருமளவு விஞ்சக்கூடிய மிகப்பெரிய தரவுத் தொகுதிகளை வரிசையாக்கம் செய்வதற்காக, வடிவமைக்கப்பட்ட படிமுறைகளை ஒருங்கிணைத்து முதலில் சுட்டை வரிசையாக்கம் செய்ய வேண்டியிருக்கிறது, அதே சமயம் மாய நினைவகம் தேவைப்படும் மாற்றத்தின் அளவைக் குறைப்பதற்குப் பயன்படுகிறது.

மேலும் காண்க

வெளிப்புற வரிசையாக்கம்
வரிசையாக்க வலையமைப்புகள் (ஒப்பீடு)
அடுக்கு
ஸ்க்வார்ட்சியன் உருமாற்று
கலக்கும் படிமுறைகள்
தேடும் படிமுறைகள்
விக்கிபுத்தகங்கள்: படிமுறைகள்: பல வரிசையாக்கப் படிமுறைகளுடன் அட்டைக் கட்டுகளின் வரிசையாக்கத்தைப் பயன்படுத்துவதை உதாரணமாகச் சொல்லலாம்

பார்வைக் குறிப்புகள்

↑ டீமத்.எச். எலெக்ட்ரானிக் டேட்டா சார்டிங். பிஎச்டி தீசிஸ், ஸ்டான்ஸ்ஃபோர்ட் யுனிவரிசிட்டி, 1956.
↑ ஒய்.ஹான். டிடர்மினிஸ்டிக் சார்டிங் இன் ${\mathcal {O}}\left({n\log \log n}\right)$ டைம் அன்ட் லீனியர் ஸ்பேஸ் . தியரி ஆப் கம்ப்யூடிங்கின் முப்பத்து நான்காவது ஆண்டு ஏசிஎம் கருத்தரங்கின் செயல்பாடுகள், மோன்ட்ரியல், கியூபெக், கனடா, 2002.பி.602-608.
↑ எம்.தோர்ப். ரேன்டமைஸ்ட் சார்டிங் இன் ${\mathcal {O}}\left({n\log \log n}\right)$ டைம் அன்ட் லீனியர் ஸ்பேஸ் யூசிங் அடிஷன், ஷிப்ட், அன்ட் பிட்-வைஸ் பூலியன் ஆப்பரேஷன்ஸ் . படிமுறைகளின் பத்திரிகை, புத்தகம் 42, பிப்ரவரி 2002, பிபி. 205-230(26)
↑ ஹான், ஒய். அன்ட் தோர்ப், எம்.2002. இனிடீஜர் சார்டிங் இன் ${\mathcal {O}}\left({n{\sqrt {\log \log n}}}\right)$ எக்ஸ்பெக்டட் டைம் அன்ட் லீனியர் ஸ்பேஸ். இன் புரசீடிங்ஸ் ஆப் தி 43 சிம்போசியம் ஆன் பவுன்டேஷன்ஸ் ஆப் கம்ப்யூடர் சயின்ஸ் (நவம்பர் 16 - 19, 2002). ஃபோக்கஸ். ஐடிரிபில்இ கம்ப்யூட்டர் சொசைட்டி, வாஷிங்டன், டிசி, 135-144.
↑ பெர்ல் வரிசைப்படுத்தும் ஆவணம்
↑ டிம் பீட்டரின் நேர்த்தியான டிம் வரிசையாக்கத்தின் வரையறை
↑ "காப்பகப்படுத்தப்பட்ட நகல்". Archived from the original on 2012-02-28. பார்க்கப்பட்ட நாள் 2010-04-08.
↑ "பிசி பத்திரிகைக் கூற்றின்படி "அடையாள ஒட்டு வரிசையாக்கத்தின்" வரையறை". Archived from the original on 2012-10-06. பார்க்கப்பட்ட நாள் 2022-01-13.

டி.இ. குனத், தி ஆர்ட் ஆப் கம்ப்யூட்டர் புரோக்ராமிங்]], வால்யூம் 3: சார்டிங் அன்ட் சர்ச்சிங் .

வெளிப்புற இணைப்புகள்

வரிசை மற்றும் இணை வரிசையாக்கப் படிமுறைகள் பரணிடப்பட்டது 2012-12-13 at the வந்தவழி இயந்திரம் – இதைப் போன்ற பல படிமுறைகளின் விளக்கங்கள் மற்றும் ஆய்வுகளைக் கொண்டுள்ளது.
வலைதளத்தில் ரிக்கார்டோ பாயேஸ்-யாடெஸின் வழியாக்கப் படிமுறைகள்
'படிமுறைகளின் நூலகம், தரவுக் கட்டமைப்புகள், மற்றும் பிரச்சினைகள்’
வரிசையாக்கப் படிமுறைகளின் மிகச்சிறிய நம்பிக்கையற்ற பார்வை மிருதுவான பரந்த காட்சிப் பக்கம் பல்வேறு உயர்வான படிமுறைகளை விவாதிக்கிறது என்பதுடன் வேக வரிசையாக்கத்திற்கான மாற்றுக்களை ஊக்குவிக்கிறது.
வரிசையாக்கப் படிமுறை அசைவூட்டம்

[1] டீமத்.எச். எலெக்ட்ரானிக் டேட்டா சார்டிங். பிஎச்டி தீசிஸ், ஸ்டான்ஸ்ஃபோர்ட் யுனிவரிசிட்டி, 1956.

[2] ஒய்.ஹான். டிடர்மினிஸ்டிக் சார்டிங் இன் ${\mathcal {O}}\left({n\log \log n}\right)$ டைம் அன்ட் லீனியர் ஸ்பேஸ் . தியரி ஆப் கம்ப்யூடிங்கின் முப்பத்து நான்காவது ஆண்டு ஏசிஎம் கருத்தரங்கின் செயல்பாடுகள், மோன்ட்ரியல், கியூபெக், கனடா, 2002.பி.602-608.

[3] எம்.தோர்ப். ரேன்டமைஸ்ட் சார்டிங் இன் ${\mathcal {O}}\left({n\log \log n}\right)$ டைம் அன்ட் லீனியர் ஸ்பேஸ் யூசிங் அடிஷன், ஷிப்ட், அன்ட் பிட்-வைஸ் பூலியன் ஆப்பரேஷன்ஸ் . படிமுறைகளின் பத்திரிகை, புத்தகம் 42, பிப்ரவரி 2002, பிபி. 205-230(26)

[4] ஹான், ஒய். அன்ட் தோர்ப், எம்.2002. இனிடீஜர் சார்டிங் இன் ${\mathcal {O}}\left({n{\sqrt {\log \log n}}}\right)$ எக்ஸ்பெக்டட் டைம் அன்ட் லீனியர் ஸ்பேஸ். இன் புரசீடிங்ஸ் ஆப் தி 43 சிம்போசியம் ஆன் பவுன்டேஷன்ஸ் ஆப் கம்ப்யூடர் சயின்ஸ் (நவம்பர் 16 - 19, 2002). ஃபோக்கஸ். ஐடிரிபில்இ கம்ப்யூட்டர் சொசைட்டி, வாஷிங்டன், டிசி, 135-144.

[5] பெர்ல் வரிசைப்படுத்தும் ஆவணம்

[6] டிம் பீட்டரின் நேர்த்தியான டிம் வரிசையாக்கத்தின் வரையறை

[7] "காப்பகப்படுத்தப்பட்ட நகல்". Archived from the original on 2012-02-28. பார்க்கப்பட்ட நாள் 2010-04-08.

[8] "பிசி பத்திரிகைக் கூற்றின்படி "அடையாள ஒட்டு வரிசையாக்கத்தின்" வரையறை". Archived from the original on 2012-10-06. பார்க்கப்பட்ட நாள் 2022-01-13.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]