Penyortiran adalah salah satu tipe dasar aktivitas atau tindakan yang dilakukan pada objek. Bahkan di masa kanak-kanak, anak diajarkan untuk memilah, mengembangkan pemikirannya. Komputer dan program juga tidak terkecuali. Ada berbagai macam algoritma. Saya sarankan Anda melihat apa itu dan cara kerjanya. Ditambah lagi, bagaimana jika suatu hari Anda ditanya tentang salah satu hal ini dalam sebuah wawancara?
Perkenalan
Pengurutan elemen adalah salah satu kategori algoritma yang harus dibiasakan oleh pengembang. Jika dulu ketika saya masih belajar ilmu komputer tidak dianggap begitu serius, sekarang di sekolah mereka harus bisa mengimplementasikan algoritma pengurutan dan memahaminya. Algoritma dasar, yang paling sederhana, diimplementasikan menggunakan loop for. Tentu saja, untuk mengurutkan kumpulan elemen, misalnya array, Anda perlu melintasi koleksi ini. Misalnya:
int[] array ={10,2,10,3,1,2,5};for(int i =0; i < array.length; i++){System.out.println(array[i]);}
Apa yang dapat Anda katakan tentang potongan kode ini? Kami memiliki loop di mana kami mengubah nilai indeks ( int i) dari 0 ke elemen terakhir dalam array. Pada dasarnya, kita hanya mengambil setiap elemen dalam array dan mencetak isinya. Semakin banyak elemen dalam array, semakin lama waktu yang dibutuhkan untuk mengeksekusi kode. Artinya, jika n adalah jumlah elemen, dengan n=10 program akan memakan waktu 2 kali lebih lama untuk dieksekusi dibandingkan dengan n=5. Ketika program kita memiliki satu loop, waktu eksekusi meningkat secara linear: semakin banyak elemen, semakin lama eksekusinya. Ternyata algoritma kode di atas berjalan dalam waktu linier (n). Dalam kasus seperti ini, “kompleksitas algoritma” dikatakan O(n). Notasi ini disebut juga "O besar" atau "perilaku asimtotik". Namun Anda cukup mengingat “kompleksitas algoritme”.
Penyortiran paling sederhana (Bubble Sort)
Jadi, kami memiliki array dan dapat mengulanginya. Besar. Sekarang mari kita coba mengurutkannya dalam urutan menaik. Apa artinya ini untuk kita? Artinya, jika ada dua elemen (misalnya, a=6, b=5), kita harus menukar a dan b jika a lebih besar dari b (jika a > b). Apa artinya ini bagi kita ketika bekerja dengan koleksi berdasarkan indeks (seperti halnya array)? Artinya jika elemen dengan indeks a lebih besar dari elemen dengan indeks b, (array[a] > array[b]), elemen tersebut harus ditukar. Pindah tempat sering disebut swap. Ada berbagai cara untuk berpindah tempat. Namun kami menggunakan kode yang sederhana, jelas dan mudah diingat:
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));
Seperti yang bisa kita lihat, unsur-unsurnya memang telah berpindah tempat. Kami memulai dengan satu elemen, karena... jika array hanya terdiri dari satu elemen, ekspresi 1 < 1 tidak akan mengembalikan nilai true dan dengan demikian kita akan melindungi diri dari kasus array dengan satu elemen atau tanpa elemen sama sekali, dan kode akan terlihat lebih baik. Tapi array terakhir kita tidak diurutkan, karena... Tidak mungkin mengurutkan semua orang sekaligus. Kita harus menambahkan loop lain di mana kita akan melakukan passing satu per satu sampai kita mendapatkan array yang diurutkan:
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));
Jadi penyortiran pertama kami berhasil. Kami mengulangi di loop luar ( while) sampai kami memutuskan bahwa tidak diperlukan iterasi lagi. Secara default, sebelum setiap iterasi baru, kita berasumsi bahwa array kita sudah diurutkan, dan kita tidak ingin melakukan iterasi lagi. Oleh karena itu, kami memeriksa elemen-elemen tersebut secara berurutan dan memeriksa asumsi ini. Namun jika elemen-elemennya tidak berurutan, kita menukar elemen-elemen tersebut dan menyadari bahwa kita tidak yakin apakah elemen-elemen tersebut berada dalam urutan yang benar. Oleh karena itu, kami ingin melakukan satu iterasi lagi. Misalnya, [3, 5, 2]. 5 lebih dari tiga, semuanya baik-baik saja. Namun 2 lebih kecil dari 5. Namun, [3, 2, 5] memerlukan satu operan lagi, karena 3 > 2 dan mereka perlu ditukar. Karena kita menggunakan loop dalam satu loop, ternyata kompleksitas algoritma kita meningkat. Dengan n elemen menjadi n * n, yaitu O(n^2). Kompleksitas ini disebut kuadrat. Seperti yang kami pahami, kami tidak dapat mengetahui secara pasti berapa banyak iterasi yang diperlukan. Indikator kompleksitas algoritme bertujuan untuk menunjukkan tren peningkatan kompleksitas, dalam kasus terburuk. Berapa peningkatan waktu berjalan ketika jumlah elemen n berubah. Bubble sort adalah salah satu jenis yang paling sederhana dan tidak efisien. Kadang-kadang juga disebut "penyortiran bodoh". Materi terkait:
Pengurutan lainnya adalah pengurutan seleksi. Ia juga memiliki kompleksitas kuadrat, tetapi akan dibahas lebih lanjut nanti. Jadi idenya sederhana. Setiap lintasan memilih elemen terkecil dan memindahkannya ke awal. Dalam hal ini, mulailah setiap lintasan baru dengan bergerak ke kanan, yaitu lintasan pertama - dari elemen pertama, lintasan kedua - dari elemen kedua. Ini akan terlihat seperti ini:
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));
Penyortiran ini tidak stabil karena elemen yang identik (dari sudut pandang karakteristik yang kita gunakan untuk mengurutkan elemen) dapat mengubah posisinya. Contoh bagus diberikan dalam artikel Wikipedia: Sorting_by-selection . Materi terkait:
Pengurutan penyisipan juga memiliki kompleksitas kuadrat, karena kita juga memiliki perulangan di dalam perulangan. Apa bedanya dengan pengurutan seleksi? Penyortiran ini "stabil". Artinya elemen yang identik tidak akan mengubah urutannya. Identik dalam hal karakteristik yang kita gunakan untuk mengurutkan.
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));
Di antara penyortiran sederhana, ada satu lagi - penyortiran ulang-alik. Tapi saya lebih suka variasi shuttle. Bagi saya, kita jarang membicarakan pesawat ulang-alik, dan pesawat ulang-alik lebih bersifat lari. Oleh karena itu, lebih mudah untuk membayangkan bagaimana pesawat ulang-alik diluncurkan ke luar angkasa. Berikut hubungannya dengan algoritma ini. Apa inti dari algoritma? Inti dari algoritme ini adalah kami melakukan iterasi dari kiri ke kanan, dan saat menukar elemen, kami memeriksa semua elemen lain yang tertinggal untuk melihat apakah pertukaran perlu diulang.
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));
Pengurutan sederhana lainnya adalah pengurutan Shell. Esensinya mirip dengan bubble sort, namun setiap iterasi kita mempunyai jarak yang berbeda antar elemen yang dibandingkan. Setiap iterasi dibelah dua. Berikut ini contoh penerapannya:
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));
Selain pengurutan sederhana yang disebutkan, ada pengurutan yang lebih kompleks. Misalnya, gabungkan sortir. Pertama, rekursi akan membantu kita. Kedua, kompleksitas kita tidak lagi bersifat kuadrat seperti dulu. Kompleksitas algoritma ini adalah logaritmik. Ditulis sebagai O(n log n). Jadi mari kita lakukan ini. Pertama, mari kita tulis panggilan rekursif ke metode pengurutan:
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);}}
Sekarang, mari tambahkan tindakan utama ke dalamnya. Berikut adalah contoh supermetode kami dengan implementasi:
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);}
Mari kita jalankan contohnya dengan memanggil mergeSort(array, 0, array.length-1). Seperti yang Anda lihat, intinya adalah kita mengambil array yang menunjukkan awal dan akhir bagian yang akan diurutkan sebagai masukan. Saat penyortiran dimulai, ini adalah awal dan akhir array. Selanjutnya kita menghitung pembatas – posisi pembagi. Jika pembagi dapat dibagi menjadi 2 bagian, maka kita memanggil pengurutan rekursif untuk bagian dimana pembagi membagi array. Kami menyiapkan array buffer tambahan di mana kami memilih bagian yang diurutkan. Selanjutnya kita letakkan kursor di awal area yang akan diurutkan dan mulai menelusuri setiap elemen array kosong yang telah kita siapkan dan mengisinya dengan elemen terkecil. Jika elemen yang ditunjuk oleh kursor lebih kecil dari elemen yang ditunjuk oleh pembagi, kita menempatkan elemen ini dalam array buffer dan memindahkan kursor. Jika tidak, kami menempatkan elemen yang ditunjuk oleh pemisah ke dalam array buffer dan memindahkan pemisah. Segera setelah pemisah melampaui batas area yang diurutkan atau kita mengisi seluruh larik, rentang yang ditentukan dianggap terurut. Materi terkait:
Algoritma pengurutan menarik lainnya adalah Counting Sort. Kompleksitas algoritmik dalam hal ini adalah O(n+k), dengan n adalah jumlah elemen, dan k adalah nilai maksimum elemen. Ada satu masalah dengan algoritma ini: kita perlu mengetahui nilai minimum dan maksimum dalam array. Berikut adalah contoh implementasi pengurutan penghitungan:
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;}
Seperti yang kita pahami, sangat merepotkan bila kita harus mengetahui terlebih dahulu nilai minimum dan maksimumnya. Dan ada algoritma lain - Radix Sort. Saya akan menyajikan algoritma di sini hanya secara visual. Untuk implementasinya lihat materi:
Nah, untuk hidangan penutup - salah satu algoritma paling terkenal: penyortiran cepat. Ini memiliki kompleksitas algoritmik, yaitu, kita memiliki O(n log n). Jenis ini disebut juga jenis Hoare. Menariknya, algoritme ini ditemukan oleh Hoare selama ia tinggal di Uni Soviet, tempat ia belajar terjemahan komputer di Universitas Moskow dan mengembangkan buku ungkapan Rusia-Inggris. Algoritma ini juga digunakan dalam implementasi yang lebih kompleks pada Arrays.sort di Java. Bagaimana dengan Koleksi.sort? Saya sarankan Anda melihat sendiri bagaimana mereka diurutkan “di balik terpal”. Jadi, kodenya:
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);}}
Segala sesuatu di sini sangat menakutkan, jadi kami akan mencari tahu. Untuk sumber array input int[], kami menetapkan dua penanda, kiri (L) dan kanan (R). Saat dipanggil untuk pertama kali, mereka cocok dengan awal dan akhir array. Selanjutnya ditentukan unsur pendukungnya alias pivot. Setelah ini, tugas kita adalah memindahkan nilai yang lebih kecil dari pivot, ke kiri pivot, dan nilai yang lebih besar ke kanan. Untuk melakukan ini, pertama-tama gerakkan penunjuk Lhingga kita menemukan nilai yang lebih besar dari pivot. Jika nilai yang lebih kecil tidak ditemukan, maka
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