מיון הוא אחד מהסוגים הבסיסיים של פעילויות או פעולות המבוצעות על אובייקטים. אפילו בילדות מלמדים ילדים למיין, לפתח את החשיבה שלהם. גם מחשבים ותוכנות אינם יוצאי דופן. יש מגוון עצום של אלגוריתמים. אני מציע לך לבדוק מה הם ואיך הם עובדים. בנוסף, מה אם יום אחד ישאלו אותך על אחד כזה בראיון?
מבוא
רכיבי מיון היא אחת מקטגוריות האלגוריתמים שמפתח חייב להתרגל אליהן. אם פעם, כשלמדתי, מדעי המחשב לא לקחו כל כך ברצינות, עכשיו בבית הספר הם צריכים להיות מסוגלים ליישם אלגוריתמי מיון ולהבין אותם. אלגוריתמים בסיסיים, הפשוטים שבהם, מיושמים באמצעות לולאה 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). סימון זה נקרא גם "Big O" או "התנהגות אסימפטוטית". אבל אתה יכול פשוט לזכור את "מורכבות האלגוריתם".
המיון הפשוט ביותר (Bubble Sort)
אז יש לנו מערך ויכולים לחזור עליו. גדול. כעת ננסה למיין אותו בסדר עולה. מה זה אומר עבורנו? המשמעות היא שבהינתן שני אלמנטים (לדוגמה, a=6, b=5), עלינו להחליף את a ו-b אם a גדול מ-b (אם a > b). מה זה אומר עלינו כשעובדים עם אוסף לפי אינדקס (כמו שקורה עם מערך)? זה אומר שאם האלמנט עם האינדקס a גדול מהאלמנט עם האינדקס b, (מערך[a] > מערך[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 לא יחזיר אמת וכך נגן על עצמנו ממקרים של מערך עם אלמנט אחד או בלעדיהם בכלל, והקוד ייראה טוב יותר. אבל המערך הסופי שלנו לא מסודר בכל מקרה, כי... לא ניתן למיין את כולם במעבר אחד. נצטרך להוסיף לולאה נוספת בה נבצע מעברים אחד אחד עד שנקבל מערך ממוין:
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));
מיון זה אינו יציב, כי אלמנטים זהים (מנקודת המבט של המאפיין שלפיו אנו ממיינים את האלמנטים) יכולים לשנות את מיקומם. דוגמה טובה ניתנת במאמר בויקיפדיה: מיון_לפי בחירה . חומר קשור:
למיון ההכנסה יש גם מורכבות ריבועית, מכיוון ששוב יש לנו לולאה בתוך לולאה. במה זה שונה ממיון בחירה? המיון הזה הוא "יציב". המשמעות היא שאלמנטים זהים לא ישנו את הסדר שלהם. זהה מבחינת המאפיינים שלפיהם אנחנו ממיינים.
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));
בנוסף למיונים הפשוטים שצוינו, ישנם מיונים מורכבים יותר. לדוגמה, מיזוג מיון. ראשית, הרקורסיה תבוא לעזרתנו. שנית, המורכבות שלנו כבר לא תהיה ריבועית, כפי שהורגלנו. המורכבות של אלגוריתם זה היא לוגריתמית. נכתב כ-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. מעניין לציין שהאלגוריתם הומצא על ידי הואר במהלך שהותו בברית המועצות, שם למד תרגום מחשבים באוניברסיטת מוסקבה ופיתח שיחון רוסית-אנגלית. אלגוריתם זה משמש גם ביישום מורכב יותר ב-Arrays.sort ב-Java. מה לגבי 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). כאשר קוראים להם בפעם הראשונה, הם תואמים את ההתחלה והסוף של המערך. לאחר מכן, האלמנט התומך נקבע, aka 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