பொருளடக்கம்[மறை][காட்டு]
கணினி அறிவியல் என்பது அல்காரிதம்கள் மற்றும் தரவு கட்டமைப்புகளின் சிக்கல்களைப் புரிந்துகொள்வதாகும்.
வரிசைப்படுத்த வேண்டிய உருப்படிகளின் பட்டியல் உங்களிடம் உள்ளது, ஆனால் சிக்கலான வரிசையாக்க அல்காரிதத்தைப் பயன்படுத்த உங்களுக்கு நேரமோ ஆதாரமோ இல்லை.
செருகும் வரிசையாக்கம் எளிமையான வரிசையாக்க வழிமுறைகளில் ஒன்றாகும், ஆனால் பெரிய பட்டியல்களுக்கு இது மெதுவாக இருக்கும்.
எளிமையான செயல்படுத்தல் மற்றும் புரிதல் இந்த முறையை புரோகிராமர்கள் மத்தியில் பிடித்ததாக ஆக்கியுள்ளது. சிறிய பட்டியல்களுக்கு அல்லது உங்களுக்கு விரைவான தீர்வு தேவைப்படும்போது இது சரியானது.
இந்த வலைப்பதிவு இடுகையில், செருகும் வரிசையாக்கத்தின் நேர சிக்கலைப் பார்ப்போம். இந்த அல்காரிதம் அணிவரிசைகளை வரிசைப்படுத்தப் பயன்படுகிறது, மேலும் இது O(n) இயக்க நேரத்தைக் கொண்டுள்ளது2) இதன் பொருள் வரிசையின் அளவுடன் நேர சிக்கலானது அதிகரிக்கிறது.
இருப்பினும், இந்த அல்காரிதம் விரைவு வரிசை போன்ற பிற வரிசையாக்க வழிமுறைகளை விட வேகமாக இருக்கும்.
செருகும் வரிசையாக்கம் எவ்வாறு செயல்படுகிறது என்பதை விரிவாகப் பார்ப்போம்!
செருகும் வரிசை அல்காரிதம் என்றால் என்ன?
ஒரு நேரத்தில் ஒரு உறுப்பு, செருகும் வரிசை வரிசைப்படுத்தக்கூடிய வரிசையை உருவாக்குகிறது, இது அடிக்கடி பட்டியல் என்று அழைக்கப்படுகிறது.
எடுத்துக்காட்டாக, கம்பைலர்கள் போன்ற சிக்கலான கணினி நிரல்களில் வரிசையாக்கம் பயன்படுத்தப்படுகிறது, அங்கு நிரலின் விளக்கத்திற்கு டோக்கன்களின் வரிசை முக்கியமானது.
செருகும் வரிசை எப்படி வேலை செய்கிறது?
ஒரு வரிசையை வரிசைப்படுத்த செருகும் வரிசையைப் பயன்படுத்தும்போது, பட்டியலில் உள்ள சிறிய உருப்படியைக் கண்டுபிடித்து அதை சரியான நிலையில் செருகுவதன் மூலம் அல்காரிதம் தொடங்குகிறது.
அது அடுத்த சிறிய பொருளைக் கண்டுபிடித்து அதை சரியான நிலையில் செருகுகிறது, மற்றும் பல.
அல்காரிதம் பட்டியலைச் சுழற்றுவதன் மூலம் செயல்படுகிறது, ஒவ்வொரு உருப்படியையும் அதற்கு முன் வரும் உருப்படியுடன் ஒப்பிடுகிறது.
உருப்படிகள் தவறான வரிசையில் இருந்தால், அல்காரிதம் அவற்றை மாற்றும். பட்டியல் வரிசைப்படுத்தப்பட்டுள்ளதா என்று சரிபார்க்கிறது, அது இருந்தால், அல்காரிதம் முடிவடைகிறது.
நடைமுறையில், செருகும் வரிசைமுறையானது சில வரிகளின் குறியீட்டைப் பயன்படுத்தி செயல்படுத்தப்படுகிறது, இது சிறிய வரிசைகளை வரிசைப்படுத்துவதற்கான பிரபலமான தேர்வாக அமைகிறது. இருப்பினும், இந்த அல்காரிதத்தைப் பயன்படுத்தும் போது நேர சிக்கலைக் கருத்தில் கொள்ள வேண்டும்.
உதாரணமாக:
செருகல் வரிசையாக்கம் எவ்வாறு செயல்படுகிறது என்பதற்கான எடுத்துக்காட்டு இங்கே. பின்வரும் வரிசையைப் பயன்படுத்துவோம்:
1, 2, 3, 4, 5, 6
அல்காரிதம் பட்டியலில் உள்ள மிகச்சிறிய உருப்படியைக் கண்டறிவதன் மூலம் தொடங்குகிறது, அது 1. அது அதை சரியான நிலையில், முதல் நிலையில் செருகும். அது அடுத்த சிறிய உருப்படியைக் கண்டுபிடிக்கும், அதாவது 2. அது சரியான நிலையில் அதைச் செருகுகிறது, இது இரண்டாவது நிலை.
அது அடுத்த சிறிய உருப்படியைக் கண்டுபிடிக்கும், அதாவது 3. அது சரியான நிலையில் அதைச் செருகுகிறது, இது மூன்றாவது நிலை.
இது அடுத்த சிறிய உருப்படியைக் கண்டுபிடிக்கும், அது 4. அது சரியான நிலையில் அதைச் செருகுகிறது, இது நான்காவது நிலை, மற்றும் பல. பட்டியல் இப்போது வரிசைப்படுத்தப்பட்டுள்ளது!
பட்டியலை வரிசைப்படுத்த அல்காரிதம் ஆறு ஒப்பீடுகள் மற்றும் இடமாற்றுகளை எடுக்கும் என்பதை எடுத்துக்காட்டில் இருந்து பார்க்கலாம். ஏனெனில் இது n எடுக்கிறது2 n உருப்படிகளின் பட்டியலை வரிசைப்படுத்த ஒப்பீடுகள் மற்றும் இடமாற்றுகள். இந்த வழக்கில், n=6.
செருகும் வரிசைப்படுத்தும் நேர சிக்கலை எவ்வாறு மேம்படுத்துவது?
செருகும் வரிசையானது O(n) இயக்க நேரத்தைக் கொண்டிருக்கும் போது2), விரைவான வரிசை போன்ற சிறந்த வரிசையாக்க வழிமுறையைப் பயன்படுத்தி மேம்படுத்தலாம்.
Quicksort ஆனது O(n log n) இயக்க நேரத்தைக் கொண்டுள்ளது, இது O(n) ஐ விட மிக வேகமானது2).
இருப்பினும், சில சந்தர்ப்பங்களில், செருகும் வரிசையாக்கம் விரைவான வரிசையை விட வேகமாக இருக்கும்.
எடுத்துக்காட்டாக, பட்டியல் ஏற்கனவே ஒழுங்காக இருந்தால், செருகும் வரிசைப்படுத்தல் விரைவான வரிசையை விட குறைவான நேரத்தை எடுக்கும்.
நடைமுறையில், செருகும் வரிசைமுறையானது சில வரிகளின் குறியீட்டைப் பயன்படுத்தி செயல்படுத்தப்படுகிறது, இது சிறிய வரிசைகளை வரிசைப்படுத்துவதற்கான பிரபலமான தேர்வாக அமைகிறது.
இருப்பினும், இந்த அல்காரிதத்தைப் பயன்படுத்தும் போது நேர சிக்கலைக் கருத்தில் கொள்ள வேண்டும்.
நேர சிக்கல்கள்
மோசமான நிலை சிக்கலான O(n2):
வரிசையின் அளவோடு நேர சிக்கலானது அதிகரிக்கிறது. இது n எடுக்கும்2 n உருப்படிகளின் பட்டியலை வரிசைப்படுத்த ஒப்பீடுகள் மற்றும் இடமாற்றுகள்.
எடுத்துக்காட்டாக, எங்களிடம் 1000 அளவு வரிசை இருந்தால், வரிசையை வரிசைப்படுத்த அல்காரிதம் 1,000,000 ஒப்பீடுகளையும் இடமாற்றங்களையும் எடுக்கும்.
சிறந்த வழக்கு சிக்கலான O(n):
உள்ளீட்டு வரிசையின் அளவைப் போலவே நேர சிக்கலும் இருக்கும். நான்
n உருப்படிகளின் பட்டியலை வரிசைப்படுத்த t n ஒப்பீடுகள் மற்றும் இடமாற்றுகளை எடுக்கும். எடுத்துக்காட்டாக, அளவு 5 வரிசையைக் கவனியுங்கள். வரிசையை வரிசைப்படுத்த அல்காரிதம் ஐந்து ஒப்பீடுகள் மற்றும் இடமாற்றங்களை எடுக்கும்.
சராசரி வழக்கு சிக்கலான O(n2):
நேர சிக்கலானது இந்த வழக்கில் மோசமான மற்றும் சிறந்த வழக்கு சிக்கல்களுக்கு இடையில் உள்ளது.
இது n எடுக்கும்2 n உருப்படிகளின் பட்டியலை வரிசைப்படுத்த ஒப்பீடுகள் மற்றும் இடமாற்றுகள்.
இவ்வாறு, செருகும் வரிசையாக்கம் ஒரு நிலையான வரிசையாக்க வழிமுறையாகும்.
செருகும் வரிசை ஏன் நிலையானது?
உள்ளீட்டு வரிசையில் சம உறுப்புகளின் வரிசையைப் பாதுகாக்கும் என்பதால், செருகும் வரிசை நிலையானது.
தரவு மீட்டெடுப்பு அல்லது நிதி பகுப்பாய்வு போன்ற பல பயன்பாடுகளுக்கு இது முக்கியமானது. உதாரணமாக, எங்களிடம் இரண்டு எண்களின் பட்டியல்கள் இருந்தால், அவற்றை ஒப்பிட விரும்பினால், உறுப்புகளின் வரிசை பாதுகாக்கப்படுவதை உறுதி செய்ய வேண்டும்.
பட்டியல்கள் வரிசைப்படுத்தப்படாவிட்டால், அவற்றை நாம் துல்லியமாக ஒப்பிட மாட்டோம்.
ஒரு பதில் விடவும்