مرتب سازی یکی از انواع اساسی فعالیت ها یا اعمالی است که بر روی اشیا انجام می شود. حتی در دوران کودکی به کودکان آموزش داده می شود که مرتب سازی کنند و تفکر خود را توسعه دهند. رایانه ها و برنامه ها نیز از این قاعده مستثنی نیستند. الگوریتم های بسیار متنوعی وجود دارد. من به شما پیشنهاد می کنم ببینید چه هستند و چگونه کار می کنند. بعلاوه، اگر روزی در مصاحبه ای در مورد یکی از این موارد از شما سوال شود، چه؟
معرفی
مرتب سازی عناصر یکی از دسته الگوریتم هایی است که یک توسعه دهنده باید به آن عادت کند. اگر روزگاری، زمانی که من درس می خواندم، علم کامپیوتر را چندان جدی نمی گرفتند، حالا در مدرسه باید بتوانند الگوریتم های مرتب سازی را پیاده سازی کنند و آنها را درک کنند. الگوریتم های پایه، ساده ترین آنها، با استفاده از یک حلقه پیاده سازی می شوند 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 اجرای برنامه 2 برابر بیشتر از n=5 طول می کشد. وقتی برنامه ما یک حلقه داشته باشد، زمان اجرا به صورت خطی افزایش می یابد: هر چه تعداد عناصر بیشتر باشد، اجرا طولانی تر می شود. معلوم می شود که الگوریتم کد بالا در زمان خطی (n) کار می کند. در چنین مواردی، "پیچیدگی الگوریتم" O(n) گفته می شود. به این نماد "O بزرگ" یا "رفتار مجانبی" نیز می گویند. اما شما می توانید به سادگی "پیچیدگی الگوریتم" را به خاطر بسپارید.
ساده ترین مرتب سازی (مرتب سازی حباب)
بنابراین، ما یک آرایه داریم و می توانیم روی آن تکرار کنیم. عالی. حالا بیایید سعی کنیم آن را به ترتیب صعودی مرتب کنیم. معنی این برای ما چیست؟ این بدان معناست که با توجه به دو عنصر (مثلاً a=6، b=5)، اگر a بزرگتر از b باشد (اگر a > b) باید a و b را با هم عوض کنیم. این برای ما هنگام کار با مجموعه بر اساس شاخص (مانند آرایه) چه معنایی دارد؟ این بدان معنی است که اگر عنصر با شاخص a بزرگتر از عنصر با شاخص b باشد (array[a] > array[b])، چنین عناصری باید تعویض شوند. تغییر مکان را اغلب تعویض می گویند. روش های مختلفی برای تغییر مکان وجود دارد. اما ما از کدهای ساده، واضح و آسان برای به خاطر سپردن استفاده می کنیم:
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 < 1 true برنمی گردد و بنابراین ما خود را از مواردی که یک آرایه با یک عنصر یا اصلاً بدون آنها وجود دارد محافظت می کنیم و کد بهتر به نظر می رسد. اما آرایه نهایی ما به هر حال مرتب نشده است، زیرا ... نمی توان همه را در یک گذر مرتب کرد. ما باید یک حلقه دیگر اضافه کنیم که در آن پاس ها را یکی یکی انجام می دهیم تا زمانی که یک آرایه مرتب شده به دست آوریم:
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 بیشتر از سه است، همه چیز خوب است. اما 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));
این مرتب سازی ناپایدار است، زیرا عناصر یکسان (از نقطه نظر مشخصه ای که عناصر را بر اساس آن مرتب می کنیم) می توانند موقعیت خود را تغییر دهند. یک مثال خوب در مقاله ویکی پدیا آورده شده است: Sorting_by-selection . مطالب مرتبط:
مرتب‌سازی درج نیز پیچیدگی درجه دوم دارد، زیرا ما دوباره یک حلقه در یک حلقه داریم. چه تفاوتی با مرتب سازی انتخابی دارد؟ این مرتب سازی "پایدار" است. این بدان معنی است که عناصر یکسان ترتیب خود را تغییر نمی دهند. از نظر ویژگی هایی که بر اساس آنها مرتب می کنیم یکسان است.
int[] array ={10,2,10,3,1,2,5};System.out.println(Arrays.toString(array));for(int left =0; left < array.length; left++){// Retrieve the value of the elementint value = array[left];// Move through the elements that are before the pulled elementint i = left -1;for(; i >=0; i--){// If a smaller value is pulled out, move the larger element furtherif(value < array[i]){
array[i +1]= array[i];}else{// If the pulled element is larger, stopbreak;}}// Insert the extracted value into the freed 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 elementsint gap = array.length /2;// As long as there is a difference between the elementswhile(gap >=1){for(int right =0; right < array.length; right++){// Shift the right pointer until we can find one that// there won't be enough space between it and the element before itfor(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));
علاوه بر انواع ساده نشان داده شده، انواع پیچیده تری نیز وجود دارد. به عنوان مثال، merge sort. اول، بازگشت به کمک ما خواهد آمد. ثانیاً، پیچیدگی ما دیگر آنطور که عادت کرده ایم درجه دوم نخواهد بود. پیچیدگی این الگوریتم لگاریتمی است. به صورت O(n log n) نوشته شده است. پس بیایید این کار را انجام دهیم. ابتدا بیایید یک فراخوان بازگشتی به روش مرتب سازی بنویسیم:
publicstaticvoidmergeSort(int[] source,int left,int right){// Choose a separator, i.e. split the input array in halfint delimiter = left +((right - left)/2)+1;// Execute this function recursively for the two halves (if we can split(if(delimiter >0&& right >(left +1)){mergeSort(source, left, delimiter -1);mergeSort(source, delimiter, right);}}
حالا بیایید یک اکشن اصلی به آن اضافه کنیم. در اینجا یک نمونه از ابر روش ما با پیاده سازی است:
publicstaticvoidmergeSort(int[] source,int left,int right){// Choose a separator, i.e. split the input array in halfint delimiter = left +((right - left)/2)+1;// Execute this function recursively for the two halves (if we can split(if(delimiter >0&& right >(left +1)){mergeSort(source, left, delimiter -1);mergeSort(source, delimiter, right);}// Create a temporary array with the desired sizeint[] buffer =newint[right - left +1];// Starting from the specified left border, go through each elementint cursor = left;for(int i =0; i < buffer.length; i++){// We use the delimeter to point to the element from the right side// If delimeter > right, then there are no unadded elements left on the right sideif(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 قسمت تقسیم شود، برای بخش هایی که تقسیم کننده آرایه را به آنها تقسیم کرده است، مرتب سازی بازگشتی می نامیم. یک آرایه بافر اضافی آماده می کنیم که در آن قسمت مرتب شده را انتخاب می کنیم. در مرحله بعد، مکان نما را در ابتدای ناحیه مورد نظر قرار می دهیم و شروع می کنیم به مرور هر عنصر از آرایه خالی که آماده کرده ایم و آن را با کوچکترین عناصر پر می کنیم. اگر عنصری که مکان نما به آن اشاره می کند کوچکتر از عنصری باشد که مقسوم علیه به آن اشاره می کند، این عنصر را در آرایه بافر قرار می دهیم و مکان نما را حرکت می دهیم. در غیر این صورت، عنصری را که جداکننده به آن اشاره می کند، در آرایه بافر قرار می دهیم و جداکننده را حرکت می دهیم. به محض اینکه جداکننده از مرزهای منطقه مرتب شده فراتر رفت یا کل آرایه را پر کنیم، محدوده مشخص شده مرتب شده در نظر گرفته می شود. مطالب مرتبط:
یکی دیگر از الگوریتم های مرتب سازی جالب Counting Sort است. پیچیدگی الگوریتمی در این حالت O(n+k) خواهد بود، که در آن n تعداد عناصر و k حداکثر مقدار عنصر است. یک مشکل با الگوریتم وجود دارد: ما باید حداقل و حداکثر مقادیر را در آرایه بدانیم. در اینجا نمونه ای از اجرای مرتب سازی شمارش است:
publicstaticint[]countingSort(int[] theArray,int maxValue){// Array with "counters" ranging from 0 to the maximum valueint numCounts[]=newint[maxValue +1];// In the corresponding cell (index = value) we increase the counterfor(int num : theArray){
numCounts[num]++;}// Prepare array for sorted resultint[] sortedArray =newint[theArray.length];int currentSortedIndex =0;// go through the array with "counters"for(int n =0; n < numCounts.length; n++){int count = numCounts[n];// go by the number of valuesfor(int k =0; k < count; k++){
sortedArray[currentSortedIndex]= n;
currentSortedIndex++;}}return sortedArray;}
همانطور که می‌دانیم، زمانی که باید حداقل و حداکثر مقادیر را از قبل بدانیم، بسیار ناخوشایند است. و سپس الگوریتم دیگری وجود دارد - Radix Sort. من الگوریتم را در اینجا فقط به صورت بصری ارائه خواهم کرد. برای اجرا، به مواد مراجعه کنید:
خوب، برای دسر - یکی از معروف ترین الگوریتم ها: مرتب سازی سریع. پیچیدگی الگوریتمی دارد، یعنی O(n log n) داریم. به این نوع مرتب سازی Hoare نیز می گویند. جالب اینجاست که این الگوریتم توسط Hoare در زمان اقامتش در اتحاد جماهیر شوروی اختراع شد، جایی که او در دانشگاه مسکو مترجم کامپیوتری خواند و در حال توسعه یک کتاب عبارات روسی-انگلیسی بود. این الگوریتم در پیاده سازی پیچیده تر در Arrays.sort در جاوا نیز استفاده می شود. در مورد Collections.sort چطور؟ پیشنهاد می کنم خودتان ببینید که چگونه آنها را "زیر کاپوت" طبقه بندی می کنند. بنابراین، کد:
publicstaticvoidquickSort(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 while element is less than pivotwhile(source[leftMarker]< pivot){
leftMarker++;}// Move the right marker until element is greater than pivotwhile(source[rightMarker]> pivot){
rightMarker--;}// Check if you don't need to swap elements pointed to by markersif(leftMarker <= rightMarker){// The left marker will only be less than the right marker if we have to swapif(leftMarker < rightMarker){int tmp = source[leftMarker];
source[leftMarker]= source[rightMarker];
source[rightMarker]= tmp;}// Move markers to get new borders
leftMarker++;
rightMarker--;}}while(leftMarker <= rightMarker);// Execute recursively for partsif(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 meaning. Если меньшее meaning не нашли, то
R совпадёт с
pivot. Далее, если указатель
L находится до указателя
R or совпадает с ним, то пытаемся выполнить обмен элементов, если элемент
L меньше, чем
R. Далее
L сдвигаем вправо на 1 позицию,
R сдвигаем влево на одну позицию. Когда левый маркер
L окажется за правым маркером
R это будет означать, что обмен закончен, слева от
pivot меньшие значения, справа от
pivot — большие значения. После этого рекурсивно вызываем такую же сортировку для участков массива от начала сортируемого участка до правого маркера и от левого маркера до конца сортируемого участка. Почему от начала до правого? Потому что в конце итерации так и получится, что правый маркер сдвинется настолько, что станет границей части слева. Этот алгоритм более сложный, чем простая sorting, поэтому его лучше зарисовать. Возьмём белый лист бумаги, запишем: 4 2 6 7 3 , а
Pivot по центру, т.е. число 6. Обведём его в круг. Под 4 напишем
L, под 3 напишем
R. 4 меньше чем 6, 2 меньше чем 6. Total,
L переместился на положение
pivot, т.к. по условию
L не может уйти дальше, чем
pivot. Напишем снова 4 2 6 7 3 , обведём 6 вкруг (
pivot) и поставим под ним
L. Теперь двигаем указатель
R. 3 меньше чем 6, поэтому ставим маркер
R на цифру 3. Так How 3 меньше, чем
pivot 6 выполняем
swap, т.е. обмен. Запишем результат: 4 2 3 7 6 , обводим 6 вкруг, т.к. он по прежнему
pivot. Указатель
L на цифре 3, указатель
R на цифре 6. Мы помним, что двигаем указатели до тех пор, пока
L не зайдём за
R.
L двигаем на следующую цифру. Тут хочется разобрать два варианта: если бы предпоследняя цифра была 7 и если бы она была не 7, а 1.
Предпоследня цифра 1: Сдвинули указатель
L на цифру 1, т.к. мы можем двигать
L до тех пор, пока указатель
L указывает на цифру, меньшую чем
pivot. А вот
R мы не можем сдвинуть с 6, т.к. R не мы можем двигать только если указатель
R указывает на цифру, которая больше чем
pivot.
swap не делаем, т.к. 1 меньше 6. Записываем положение: 4 2 3 1 6, обводим
pivot 6.
L сдвигается на
pivot и больше не двигается.
R тоже не двигается. Обмен не производим. Сдвигаем
L и
R на одну позицию и подписываем цифру 1 маркером
R, а
L получается вне числа. Т.к.
L вне числа — ничего не делаем, а вот часть 4 2 3 1 выписываем снова, т.к. это наша левая часть, меньшая, чем
pivot 6. Выделяем новый
pivot и начинаем всё снова )
Предпоследняя цифра 7: Сдвинули указать
L на цифру 7, правый указатель не можем двигать, т.к. он уже указывает на pivot. т.к. 7 больше, чем
pivot, то делаем
swap. Запишем результат: 4 2 3 6 7, обводим 6 кружком, т.к. он
pivot. Указатель
L теперь сдвигается на цифру 7, а указатель
R сдвигается на цифру 3. Часть от
L до конца нет смысла сортировать, т.к. там всего 1 элемент, а вот часть от 4 до указателя
R отправляем на сортировку. Выбираем
pivot и начинаем всё снова ) Может на первый взгляд показаться, что если расставить много одинаковых с
pivot значений, это сломает алгоритм, но это не так. Можно напридумывать каверзных вариантов и на бумажке убедиться, что всё правильно и подивиться, How такие простые действия предоставляют такой надёжный механизм. Единственный минус — такая sorting не является стабильной. Т.к. при выполнении обмена одинаковые элементы могут поменять свой порядок, если один из них встретился до
pivot до того, How другой элемент попал в часть до
pivot при помощи обмена. Материал:
Выше мы рассмотрели "джентельменский" набор алгоритмов сортировки, реализованных на Java. Алгоритмы вообще штука полезная, How с прикладной точки зрения, так и с точки зрения развития мышления. Некоторые из них попроще, некоторые посложнее. По Howим-то умные люди защищали различные работы на степени, а по другим писали толстые-толстые книги. Надеюсь, приложенный к статье материал позволит вам узнать ещё больше, так How это обзорная статья, которая и так получилась увесистой. И цель её — дать небольшое вступление. Про введение в алгоритмы можно так же прочитать ознакомиться с книгой "
Грокаем Алгоримы". Также мне нравится плэйлист от Jack Brown —
AQA Decision 1 1.01 Tracing an Algorithm. Ради интереса можно посмотреть на визуализацию алгоритмов на
sorting.at и
visualgo.net. Ну и весь Youtube к вашим услугам.
GO TO FULL VERSION