الگوریتم های مرتب سازی در تئوری و عملی

مرتب سازی یکی از عملیات اساسی است که ما روی اشیا انجام می دهیم. حتی در دوران کودکی، به کودکان آموزش داده می شود که با رشد مهارت های فکری خود، مرتب سازی کنند. کامپیوتر و نرم افزار نیز از این قاعده مستثنی نیستند. الگوریتم های مرتب سازی بسیار متنوعی در جاوا وجود دارد . پیشنهاد می‌کنم بررسی کنید که چه هستند و چگونه کار می‌کنند. اگر روزی در مصاحبه ای از شما در مورد یکی از آنها سوال شود چه؟

معرفی

مرتب سازی عناصر یکی از دسته الگوریتم هایی است که یک توسعه دهنده باید بداند. اگر زمانی که من در مدرسه بودم علوم کامپیوتر جدی گرفته نمی شد، دانش آموزان امروزی باید بتوانند الگوریتم های مرتب سازی را پیاده سازی و درک کنند. الگوریتم های پایه، ساده ترین، با استفاده از حلقه for پیاده سازی می شوند . به طور طبیعی، برای مرتب کردن مجموعه ای از عناصر، مانند یک آرایه، باید به نحوی مجموعه را مرور کنید. مثلا:

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)" است. به این نماد "O بزرگ" یا "رفتار مجانبی" نیز می گویند. اما شما فقط می توانید "پیچیدگی الگوریتم" را به خاطر بسپارید.

ساده ترین الگوریتم مرتب سازی (مرتب سازی حبابی)

فرض کنید یک آرایه داریم و می توانیم از طریق آن تکرار کنیم. عالی. حالا بیایید سعی کنیم آن را به ترتیب صعودی مرتب کنیم. این یعنی چی؟ به این معنی که با توجه به دو عنصر (مثلاً a = 6، b = 5)، باید مرتب سازی مجدد کنیم aو bif aبزرگتر از b(if a > b) است. وقتی از یک شاخص برای کار با یک مجموعه استفاده می کنیم (همانطور که در مورد یک آرایه وجود دارد) این به چه معناست؟ به این معنی که اگر عنصر با شاخص a بزرگتر از عنصر با شاخص b( array[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]برای index نامعتبر است 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تغییر تعداد عناصر، زمان اجرا چقدر افزایش می یابد. مرتب‌سازی حبابی یکی از ساده‌ترین و ناکارآمدترین الگوریتم‌های مرتب‌سازی است. گاهی اوقات به آن "مرتب سازی احمقانه" نیز می گویند. مطالب مربوط به این موضوع:

• "HackerRank: الگوریتم ها - مرتب سازی حباب "

مرتب سازی انتخابی

یکی دیگر از الگوریتم های مرتب سازی انتخاب مرتب سازی است. همچنین دارای پیچیدگی درجه دوم است، اما بعداً در مورد آن بیشتر توضیح خواهیم داد. بنابراین ایده ساده است. در هر پاس، کوچکترین عنصر را انتخاب می کنیم و آن را به ابتدا منتقل می کنیم. علاوه بر این، هر پاس یک قدم به سمت راست شروع می شود. به عبارت دیگر، پاس اول از عنصر صفر شروع می شود، پاس دوم از عنصر اول و ... به این صورت خواهد بود:

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));

این مرتب‌سازی ناپایدار است، زیرا عناصر یکسان (از نظر ویژگی‌هایی که برای مرتب‌سازی عناصر استفاده می‌کنیم) می‌توانند موقعیت نسبی خود را تغییر دهند. یک مثال خوب در مقاله ویکی پدیا در مورد مرتب سازی انتخاب وجود دارد . مطالب مربوط به این موضوع:

• "CS50: انتخاب مرتب سازی"

مرتب سازی درج

مرتب‌سازی درج نیز پیچیدگی درجه دوم دارد، زیرا ما دوباره یک حلقه در یک حلقه داریم. چه چیزی مرتب‌سازی درج را متفاوت می‌کند؟ این الگوریتم مرتب سازی "پایدار" است. این بدان معنی است که عناصر یکسان ترتیب نسبی خود را تغییر نمی دهند. باز هم، منظور ما از نظر ویژگی هایی که بر اساس آنها مرتب می کنیم، یکسان هستند.

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));

مطالب مربوط به این موضوع:

• AQA Decision 1 2.02a معرفی مرتب سازی شاتل توسط جک براون

مرتب سازی پوسته

یکی دیگر از الگوریتم های مرتب سازی ساده، مرتب سازی پوسته است. خلاصه آن شبیه به مرتب سازی حبابی است، اما در هر تکرار، شکاف متفاوتی بین عناصر مقایسه شده داریم. با هر بار تکرار از وسط نصف می شود. در اینجا یک پیاده سازی است:

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));

مطالب مربوط به این موضوع:

• AQA Decision 1 2.03a Shell Sort - مثالی با 8 عدد

ادغام مرتب سازی

علاوه بر این الگوریتم های مرتب سازی ساده، الگوریتم های مرتب سازی پیچیده تری نیز وجود دارد. مثلا ادغام مرتب سازی. دو نکته قابل توجه است. اول، بازگشت به نجات ما در اینجا می آید. دوم، پیچیدگی الگوریتم دیگر آنطور که ما به آن عادت کرده ایم، درجه دوم نیست. پیچیدگی این الگوریتم لگاریتمی است. این به صورت نوشته شده است 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 قسمت تقسیم کرد، روش مرتب سازی را به صورت بازگشتی برای دو نیمه آرایه فراخوانی می کنیم. ما یک بافر کمکی آماده می کنیم که در آن بخش مرتب شده را وارد می کنیم. سپس، شاخص را در ابتدای بخش تنظیم کنید و شروع به قدم زدن در هر عنصر بافر خالی کنید و آن را با کوچکترین عناصر پر کنید. اگر عنصری که شاخص به آن اشاره می کند کمتر از عنصری باشد که جداکننده به آن اشاره می کند، عنصر را در بافر قرار می دهیم و شاخص را جابجا می کنیم. در غیر این صورت، عنصری را که جداکننده به آن اشاره می کند، در بافر قرار می دهیم و جداکننده را تغییر می دهیم. به محض اینکه جداکننده از مرزهای قسمت در حال مرتب سازی فراتر رفت یا کل آرایه را پر کنیم، محدوده مشخص شده مرتب شده در نظر گرفته می شود. مطالب مربوط به این موضوع:

• CS50: مرتب سازی ادغام
• دستورالعمل ایده - مرتب سازی ادغام

شمارش مرتب سازی و مرتب سازی ریشه

یکی دیگر از الگوریتم های مرتب سازی جالب، شمارش مرتب سازی است. پیچیدگی الگوریتمی در اینجا این است 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). این الگوریتم مرتب سازی توسط Tony Hoare توسعه داده شده است. جالب اینجاست که او زمانی که در اتحاد جماهیر شوروی زندگی می کرد، آن را اختراع کرد، جایی که در دانشگاه مسکو مترجمی ماشینی خواند و یک کتاب عبارات روسی-انگلیسی توسعه داد. علاوه بر این، جاوا از نسخه پیچیده تری از این الگوریتم در استفاده می کند 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. اگر مقدار کمتری پیدا نشد، پس L برابر می شود pivot. سپس Rنشانگر را حرکت می دهیم تا مقداری کوچکتر از pivot. اگر مقدار بزرگ تری پیدا نشد، Rبرابر می شود pivot. در مرحله بعد، اگر Lنشانگر قبل از نشانگر باشد یا با آن منطبق باشد، در صورتی که عنصر کمتر از عنصر باشد، Rسعی می کنیم عناصر را عوض کنیم . سپس با 1 به سمت راست و 1 به چپ تغییر می کنیم . هنگامی که نشانگر فراتر از نشانگر حرکت می کند، به این معنی است که تعویض کامل شده است: مقادیر کوچکتر در سمت چپ و مقادیر بزرگتر در سمت راست هستند . پس از این، ما همان روش مرتب‌سازی را به صورت بازگشتی در زیرآرایه‌ها فراخوانی می‌کنیم - از ابتدای قسمتی که باید مرتب‌سازی شود به نشانگر سمت راست و از نشانگر سمت چپ تا انتهای بخشی که باید مرتب شود. چرا از ابتدا به نشانگر سمت راست؟ زیرا در پایان یک تکرار، مشخص می شود که نشانگر سمت راست به اندازه ای حرکت می کند که به مرز قسمت چپ تبدیل شود. این الگوریتم پیچیده تر از مرتب سازی ساده است، بنابراین بهتر است آن را ترسیم کنید. یک برگه سفید بردارید و بنویسید: 4 2 6 7 3. سپس در وسط، یعنی زیر شماره 6 بنویسید. دور آن دایره بکشید. زیر 4 بنویسید و زیر 3 بنویسید . 4 کمتر از 6، 2 کمتر از 6. ما در نهایت به سمت موقعیت حرکت می کنیم، زیرا طبق شرایط نمی توان از گذشته عبور کرد . دوباره 4 2 6 7 3 را بنویسید. 6 ( ) را دایره کنید و زیر آن قرار دهید. حالا نشانگر را حرکت دهید. 3 کوچکتر از 6 است، بنابراین نشانگر را روی 3 قرار دهید. از آنجایی که 3 کوچکتر از 6 است ، یک . نتیجه را بنویسید: 4 2 3 7 6. دایره 6 بزنید، زیرا هنوز هم . نشانگر روی 3 است. نشانگر روی 6 است. به یاد داشته باشید که ما نشانگرها را تا زمانی که به فراتر از آن حرکت می کنیم حرکت می دهیم . به شماره بعدی بروید . در اینجا می خواهم دو احتمال را بررسی کنم: 1) موردی که عدد ماقبل آخر 7 است و 2) موردی که 1 است نه 7. اگر عدد ماقبل آخر 1 است: نشانگر را به 1 منتقل کنید ، زیرا می توانیم حرکت کنیم. تا زمانی که نشانگر به عددی کوچکتر از . اما نمی‌توانیم از 6 فاصله بگیریم، زیرا تنها زمانی می‌توانیم R را حرکت دهیم که نشانگر به عددی بزرگ‌تر از . ما a را اجرا نمی کنیم ، زیرا 1 کمتر از 6 است. وضعیت فعلی را بنویسید: 4 2 3 1 6. دایره 6 ( ). جابجا می شود و حرکت را متوقف می کند. حرکت نمی کند ما مبادله ای انجام نمی دهیم. شیفت و با یک موقعیت. نشانگر را زیر 1 بنویسید. نشانگر خارج از محدوده است. زیرا L R L R L R pivot pivot pivot L R L pivot L pivot pivot L R R pivot swap pivot L R L R L L L L pivot R R pivot swap pivot L pivot R L R R L Lخارج از محدوده است، ما هیچ کاری نمی کنیم. اما، دوباره 4 2 3 1 می نویسیم، زیرا این سمت چپ ما است که کمتر از pivot(6) است. جدید را انتخاب کنید pivotو همه چیز را دوباره شروع کنید :) اگر عدد ماقبل آخر 7 است: نشانگر را به 7 منتقل کنید L. ما نمی توانیم نشانگر سمت راست را جابجا کنیم، زیرا از قبل به سمت محور اشاره می کند. 7 بزرگتر از است pivot، بنابراین یک را انجام می دهیم swap. نتیجه را بنویسید: 4 2 3 6 7. دایره 6 بزنید، زیرا این عدد است pivot. نشانگر Lاکنون به 7 و نشانگر به 3 منتقل شده است. مرتب کردن قسمت از انتها Rمنطقی نیست ، زیرا فقط 1 عنصر وجود دارد. Lبا این حال، ما قطعه را از 4 به Rنشانگر برای مرتب سازی می فرستیم. ما a را انتخاب می کنیم pivotو دوباره شروع می کنیم :) در نگاه اول، ممکن است به نظر برسد که اگر مقادیر زیادی برابر با اضافه کنید pivot، الگوریتم را خراب خواهید کرد. اما اینطور نیست. می توانید ترکیب های پیچیده ای را در نظر بگیرید و روی کاغذ خود را متقاعد کنید که همه چیز درست است و از اینکه چنین اقدامات ساده ای چنین مکانیسم مرتب سازی قابل اعتمادی را اجرا می کند شگفت زده شوید. تنها نقطه ضعف این است که این الگوریتم مرتب سازی پایدار نیست. زیرا یک مبادله ممکن است ترتیب نسبی عناصر یکسان را تغییر دهد اگر یکی از آنها قبل از اینکه pivotعنصر دیگر در قسمت قبلی مبادله شود، با یکی از آنها روبرو شده باشد pivot.

خط پایین

در بالا، ما به مجموعه ای از الگوریتم های مرتب سازی "جنتلمن" که در جاوا پیاده سازی شده اند نگاه کردیم. الگوریتم ها به طور کلی مفید هستند، هم از منظر کاربردی و هم از نظر یادگیری نحوه تفکر. برخی ساده تر، برخی پیچیده تر هستند. افراد باهوش برای برخی از پایان نامه خود دفاع کردند. برای دیگران، آنها کتاب های فوق العاده قطور نوشتند. امیدوارم مطالب تکمیلی به شما کمک کند حتی بیشتر بیاموزید، زیرا این مقاله فقط یک مرور کلی است که قبلاً سنگین شده است. و هدف آن ارائه یک مقدمه کوچک است. همچنین اگر «الگوریتم‌های گروکینگ » را بخوانید، می‌توانید مقدمه‌ای برای الگوریتم‌ها پیدا کنید . من همچنین لیست پخش جک براون را دوست دارم: AQA Decision 1 1.01 Tracing an Algorithm . برای سرگرمی، می‌توانید تجسم‌های الگوریتم را در sorting.at و visualgo.net ببینید .