பொருளடக்கம்
- அறிமுகம்
- C++ இல் Merge Sort என்றால் என்ன
- பிரித்து வெற்றி அணுகுமுறை
- வரிசைப்படுத்தும் அல்காரிதத்தை ஒன்றிணைக்கவும்
- C++ இல் Merge Sort ஐ செயல்படுத்துதல்
- முடிவுரை
1. அறிமுகம்
கணினி அறிவியலில் வரிசையாக்க வழிமுறைகள் ஏறுவரிசை அல்லது இறங்கு வரிசையில் தரவை ஒழுங்கமைக்கப் பயன்படுகின்றன. தனித்துவமான பண்புகளுடன் பல வரிசையாக்க வழிமுறைகள் உள்ளன. Merge sort என்பது C++ இல் உள்ள முறைகளில் ஒன்றாகும், இது வரிசைகளை வரிசைப்படுத்த முடியும்.
2. C++ இல் Merge Sort என்றால் என்ன
Merge sort ஆனது வரிசையின் கூறுகளை வரிசைப்படுத்தக்கூடிய பிரித்து வெற்றிபெறும் நுட்பத்தைப் பயன்படுத்துகிறது. இது C++ இல் உள்ள உறுப்புகளின் பட்டியலையும் வரிசைப்படுத்தலாம். இது உள்ளீட்டை இரண்டு பகுதிகளாகப் பிரித்து, ஒவ்வொரு பாதியையும் தனித்தனியாக வரிசைப்படுத்தி, பின்னர் அவற்றை சரியான வரிசையில் இணைக்கிறது.
3. பிரித்து வெற்றிகொள்ளும் அணுகுமுறை
வரிசைப்படுத்தும் அல்காரிதம் ஒரு பிரித்து வெற்றிபெறும் உத்தியைப் பயன்படுத்துகிறது, இது உள்ளீட்டு வரிசையை சிறிய துணைக்குழுக்களாகப் பிரித்து, தனித்தனியாகத் தீர்த்து, பின்னர் முடிவுகளை ஒன்றிணைத்து வரிசைப்படுத்தப்பட்ட வெளியீட்டை உருவாக்குகிறது. ஒன்றிணைக்கும் வரிசையின் விஷயத்தில், ஒவ்வொரு பாதியிலும் ஒரு உறுப்பு மட்டுமே எஞ்சியிருக்கும் வரை அணிவரிசை இரண்டு பகுதிகளாகப் பிரிக்கப்படும்.
4. வரிசைப்படுத்தல் அல்காரிதத்தை ஒன்றிணைக்கவும்
ஒன்றிணைக்கும் வரிசை வழிமுறை இரண்டு முக்கிய படிகளைக் கொண்டுள்ளது: பிரித்தல் மற்றும் ஒன்றிணைத்தல். படிகள் பின்வருமாறு:
4.1 பிரிக்கவும்
ஒரு வரிசையில் உள்ள உறுப்புகளை வரிசைப்படுத்துவதற்கான பிரித்து-வெற்றி உத்தியை ஒன்றிணைக்கும் வரிசை வழிமுறை பின்பற்றுகிறது.
- அல்காரிதத்தின் முதல் படி வரிசை கூறுகளை சரிபார்க்கும். அதில் ஒரு உறுப்பு இருந்தால், அது ஏற்கனவே வரிசைப்படுத்தப்பட்டதாகக் கருதப்படுகிறது, மேலும் அல்காரிதம் எந்த மாற்றமும் இல்லாமல் அதே வரிசையை வழங்கும்.
- அணிவரிசையில் ஒன்றுக்கு மேற்பட்ட உறுப்புகள் இருந்தால், அல்காரிதம் அதை இரண்டு பகுதிகளாகப் பிரிக்கிறது: இடது பாதி மற்றும் வலது பாதி.
- ஒன்றிணைக்கும் வரிசை அல்காரிதம் பின்னர் வரிசையின் இடது மற்றும் வலது பகுதிகளுக்கு மீண்டும் மீண்டும் பயன்படுத்தப்படுகிறது, அவற்றை திறம்பட சிறிய துணைக்குழுக்களாகப் பிரித்து தனித்தனியாக வரிசைப்படுத்துகிறது.
- துணைவரிசைகள் ஒவ்வொன்றும் ஒரு தனிமத்தை மட்டுமே கொண்டிருக்கும் வரை (படி 1 இன் படி) இந்த சுழல்நிலை செயல்முறை தொடர்கிறது, அந்த நேரத்தில் அவை இறுதி, வரிசைப்படுத்தப்பட்ட வெளியீட்டு வரிசையை உருவாக்க ஒன்றிணைக்கப்படலாம்.
4.2 ஒன்றிணைத்தல்
இப்போது வரிசைகளை ஒன்றிணைப்பதற்கான படிகளைப் பார்ப்போம்:
- ஒன்றிணைக்கும் வரிசை வழிமுறைக்கான முதல் படி வெற்று வரிசையை உருவாக்குவதை உள்ளடக்கியது.
- அல்காரிதம் பின்னர் உள்ளீட்டு வரிசையின் இடது மற்றும் வலது பகுதிகளின் முதல் கூறுகளை ஒப்பிட்டுப் பார்க்கிறது.
- இரண்டு உறுப்புகளில் சிறியவை புதிய அணிவரிசையில் சேர்க்கப்பட்டு பின்னர் உள்ளீட்டு வரிசையின் அந்தந்த பாதியில் இருந்து அகற்றப்படும்.
- 2-3 படிகள் பின்னர் ஒரு பகுதி காலியாகும் வரை மீண்டும் மீண்டும் செய்யப்படுகிறது.
- காலியாக இல்லாத பாதியில் மீதமுள்ள கூறுகள் புதிய வரிசையில் சேர்க்கப்படும்.
- இதன் விளைவாக வரிசை இப்போது முழுமையாக வரிசைப்படுத்தப்பட்டு, ஒன்றிணைக்கும் வரிசை அல்காரிதத்தின் இறுதி வெளியீட்டைக் குறிக்கிறது.
5. C++ இல் Merge Sort ஐ செயல்படுத்துதல்
C++ இல் ஒன்றிணைக்கும் வரிசையை செயல்படுத்த இரண்டு வெவ்வேறு முறைகள் பின்பற்றப்படுகின்றன. இரண்டு முறைகளின் நேரச் சிக்கலானது சமமானதாகும், ஆனால் அவற்றின் தற்காலிக துணைவரிசைகளின் பயன்பாடு வேறுபட்டது.
C++ இல் ஒன்றிணைக்கும் வரிசைக்கான முதல் முறை இரண்டு தற்காலிக துணைவரிசைகளைப் பயன்படுத்துகிறது, இரண்டாவது முறை ஒன்றை மட்டுமே பயன்படுத்துகிறது. முதல் முறையில் உள்ள இரண்டு தற்காலிக துணைவரிசைகளின் மொத்த அளவு, இரண்டாவது முறையின் அசல் வரிசையின் அளவிற்கு சமமாக உள்ளது என்பது குறிப்பிடத்தக்கது, எனவே விண்வெளி சிக்கலானது மாறாமல் உள்ளது.
முறை 1 - இரண்டு டெம்ப் சுபரேகளைப் பயன்படுத்துதல்
முறை 1 ஐப் பயன்படுத்தி C++ இல் வரிசைப்படுத்துவதற்கான ஒரு எடுத்துக்காட்டு நிரல் இங்கே உள்ளது, இது இரண்டு தற்காலிக துணைவரிசைகளைப் பயன்படுத்துகிறது:
#பெயர்வெளி std ஐப் பயன்படுத்துகிறது ;
வெற்றிடமானது ஒன்றிணைக்க ( முழு எண்ணாக arr [ ] , முழு எண்ணாக எல் , முழு எண்ணாக மீ , முழு எண்ணாக ஆர் )
{
முழு எண்ணாக n1 = மீ - எல் + 1 ;
முழு எண்ணாக n2 = ஆர் - மீ ;
முழு எண்ணாக எல் [ n1 ] , ஆர் [ n2 ] ;
க்கான ( முழு எண்ணாக நான் = 0 ; நான் < n1 ; நான் ++ )
எல் [ நான் ] = arr [ எல் + நான் ] ;
க்கான ( முழு எண்ணாக ஜே = 0 ; ஜே < n2 ; ஜே ++ )
ஆர் [ ஜே ] = arr [ மீ + 1 + ஜே ] ;
முழு எண்ணாக நான் = 0 , ஜே = 0 , கே = எல் ;
போது ( நான் < n1 && ஜே < n2 ) {
என்றால் ( எல் [ நான் ] <= ஆர் [ ஜே ] ) {
arr [ கே ] = எல் [ நான் ] ;
நான் ++;
}
வேறு {
arr [ கே ] = ஆர் [ ஜே ] ;
ஜே ++;
}
கே ++;
}
போது ( நான் < n1 ) {
arr [ கே ] = எல் [ நான் ] ;
நான் ++;
கே ++;
}
போது ( ஜே < n2 ) {
arr [ கே ] = ஆர் [ ஜே ] ;
ஜே ++;
கே ++;
}
}
வெற்றிடமானது ஒன்றிணைத்தல் ( முழு எண்ணாக arr [ ] , முழு எண்ணாக எல் , முழு எண்ணாக ஆர் )
{
என்றால் ( எல் < ஆர் ) {
முழு எண்ணாக மீ = எல் + ( ஆர் - எல் ) / 2 ;
ஒன்றிணைத்தல் ( arr , எல் , மீ ) ;
ஒன்றிணைத்தல் ( arr , மீ + 1 , ஆர் ) ;
ஒன்றிணைக்க ( arr , எல் , மீ , ஆர் ) ;
}
}
முழு எண்ணாக முக்கிய ( )
{
முழு எண்ணாக arr [ ] = { 12 , பதினொரு , 13 , 5 , 6 , 7 } ;
முழு எண்ணாக arr_size = அளவு ( arr ) / அளவு ( arr [ 0 ] ) ;
கூட் << 'கொடுக்கப்பட்ட வரிசை உள்ளது \n ' ;
க்கான ( முழு எண்ணாக நான் = 0 ; நான் < arr_size ; நான் ++ )
கூட் << arr [ நான் ] << '' ;
ஒன்றிணைத்தல் ( arr , 0 , arr_size - 1 ) ;
கூட் << ' \n வரிசைப்படுத்தப்பட்ட வரிசை என்பது \n ' ;
க்கான ( முழு எண்ணாக நான் = 0 ; நான் < arr_size ; நான் ++ )
கூட் << arr [ நான் ] << '' ;
திரும்ப 0 ;
}
இந்த நிரலில், ஒன்றிணைப்பு செயல்பாடு arr, l மற்றும் r ஆகிய மூன்று வாதங்களை எடுக்கும், இது வரிசைப்படுத்தப்பட வேண்டிய வரிசையைக் குறிக்கிறது மற்றும் இணைக்கப்பட வேண்டிய துணைவரிசையின் குறியீடுகளைக் காட்டுகிறது. இந்தச் செயல்பாடு முதலில் இணைக்கப்பட வேண்டிய இரண்டு துணைவரிசைகளின் அளவுகளைக் கண்டறிந்து, இந்த துணைவரிசைகளின் தனிமங்களைச் சேமிப்பதற்காக இரண்டு தற்காலிக துணைவரிசைகளான L மற்றும் R ஐ உருவாக்குகிறது. இது L மற்றும் R இல் உள்ள உறுப்புகளை ஒப்பிட்டு, பெயரிடப்பட்ட அசல் வரிசையில் அவற்றை இணைக்கிறது arr ஏறுவரிசையில்.
சப்அரேயில் ஒரே ஒரு உறுப்பு மட்டுமே இருக்கும் வரை, வரிசையை இரண்டு பகுதிகளாகப் பிரிக்க, mergeSort செயல்பாட்டின் மூலம் பிரித்து வெற்றிபெறும் நுட்பம் பயன்படுத்தப்படுகிறது. பின்னர் அது இரண்டு துணைவரிசைகளையும் ஒரு வரிசைப்படுத்தப்பட்ட துணைக்குழுவாக இணைக்கிறது. முழுமையான வரிசையை வரிசைப்படுத்தாத வரை செயல்பாடு துணைவரிசைகளை ஒன்றிணைப்பதைத் தொடர்கிறது.
முக்கிய செயல்பாட்டில், 6 உறுப்புகள் கொண்ட ஒரு array arr ஐ வரையறுத்து அதை வரிசைப்படுத்த mergeSort செயல்பாட்டை அழைக்கிறோம். குறியீட்டின் முடிவில், வரிசைப்படுத்தப்பட்ட வரிசை அச்சிடப்படுகிறது.
முறை 2 - ஒரு டெம்ப் சுபரேயைப் பயன்படுத்துதல்
முறை 2 ஐப் பயன்படுத்தி C++ இல் வரிசைப்படுத்துவதற்கான ஒரு எடுத்துக்காட்டு நிரல் இங்கே உள்ளது, இது ஒரு தற்காலிக துணைக்குழுவைப் பயன்படுத்துகிறது:
#பெயர்வெளி std ஐப் பயன்படுத்துகிறது ;
வெற்றிடமானது ஒன்றிணைக்க ( முழு எண்ணாக arr [ ] , முழு எண்ணாக எல் , முழு எண்ணாக மீ , முழு எண்ணாக ஆர் )
{
முழு எண்ணாக நான் , ஜே , கே ;
முழு எண்ணாக n1 = மீ - எல் + 1 ;
முழு எண்ணாக n2 = ஆர் - மீ ;
// தற்காலிக துணை அணிகளை உருவாக்கவும்
முழு எண்ணாக எல் [ n1 ] , ஆர் [ n2 ] ;
// தரவை துணைக்குழுக்களுக்கு நகலெடுக்கவும்
க்கான ( நான் = 0 ; நான் < n1 ; நான் ++ )
எல் [ நான் ] = arr [ எல் + நான் ] ;
க்கான ( ஜே = 0 ; ஜே < n2 ; ஜே ++ )
ஆர் [ ஜே ] = arr [ மீ + 1 + ஜே ] ;
// தற்காலிக துணைக்குழுக்களை அசல் வரிசையில் மீண்டும் இணைக்கவும்
நான் = 0 ;
ஜே = 0 ;
கே = எல் ;
போது ( நான் < n1 && ஜே < n2 ) {
என்றால் ( எல் [ நான் ] <= ஆர் [ ஜே ] ) {
arr [ கே ] = எல் [ நான் ] ;
நான் ++;
}
வேறு {
arr [ கே ] = ஆர் [ ஜே ] ;
ஜே ++;
}
கே ++;
}
// L இன் மீதமுள்ள கூறுகளை நகலெடுக்கவும்[]
போது ( நான் < n1 ) {
arr [ கே ] = எல் [ நான் ] ;
நான் ++;
கே ++;
}
// R இன் மீதமுள்ள கூறுகளை நகலெடுக்கவும்[]
போது ( ஜே < n2 ) {
arr [ கே ] = ஆர் [ ஜே ] ;
ஜே ++;
கே ++;
}
}
வெற்றிடமானது ஒன்றிணைத்தல் ( முழு எண்ணாக arr [ ] , முழு எண்ணாக எல் , முழு எண்ணாக ஆர் )
{
என்றால் ( எல் < ஆர் ) {
முழு எண்ணாக மீ = எல் + ( ஆர் - எல் ) / 2 ;
// இடது மற்றும் வலது பாதிகளை சுழல்நிலையாக வரிசைப்படுத்தவும்
ஒன்றிணைத்தல் ( arr , எல் , மீ ) ;
ஒன்றிணைத்தல் ( arr , மீ + 1 , ஆர் ) ;
// இரண்டு வரிசைப்படுத்தப்பட்ட பகுதிகளை ஒன்றிணைக்கவும்
ஒன்றிணைக்க ( arr , எல் , மீ , ஆர் ) ;
}
}
முழு எண்ணாக முக்கிய ( )
{
முழு எண்ணாக arr [ ] = { 12 , பதினொரு , 13 , 5 , 6 , 7 } ;
முழு எண்ணாக arr_size = அளவு ( arr ) / அளவு ( arr [ 0 ] ) ;
கூட் << 'கொடுக்கப்பட்ட வரிசை உள்ளது \n ' ;
க்கான ( முழு எண்ணாக நான் = 0 ; நான் < arr_size ; நான் ++ )
கூட் << arr [ நான் ] << '' ;
ஒன்றிணைத்தல் ( arr , 0 , arr_size - 1 ) ;
கூட் << ' \n வரிசைப்படுத்தப்பட்ட வரிசை என்பது \n ' ;
க்கான ( முழு எண்ணாக நான் = 0 ; நான் < arr_size ; நான் ++ )
கூட் << arr [ நான் ] << '' ;
திரும்ப 0 ;
}
இந்த நிரல் முந்தையதைப் போன்றது, ஆனால் எல் மற்றும் ஆர் என்ற இரண்டு தற்காலிக சப்அரேகளைப் பயன்படுத்துவதற்குப் பதிலாக, இது ஒரு தற்காலிக சப்ரே டெம்ப் பயன்படுத்துகிறது. ஒன்றிணைப்பு செயல்பாடு முன்பு போலவே செயல்படுகிறது, ஆனால் தரவை எல் மற்றும் ஆர்க்கு நகலெடுப்பதற்குப் பதிலாக, அதை டெம்ப்க்கு நகலெடுக்கிறது. இது தற்காலிக வரிசை கூறுகளை மீண்டும் இணைக்கிறது arr இது அசல் வரிசை.
mergeSort செயல்பாடு முன்பு இருந்ததைப் போலவே உள்ளது, இது தற்காலிக சப்ரேயை சேமிக்க L மற்றும் Rக்கு பதிலாக temp ஐப் பயன்படுத்துகிறது.
முக்கிய செயல்பாட்டில், 6 உறுப்புகள் கொண்ட ஒரு array arr ஐ வரையறுத்து அதை வரிசைப்படுத்த mergeSort செயல்பாட்டை அழைக்கிறோம். திரையில் வரிசைப்படுத்தப்பட்ட வரிசையை அச்சிடுவதன் மூலம் குறியீடு செயல்படுத்தல் முடிவடைகிறது.
முடிவுரை
Merge sort என்பது வரிசை உறுப்புகளை வரிசைப்படுத்தும் ஒரு அல்காரிதம் ஆகும், மேலும் இது பிரித்து-வெற்றி நுட்பத்தைப் பயன்படுத்துகிறது மற்றும் உறுப்புகளுக்கு இடையே ஒப்பீடு செய்கிறது. C++ இல் உள்ள Merge sort ஆனது O(n log n) இன் நேர சிக்கலைக் கொண்டுள்ளது மற்றும் பெரிய அணிவரிசைகளை வரிசைப்படுத்துவதற்கு இது மிகவும் பயனுள்ளதாக இருக்கும். இணைக்கப்பட்ட துணைவரிசைகளை சேமிப்பதற்கு கூடுதல் நினைவகம் தேவைப்பட்டாலும், அதன் நிலைத்தன்மை அதை வரிசைப்படுத்துவதற்கான ஒரு பிரபலமான தேர்வாக ஆக்குகிறது.