வரிசையாக்கம் என்பது பொருள்களில் நாம் செய்யும் அடிப்படை செயல்பாடுகளில் ஒன்றாகும். குழந்தை பருவத்தில் கூட, குழந்தைகள் தங்கள் சிந்திக்கும் திறனை வளர்த்துக் கொள்ளும்போது வரிசைப்படுத்த கற்றுக்கொடுக்கப்படுகிறார்கள். கணினி மற்றும் மென்பொருள் விதிவிலக்கல்ல. ஜாவாவில் பல்வேறு வகையான வரிசையாக்க அல்காரிதம்கள் உள்ளன . அவை என்ன, அவை எவ்வாறு செயல்படுகின்றன என்பதைப் பார்க்குமாறு நான் பரிந்துரைக்கிறேன். ஒரு நாள் நேர்காணலில் அவர்களில் ஒருவரைப் பற்றி உங்களிடம் கேட்டால் என்ன செய்வது?
அறிமுகம்
வரிசையாக்க உறுப்புகள் என்பது டெவலப்பர் கட்டாயம் தெரிந்திருக்க வேண்டிய அல்காரிதம் வகைகளில் ஒன்றாகும். நான் பள்ளியில் படிக்கும் போது கணினி அறிவியலை பெரிதாக எடுத்துக் கொள்ளவில்லை என்றால், இன்றைய மாணவர்கள் வரிசையாக்க வழிமுறைகளை செயல்படுத்தி புரிந்து கொள்ள வேண்டும். அடிப்படை வழிமுறைகள், எளிமையானவை, லூப்பைப் பயன்படுத்தி செயல்படுத்தப்படுகின்றன . இயற்கையாகவே, ஒரு வரிசை போன்ற உறுப்புகளின் தொகுப்பை வரிசைப்படுத்த, நீங்கள் எப்படியாவது சேகரிப்பு வழியாக செல்ல வேண்டும். உதாரணத்திற்கு:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
குறியீட்டின் இந்த பிரிவைப் பற்றி என்ன சொல்ல முடியும்? எங்களிடம் ஒரு லூப் உள்ளது, அதில் குறியீட்டை ( int i) 0 இலிருந்து வரிசையின் கடைசி உறுப்புக்கு மாற்றுவோம். உண்மையில், வரிசையில் உள்ள ஒவ்வொரு உறுப்பையும் எடுத்து அதன் உள்ளடக்கங்களை அச்சிடுகிறோம். வரிசையில் அதிக உறுப்புகள் இருந்தால், குறியீடு முடிக்க அதிக நேரம் எடுக்கும். அதாவது, nஉறுப்புகளின் எண்ணிக்கை என்றால், n = 10நிரல் எப்போது இயங்கும் நேரத்தை விட இரண்டு மடங்கு நேரம் எடுக்கும் n = 5. எங்கள் நிரல் ஒரு ஒற்றை வளையத்தைக் கொண்டிருந்தால், செயல்படுத்தும் நேரம் நேர்கோட்டில் வளரும்: அதிக கூறுகள் இருந்தால், செயல்படுத்தும் நேரம் நீண்டது. மேலே உள்ள அல்காரிதம் நேரியல் நேரத்தில் (n இன் நேரியல் செயல்பாடு) வேலை செய்கிறது என்று மாறிவிடும். இதுபோன்ற சந்தர்ப்பங்களில், அல்காரிதத்தின் சிக்கலானது "O(n)" என்று கூறுகிறோம். இந்த குறியீடு "பெரிய ஓ" அல்லது "அறிகுறியற்ற நடத்தை" என்றும் அழைக்கப்படுகிறது. ஆனால் உங்களால் நினைவில் கொள்ள முடியும்"
எளிமையான வரிசையாக்க அல்காரிதம் (குமிழி வரிசை)
எங்களிடம் ஒரு வரிசை உள்ளது என்று வைத்துக்கொள்வோம், அதன் மூலம் மீண்டும் மீண்டும் செய்யலாம். நன்று. இப்போது அதை ஏறுவரிசையில் வரிசைப்படுத்த முயற்சிப்போம். இதன் பொருள் என்ன? இரண்டு கூறுகள் கொடுக்கப்பட்டால் (உதாரணமாக, a = 6, b = 5), நாம் மறுசீரமைக்க வேண்டும் aமற்றும் bஎன்றால் (என்றால் ) aஅதிகமாக இருந்தால் . ஒரு தொகுப்பில் வேலை செய்ய ஒரு குறியீட்டைப் பயன்படுத்தும்போது (வரிசையைப் போலவே) இது என்ன அர்த்தம்? குறியீட்டு ( ) கொண்ட உறுப்பை விட குறியீட்டு a உடன் கூடிய உறுப்பு பெரியதாக இருந்தால் , உறுப்புகள் மாற்றப்பட வேண்டும். இடங்களை மாற்ற பல்வேறு வழிகள் உள்ளன. ஆனால் எளிமையான, புரிந்துகொள்ளக்கூடிய மற்றும் நினைவில் கொள்ள எளிதான ஒரு நுட்பத்தைப் பயன்படுத்துவோம்: ba > bbarray[a] > array[b]
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
இப்போது நாம் பின்வருவனவற்றை எழுதலாம்:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
நீங்கள் பார்க்க முடியும் என, உறுப்புகள் உண்மையில் மாற்றப்பட்டன. நாங்கள் குறியீட்டு 1 உடன் தொடங்கினோம், ஏனெனில் அணிவரிசையில் ஒரே ஒரு உறுப்பு இருந்தால், array[i] < array[i-1]குறியீட்டுக்கு வெளிப்பாடு தவறானது 0. இதைச் செய்வது, அணிவரிசையில் உறுப்புகள் இல்லாத அல்லது ஒரே ஒரு உறுப்பு இல்லாத சூழ்நிலைகளிலிருந்தும் நம்மைப் பாதுகாக்கிறது, மேலும் இது குறியீட்டை சிறப்பாகக் காண்பிக்கும். ஆனால் வரிசைப்படுத்தப்பட்ட வரிசை இன்னும் வரிசைப்படுத்தப்படவில்லை, ஏனெனில் வரிசைப்படுத்த ஒரு பாஸ் போதாது. வரிசைப்படுத்தப்பட்ட வரிசையைப் பெறும் வரை மீண்டும் மீண்டும் பாஸ்களைச் செய்யும் மற்றொரு வளையத்தைச் சேர்க்க வேண்டும்:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
எனவே எங்கள் முதல் வரிசையாக்க வழிமுறையை முடித்தோம். whileமேலும் மறு செய்கைகள் தேவையில்லை என்று முடிவு செய்யும் வரை வெளிப்புற சுழற்சியை ( ) மீண்டும் செய்கிறோம் . முன்னிருப்பாக, ஒவ்வொரு புதிய மறு செய்கைக்கு முன்பும், எங்கள் அணிவரிசை வரிசைப்படுத்தப்பட்டதாகக் கருதுகிறோம், மேலும் நாம் லூப் செய்யத் தேவையில்லை. அதன்படி, நாம் உறுப்புகள் மூலம் வரிசையாக நகர்த்தி இந்த அனுமானத்தை சரிபார்க்கிறோம். ஆனால் உறுப்புகள் ஒழுங்காக இல்லை என்றால், நாம் உறுப்புகளை மாற்றி, உறுப்புகள் சரியான வரிசையில் உள்ளன என்பதற்கு இப்போது உத்தரவாதம் இல்லை என்பதை புரிந்துகொள்கிறோம். இதன் பொருள் நாம் மற்றொரு மறு செய்கையைச் செய்ய வேண்டும். உதாரணமாக, நம்மிடம் உள்ளது என்று வைத்துக்கொள்வோம் [3, 5, 2]. 5விட அதிகமாக உள்ளது 3- எல்லாம் நன்றாக இருக்கிறது. ஆனால் 2விட குறைவாக உள்ளது 5. இருப்பினும், [3, 2, 5]மற்றொரு பாஸ் தேவைப்படுகிறது3 > 2மேலும் அவை மாற்றப்பட வேண்டும். நாம் ஒரு வளையத்திற்குள் ஒரு வளையத்தைப் பயன்படுத்துவதால், நமது வழிமுறையின் சிக்கலானது அதிகரிக்கிறது. கொடுக்கப்பட்ட nகூறுகள், அது ஆகிறது n * n, அதாவது, O(n^2). இது இருபடி சிக்கலானது என்று அழைக்கப்படுகிறது. பொதுவாக, எத்தனை மறு செய்கைகள் தேவைப்படும் என்பதை நாம் சரியாக அறிய முடியாது. ஒரு அல்காரிதத்தின் சிக்கலான வெளிப்பாடு, மோசமான நிலையில் சிக்கலானது எப்படி அதிகரிக்கிறது என்பதைக் காட்டுகிறது. அதாவது, உறுப்புகளின் எண்ணிக்கை மாறும்போது செயல்படுத்தும் நேரம் எவ்வளவு அதிகரிக்கும் என்பதை இது குறிக்கிறது n. குமிழி வரிசையாக்கம் என்பது எளிமையான மற்றும் திறமையற்ற வரிசையாக்க வழிமுறைகளில் ஒன்றாகும். இது சில நேரங்களில் "முட்டாள் வகை" என்றும் அழைக்கப்படுகிறது. இந்த தலைப்பில் பொருள்:
மற்றொரு வரிசையாக்க அல்காரிதம் தேர்வு வரிசை ஆகும். இது இருபடி சிக்கலான தன்மையையும் கொண்டுள்ளது, ஆனால் அதைப் பற்றி பின்னர். எனவே யோசனை எளிது. ஒவ்வொரு பாஸிலும், சிறிய உறுப்பைத் தேர்ந்தெடுத்து அதை தொடக்கத்திற்கு மாற்றுவோம். கூடுதலாக, ஒவ்வொரு பாஸும் வலதுபுறம் ஒரு படி தொடங்குகிறது. வேறு வார்த்தைகளில் கூறுவதானால், முதல் பாஸ் பூஜ்ஜிய உறுப்பிலிருந்து தொடங்குகிறது, இரண்டாவது பாஸ் முதல், முதலியன. இது இப்படி இருக்கும்:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
இந்த வகை நிலையற்றது, ஏனெனில் ஒரே மாதிரியான கூறுகள் (உறுப்புகளை வரிசைப்படுத்த நாம் பயன்படுத்தும் எந்தப் பண்புகளின் அடிப்படையில்) அவற்றின் தொடர்புடைய நிலைகளை மாற்ற முடியும். தேர்வு வரிசை பற்றிய விக்கிபீடியா கட்டுரையில் ஒரு நல்ல உதாரணம் உள்ளது . இந்த தலைப்பில் பொருள்:
செருகும் வரிசையும் இருபடி சிக்கலான தன்மையைக் கொண்டுள்ளது, ஏனெனில் மீண்டும் ஒரு வளையத்திற்குள் ஒரு வளையம் உள்ளது. செருகுவதை வேறுபடுத்துவது எது? இந்த வரிசையாக்க அல்காரிதம் "நிலையானது." இதன் பொருள் ஒரே மாதிரியான கூறுகள் அவற்றின் தொடர்புடைய வரிசையை மாற்றாது. மீண்டும், நாம் வரிசைப்படுத்தும் பண்புகளின் அடிப்படையில் ஒரே மாதிரியாக இருக்கிறோம்.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
ஷட்டில் வரிசை
மற்றொரு எளிய வரிசையாக்க அல்காரிதம் உள்ளது: ஷட்டில் வரிசை. இது இருதரப்பு குமிழி வரிசை அல்லது காக்டெய்ல் ஷேக்கர் வகை என்றும் அழைக்கப்படுகிறது. இந்த மாற்றுப் பெயர்கள், விண்கலம் என்பது விண்வெளி விண்கலத்தைப் பற்றியது அல்ல என்பதை நமக்குச் சொல்கிறது. இது முன்னும் பின்னுமாக நகரும் ஒன்றைப் பற்றியது. இந்த அல்காரிதம் பற்றி நீங்கள் நினைக்கும் போது இப்போது நீங்கள் அதை நினைக்கலாம். அல்காரிதத்தின் சாராம்சம் என்ன? அல்காரிதத்தின் சாராம்சம் என்னவென்றால், நாம் இடமிருந்து வலமாக மீண்டும் செய்கிறோம், உறுப்புகளை மாற்றுகிறோம் மற்றும் மற்ற திசையில் எஞ்சியிருக்கும் உறுப்புகள் ஏதேனும் மாற்றப்பட வேண்டுமா என்று சரிபார்க்கிறோம்.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
மற்றொரு எளிய வரிசையாக்க வழிமுறை ஷெல் வரிசையாகும். அதன் சாராம்சம் குமிழி வரிசையைப் போன்றது, ஆனால் ஒவ்வொரு மறு செய்கையிலும் ஒப்பிடப்பட்ட கூறுகளுக்கு இடையில் வேறுபட்ட இடைவெளி உள்ளது. ஒவ்வொரு மறு செய்கையிலும் இது பாதியாக வெட்டப்படுகிறது. இதோ ஒரு செயல்படுத்தல்:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
இந்த எளிய வரிசையாக்க வழிமுறைகளுக்கு கூடுதலாக, மிகவும் சிக்கலான வரிசையாக்க வழிமுறைகளும் உள்ளன. எடுத்துக்காட்டாக, ஒன்றிணைக்கும் வரிசை. கவனிக்க வேண்டிய இரண்டு விஷயங்கள் உள்ளன. முதலில், மறுநிகழ்வு இங்கே நம் மீட்புக்கு வருகிறது. இரண்டாவதாக, அல்காரிதத்தின் சிக்கலானது நாம் பழகியதைப் போல இருபடியாக இருக்காது. இந்த அல்காரிதம் சிக்கலானது மடக்கை ஆகும். இது என எழுதப்பட்டுள்ளது O(n log n). எனவே அதை செயல்படுத்துவோம். முதலில், வரிசைப்படுத்தும் முறைக்கு ஒரு சுழல்நிலை அழைப்பை எழுதுவோம்:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
இப்போது, முக்கிய செயலைச் செயல்படுத்துவதில் சேர்ப்போம். இங்கே எங்கள் சூப்பர் முறை:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
அழைப்பதன் மூலம் நமது உதாரணத்தை இயக்கலாம்mergeSort(array, 0, array.length-1). நீங்கள் பார்க்கிறபடி, வரிசைப்படுத்தப்பட வேண்டிய பிரிவின் ஆரம்பம் மற்றும் முடிவின் அறிகுறிகளுடன் உள்ளீட்டு வரிசையை ஏற்றுக்கொள்வதில் செயல்முறை கொதிக்கிறது. வரிசையாக்கம் தொடங்கும் போது, இவை வரிசையின் தொடக்கமும் முடிவும் ஆகும். பின்னர் நாம் பிரிவைக் கணக்கிடுகிறோம், இது வரிசையை பிரிக்கும் குறியீட்டாகும். வரிசையை 2 பகுதிகளாகப் பிரிக்க முடியுமானால், அணிவரிசையின் இரண்டு பகுதிகளுக்கு வரிசை முறையை மீண்டும் மீண்டும் அழைக்கிறோம். நாங்கள் ஒரு துணை இடையகத்தை தயார் செய்கிறோம், அங்கு வரிசைப்படுத்தப்பட்ட பகுதியைச் செருகுவோம். அடுத்து, வரிசைப்படுத்த வேண்டிய பிரிவின் தொடக்கத்தில் குறியீட்டை அமைத்து, வெற்று இடையகத்தின் ஒவ்வொரு உறுப்பு வழியாகவும் நடக்கத் தொடங்கவும், அதை சிறிய கூறுகளுடன் நிரப்பவும். குறியீடால் சுட்டிக்காட்டப்பட்ட உறுப்பு, பிரிப்பான் சுட்டிக்காட்டிய உறுப்பைக் காட்டிலும் குறைவாக இருந்தால், அந்த உறுப்பை பஃபரில் வைத்து, குறியீட்டை மாற்றுவோம். இல்லையெனில், டிலிமிட்டரால் சுட்டிக்காட்டப்பட்ட உறுப்பை இடையகத்திற்குள் வைத்து பிரிப்பானை மாற்றுவோம். வரிசைப்படுத்தப்பட்ட பிரிவின் எல்லைகளைத் தாண்டியவுடன் அல்லது முழு வரிசையையும் நிரப்பினால், குறிப்பிட்ட வரம்பு வரிசைப்படுத்தப்பட்டதாகக் கருதப்படுகிறது.இந்த தலைப்பில் பொருள்:
மற்றொரு சுவாரஸ்யமான வரிசையாக்க அல்காரிதம் எண்ணும் வரிசை ஆகும். இங்கே அல்காரிதம் சிக்கலானது O(n+k), இது nஉறுப்புகளின் எண்ணிக்கை மற்றும் kஒரு தனிமத்தின் அதிகபட்ச மதிப்பு. இந்த அல்காரிதம் ஒரு குறைபாட்டைக் கொண்டுள்ளது: வரிசையில் உள்ள குறைந்தபட்ச மற்றும் அதிகபட்ச மதிப்புகளை நாம் அறிந்து கொள்ள வேண்டும். எண்ணும் வகையின் உதாரணம் இங்கே:
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
குறைந்தபட்ச மற்றும் அதிகபட்ச மதிப்புகளை நாம் முன்கூட்டியே தெரிந்து கொள்ள வேண்டியிருக்கும் போது இது மிகவும் சிரமமாக இருக்கிறது என்பதை நீங்கள் புரிந்து கொள்ளலாம். நாம் இங்கே மற்றொரு வழிமுறையைப் பெற்றுள்ளோம்: ரேடிக்ஸ் வரிசை. நான் இங்கே அல்காரிதத்தை காட்சியாக மட்டுமே தருகிறேன். செயல்படுத்துவதற்கான துணைப் பொருட்களைப் பார்க்கவும்: பொருட்கள்:
சரி, இது இனிப்புக்கான நேரம் - விரைவான வரிசைப்படுத்தல், மிகவும் பிரபலமான வரிசையாக்க வழிமுறைகளில் ஒன்று. இது மடக்கை சிக்கலானது: O(n log n). இந்த வரிசையாக்க அல்காரிதம் டோனி ஹோரே என்பவரால் உருவாக்கப்பட்டது. சுவாரஸ்யமாக, அவர் சோவியத் யூனியனில் வாழ்ந்தபோது அதைக் கண்டுபிடித்தார், அங்கு அவர் மாஸ்கோ பல்கலைக்கழகத்தில் இயந்திர மொழிபெயர்ப்பைப் படித்தார் மற்றும் ரஷ்ய-ஆங்கில சொற்றொடர் புத்தகத்தை உருவாக்கினார். மேலும் என்னவென்றால், ஜாவா இந்த அல்காரிதத்தின் மிகவும் சிக்கலான பதிப்பை இல் பயன்படுத்துகிறது Arrays.sort. பற்றி என்ன Collections.sort? "ஹூட்டின் கீழ்" விஷயங்கள் எவ்வாறு வரிசைப்படுத்தப்படுகின்றன என்பதை ஏன் பார்க்கக்கூடாது? குறியீடு இதோ:
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
இவை அனைத்தும் மிகவும் பயமுறுத்தும் விஷயங்கள், எனவே அதை தோண்டி எடுப்போம். உள்ளீட்டு வரிசைக்கு ( int[]மூலம்), நாங்கள் இரண்டு குறிப்பான்களை உருவாக்குகிறோம்: இடது ( L) மற்றும் வலது ( R). முதல் முறை அழைப்பின் போது, அவை வரிசையின் ஆரம்பம் மற்றும் முடிவுக்கு ஒத்திருக்கும். பின்னர் நாம் பிவோட் உறுப்பைக் கண்டறிகிறோம், அதற்குப் பொருத்தமாக பெயரிடப்பட்டுள்ளது pivot. pivotஇதற்குப் பிறகு, எங்கள் பணியானது மதிப்புகளை இடதுபுறமாக விட சிறியதாகவும் pivot, பெரியவற்றை - வலதுபுறமாகவும் நகர்த்துவதாகும் . Lஇதைச் செய்ய, முதலில் மார்க்கரை விட அதிகமான மதிப்பைக் கண்டுபிடிக்கும் வரை நகர்த்துவோம் pivot. சிறிய மதிப்பு இல்லை என்றால், பின்னர்
எல் சமமாகிறது
pivot.
Rபின்னர் சிறிய மதிப்பைக் கண்டுபிடிக்கும் வரை மார்க்கரை நகர்த்துவோம்
pivot. பெரிய மதிப்பு இல்லை எனில்,
Rசமமாக மாறும்
pivot. அடுத்து,
Lமார்க்கர் மார்க்கருக்கு முன் இருந்தால் அல்லது அதனுடன் இணைந்தால், உறுப்பு உறுப்புக்கு குறைவாக
Rஇருந்தால் உறுப்புகளை மாற்ற முயற்சிப்போம் . பின்னர் நாம் 1 ஆல் வலதுபுறம் மாறுகிறோம், மேலும் 1 ஆல் இடப்புறமாக மாறுகிறோம். மார்க்கர் மார்க்கருக்கு அப்பால் நகரும் போது , பரிமாற்றம் முடிந்தது என்று அர்த்தம்: சிறிய மதிப்புகள் இடதுபுறம் , பெரிய மதிப்புகள் வலதுபுறம்
LRLRLRpivotpivot. இதற்குப் பிறகு, சப்அரேயில் அதே வரிசை முறையை மீண்டும் மீண்டும் அழைக்கிறோம் - பிரிவின் தொடக்கத்திலிருந்து வலது மார்க்கருக்கு வரிசைப்படுத்தவும், இடது மார்க்கரில் இருந்து வரிசைப்படுத்த வேண்டிய பிரிவின் இறுதி வரை. ஏன் ஆரம்பம் முதல் சரியான மார்க்கர் வரை? ஏனெனில் மறு செய்கையின் முடிவில், வலது மார்க்கர் இடது பகுதியின் எல்லையாக மாறும் அளவுக்கு நகர்கிறது. இந்த அல்காரிதம் எளிமையான வரிசையாக்கத்தை விட மிகவும் சிக்கலானது, எனவே அதை ஓவியமாக வரைவது சிறந்தது. ஒரு வெள்ளைத் தாளை எடுத்து எழுதவும்: 4 2 6 7 3. பிறகு
pivotநடுவில் அதாவது எண் 6-ன் கீழ் எழுதவும். அதை வட்டமிடவும். 4 கீழ், எழுது
L, மற்றும் 3 கீழ், எழுத
R. 6ஐ விட 4 குறைவு, 6ஐ விட 2 குறைவு . கடந்த நிலைக்குச் செல்ல முடியாததால் , நாம் நிலைக்குச்
Lசெல்கிறோம் .
pivotLpivot, நிபந்தனைக்கு ஏற்ப. மீண்டும் 4 2 6 7 3. வட்டம் 6 ( ) என்று எழுதி அதன் அடியில்
pivotவைக்கவும் .
Lஇப்போது மார்க்கரை நகர்த்தவும்
R. 3 என்பது 6 ஐ விடக் குறைவாக உள்ளது, எனவே
Rமார்க்கரை 3 இல் வைக்கவும். 3 என்பது 6 (
pivot) ஐ விடக் குறைவாக இருப்பதால், நாங்கள் ஒரு
swap. முடிவை எழுதவும்: 4 2 3 7 6. வட்டம் 6, ஏனெனில் அது இன்னும்
pivot. குறிப்பான்
L3 இல் உள்ளது. குறிப்பான் 6 இல் உள்ளது. அதைத் தாண்டி நகரும்
Rவரை நாம் குறிப்பான்களை நகர்த்துகிறோம் என்பதை நினைவில் கொள்ளுங்கள் . அடுத்த எண்ணுக்குச் செல்லவும் . இங்கே நான் இரண்டு சாத்தியக்கூறுகளை ஆராய விரும்புகிறேன்: 1) இறுதி எண் 7 மற்றும் 2) 1 ஆக இருக்கும் வழக்கு, 7 அல்ல.
இறுதி எண் 1 என்றால்: மார்க்கரை 1 க்கு நகர்த்தவும் , ஏனெனில் நாம் நகர்த்தலாம் வரை
LRLLLLகுறிப்பான் சிறிய எண்ணைக் குறிக்கிறது
pivot. ஆனால் நம்மால் 6-ல் இருந்து நகர்த்த முடியாது , ஏனென்றால் மார்க்கர் க்கு அதிகமாக இருக்கும் எண்ணை சுட்டிக்காட்டினால்
Rமட்டுமே R ஐ நகர்த்த முடியும் . 6ஐ விட 1 குறைவாக இருப்பதால், நாங்கள் ஒரு செயலைச் செய்யவில்லை . தற்போதைய நிலையை எழுதவும்: 4 2 3 1 6. வட்டம் 6 ( ). நகர்ந்து நகர்வதை நிறுத்துகிறது. நகராது. நாங்கள் பரிமாற்றம் செய்வதில்லை. மாற்றம் மற்றும் ஒரு நிலையில். மார்க்கரை 1 இன் கீழ் எழுதவும். மார்க்கர் எல்லைக்கு வெளியே உள்ளது. வரம்பிற்கு அப்பாற்பட்டதால், நாங்கள் எதுவும் செய்வதில்லை . ஆனால், நாங்கள் மீண்டும் 4 2 3 1 என்று எழுதுகிறோம், ஏனெனில் இது நமது இடது பக்கம், இது (6) ஐ விட குறைவாக உள்ளது. புதியதைத் தேர்ந்தெடுத்து எல்லாவற்றையும் மீண்டும் தொடங்கவும் :)
இறுதி எண் 7 என்றால்:RpivotswappivotLpivotRLRRLLpivotpivot
மார்க்கரை 7 க்கு நகர்த்தவும்
L. சரியான மார்க்கரை எங்களால் நகர்த்த முடியாது, ஏனெனில் அது ஏற்கனவே பிவோட்டைச் சுட்டிக்காட்டுகிறது. 7 ஐ விட பெரியது
pivot, எனவே நாங்கள் ஒரு செய்கிறோம்
swap. முடிவை எழுதவும்: 4 2 3 6 7. வட்டம் 6, ஏனெனில் அது
pivot. மார்க்கர்
Lஇப்போது 7 க்கு மாற்றப்பட்டுள்ளது, மேலும் மார்க்கர் 3 க்கு மாற்றப்பட்டுள்ளது. பகுதியை முதல் இறுதி வரை
Rவரிசைப்படுத்துவதில் அர்த்தமில்லை , ஏனெனில் 1 உறுப்பு மட்டுமே உள்ளது. இருப்பினும், வரிசைப்படுத்துவதற்காக
L4 இலிருந்து பகுதியை மார்க்கருக்கு அனுப்புகிறோம் .
Rநாங்கள் ஒன்றைத் தேர்ந்தெடுத்து
pivotமீண்டும் தொடங்குகிறோம் :) முதல் பார்வையில், நீங்கள் நிறைய மதிப்புகளைச் சேர்த்தால், சமமாகத் தோன்றலாம்.
pivot, பிறகு நீங்கள் அல்காரிதத்தை உடைப்பீர்கள். ஆனால் இது அப்படியல்ல. நீங்கள் தந்திரமான சேர்க்கைகளைப் பற்றி சிந்திக்கலாம் மற்றும் காகிதத்தில் எல்லாம் சரியானது என்று உங்களை நம்பிக் கொள்ளலாம் மற்றும் இதுபோன்ற எளிய செயல்கள் அத்தகைய நம்பகமான வரிசையாக்க பொறிமுறையை செயல்படுத்துவதில் ஆச்சரியமாக இருக்கிறது. ஒரே குறை என்னவென்றால், இந்த வரிசையாக்க அல்காரிதம் நிலையானதாக இல்லை. ஏனென்றால், ஒரு இடமாற்று ஒரே மாதிரியான உறுப்புகளின் ஒப்பீட்டு வரிசையை மாற்றக்கூடும், அவற்றில் ஒன்று முன்பு எதிர்கொண்டால்,
pivotமற்ற உறுப்பு முந்தைய பகுதிக்கு மாற்றப்படும்
pivot.
அடிக்கோடு
மேலே, ஜாவாவில் செயல்படுத்தப்பட்ட "ஜென்டில்மேன்" வரிசைப்படுத்தும் அல்காரிதம்களின் தொகுப்பைப் பார்த்தோம். அல்காரிதம்கள் பொதுவாக உபயோகமான கண்ணோட்டத்தில் இருந்தும், எப்படி சிந்திக்க வேண்டும் என்பதைக் கற்றுக்கொள்வதற்கும் பயனுள்ளதாக இருக்கும். சில எளிமையானவை, சில மிகவும் சிக்கலானவை. புத்திசாலிகள் சிலருக்கு தங்கள் ஆய்வுக் கட்டுரைகளை ஆதரித்தனர். மற்றவர்களுக்கு, அவர்கள் மிகவும் தடிமனான புத்தகங்களை எழுதினார்கள். இந்த கட்டுரை ஏற்கனவே பாரமானதாக மாறிய ஒரு கண்ணோட்டம் மட்டுமே என்பதால், துணைப் பொருட்கள் இன்னும் அதிகமாக அறிய உதவும் என்று நம்புகிறேன். மற்றும் அதன் நோக்கம் ஒரு சிறிய அறிமுகத்தை வழங்குவதாகும்.
நீங்கள் "Grokking Algorithms " ஐப் படித்தால், அல்காரிதம்களுக்கான அறிமுகத்தையும் காணலாம் . ஜாக் பிரவுனின் பிளேலிஸ்ட்டையும் விரும்புகிறேன்:
AQA முடிவு 1 1.01 ஒரு அல்காரிதம் டிரேசிங் . வேடிக்கைக்காக, வரிசைப்படுத்தும்போது அல்காரிதம் காட்சிப்படுத்தல்களைப் பார்க்கலாம்
.Visualgo.net .
GO TO FULL VERSION