Ngurutake minangka salah sawijining operasi dhasar sing ditindakake ing obyek. Malah nalika isih cilik, bocah-bocah diwulang ngurutake nalika ngembangake katrampilan mikir. Komputer lan piranti lunak ora ana sing istiméwa. Ana macem-macem algoritma ngurutake ing Jawa . Aku suggest sing mriksa metu apa lagi lan carane padha bisa. Apa yen sampeyan ditakoni babagan salah sijine ing wawancara ing sawijining dina?
Pambuka
Ngurutake unsur minangka salah sawijining kategori algoritma sing kudu dingerteni pangembang. Yen ilmu komputer biyen ora dianggep serius nalika isih sekolah, para siswa saiki kudu bisa ngetrapake lan ngerti algoritma ngurutake. Algoritma dhasar, sing paling gampang, diimplementasikake nggunakake loop for . Alami, kanggo ngurutake koleksi unsur, kayata array, sampeyan kudu ngliwati koleksi kasebut. Tuladhane:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
Apa sing bisa dikandhakake babagan segmen kode iki? Kita duwe daur ulang sing ngganti indeks ( int i) saka 0 menyang unsur pungkasan ing array. Nyatane, kita mung njupuk saben unsur ing array lan nyithak isine. Luwih akeh unsur ing array, luwih suwe kode bakal rampung. Sing, yen nnomer unsur, nalika n = 10program bakal njupuk kaping pindho luwih dawa kanggo mbukak saka nalika n = 5. Yen program kita duwe loop siji, wektu eksekusi mundhak linear: luwih akeh unsur, luwih suwe wektu eksekusi. Pranyata algoritma ing ndhuwur bisa digunakake ing wektu linear (fungsi linear n). Ing kasus kaya mengkono, kita ngomong sing kerumitan algoritma iku "O(n)". Notasi iki uga disebut "O gedhe" utawa "prilaku asimtotik". Nanging sampeyan mung bisa ngelingi"
Algoritma sorting paling gampang (bubble sort)
Upaminipun kita duwe larik lan kita bisa iterate liwat. Agung. Saiki ayo nyoba ngurutake kanthi urutan munggah. Apa tegese iki? Iku tegese diwenehi loro unsur (contone,, a = 6) b = 5, kita kudu ngatur maneh alan byen aluwih saka b(yen a > b). Apa tegese iki nalika kita nggunakake indeks kanggo nggarap koleksi (kaya ing array)? Tegese yen unsur kanthi indeks a luwih gedhe tinimbang unsur indeks b( array[a] > array[b]), mula unsur kasebut kudu diganti. Ana macem-macem cara kanggo ngganti panggonan. Nanging kita bakal nggunakake teknik sing prasaja, bisa dingerteni lan gampang dieling-eling:
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Saiki kita bisa nulis ing ngisor iki:
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));
Kaya sing sampeyan ngerteni, unsur kasebut pancen diganti. Kita miwiti karo indeks 1, amarga yen array mung nduweni siji unsur, ekspresi kasebut array[i] < array[i-1]ora sah kanggo indeks 0. Mengkono uga nglindhungi kita saka kasus ngendi Uploaded ora ana unsur utawa mung siji unsur, lan ndadekake kode katon luwih apik. Nanging array sing diasilake isih durung diurut, amarga siji pass ora cukup kanggo ngurutake. Kita kudu nambah daur ulang liyane sing bakal ditindakake bola-bali nganti entuk array sing diurutake:
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));
Dadi kita rampung algoritma ngurutake pisanan kita. Kita mbaleni loop njaba ( while) nganti kita mutusake yen ora perlu pengulangan maneh. Kanthi gawan, sadurunge saben pengulangan anyar, kita nganggep yen array kita wis diurutake lan kita ora perlu maneh. Patut, kita mindhah sequentially liwat unsur lan mriksa asumsi iki. Nanging yen unsur-unsur kasebut ora ana urutane, mula kita ganti unsur lan ngerti yen saiki ora ana jaminan manawa unsur kasebut ana ing urutan sing bener. Iki tegese kita kudu nindakake pengulangan liyane. Contone, umpamane kita duwe [3, 5, 2]. 5luwih saka 3- kabeh apik. Nanging 2kurang saka 5. Nanging, [3, 2, 5]mbutuhake pass liyane, wiwit3 > 2lan padha kudu diganti. Amarga kita nggunakake loop ing loop, kerumitan algoritma kita mundhak. Diwenehi nunsur, iku dadi n * n, sing O(n^2),. Iki diarani kompleksitas kuadrat. Umumé, kita ora bisa ngerti persis jumlah iterasi sing dibutuhake. Ekspresi kerumitan algoritma nuduhake carane kerumitan mundhak ing kasus paling awon. Yaiku, nuduhake sepira wektu eksekusi bakal saya tambah amarga jumlah unsur ndiganti. Bubble sort minangka salah sawijining algoritma pangurutan sing paling gampang lan ora efisien. Iki uga kadhangkala disebut "urutan bodho". Materi babagan topik iki:
Algoritma ngurutake liyane yaiku ngurutake pilihan. Uga nduweni kerumitan kuadrat, nanging luwih akeh mengko. Dadi gagasan iku prasaja. Ing saben pass, kita milih unsur paling cilik lan pindhah menyang wiwitan. Kajaba iku, saben pass miwiti siji langkah ing sisih tengen. Ing tembung liyane, pass pisanan diwiwiti saka unsur zeroth, pass kaloro saka pisanan, etc. Iku bakal katon kaya iki:
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));
Urut iki ora stabil, amarga unsur sing padha (ing babagan karakteristik apa wae sing digunakake kanggo ngurutake unsur) bisa ngganti posisi relatif. Conto sing apik yaiku ing artikel Wikipedia babagan pilihan . Materi babagan topik iki:
Urut sisipan uga nduweni kerumitan kuadrat, amarga kita duwe daur ulang ing daur ulang. Apa sing nggawe selipan beda? Algoritma ngurutake iki "stabil." Iki tegese unsur sing padha ora bakal ngganti urutan relatif. Maneh, tegese padha karo karakteristik sing diurutake.
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));
Urut antar-jemput
Ana algoritma ngurutake prasaja liyane: urutan antar-jemput. Iki uga dikenal minangka bidirectional bubble sort utawa cocktail shaker sort. Jeneng-jeneng alternatif iki ngandhani yen urutan pesawat ulang-alik dudu babagan pesawat ulang-alik. Iku bab soko sing obah bali lan kasebut. Saiki sampeyan bisa mikir yen sampeyan mikir babagan algoritma iki. Apa inti saka algoritma? Inti saka algoritma yaiku kita ngowahi saka kiwa menyang tengen, ngganti unsur lan mriksa manawa ana unsur sing isih ana ing arah liyane sing kudu diganti.
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));
Algoritma ngurutake prasaja liyane yaiku ngurutake cangkang. Inti saka iku padha karo ngurutake gelembung, nanging ing saben pengulangan kita duwe longkangan beda antarane unsur dibandhingake. Iki dipotong setengah karo saben pengulangan. Mangkene implementasine:
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));
Saliyane algoritma ngurutake sing prasaja iki, ana uga algoritma ngurutake sing luwih rumit. Contone, nggabung urut. Ana rong perkara sing kudu dicathet. Pisanan, rekursi teka kanggo ngluwari kita ing kene. Kapindho, kerumitan algoritma ora ana maneh kuadrat, kaya sing wis biasa. Kompleksitas algoritma iki logaritmik. Iki ditulis minangka O(n log n). Mula ayo dileksanakake. Pisanan, kita bakal nulis telpon rekursif menyang cara ngurutake:
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);
}
}
Saiki, ayo nambah tumindak utama kanggo implementasine. Mangkene metode super kita:
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);
}
Kita bisa mbukak conto kanthi nelponmergeSort(array, 0, array.length-1). Nalika sampeyan bisa ndeleng, proses boils mudhun kanggo nampa Uploaded input bebarengan karo indikasi saka wiwitan lan pungkasan bagean sing kudu diurutake. Nalika ngurutake diwiwiti, iki minangka wiwitan lan pungkasan saka array. Banjur kita ngetung delimiter, yaiku indeks ing ngendi kita bakal pamisah array. Yen array bisa dipérang dadi 2 bagean, banjur kita nelpon cara urutan rekursif kanggo loro halves saka Uploaded. Kita nyiyapake buffer tambahan ing ngendi kita bakal nglebokake bagean sing diurutake. Sabanjure, atur indeks ing wiwitan bagean sing bakal diurutake lan wiwiti mlaku liwat saben unsur saka buffer kosong, ngisi karo unsur sing paling cilik. Yen unsur nuding dening indeks kurang saka unsur nuding dening delimiter, kita sijine unsur ing buffer lan ngalih indeks. Yen ora, kita nyeleh unsur nuding dening delimiter menyang buffer lan ngalih delimiter. Sanalika delimiter ngluwihi wates bagean sing diurutake utawa kita ngisi kabeh array, sawetara sing ditemtokake dianggep diurutake.Materi babagan topik iki:
Algoritma ngurutake liyane sing menarik yaiku ngetung urut. Kompleksitas algoritmik ing kene yaiku O(n+k), ing endi njumlah unsur lan kminangka nilai maksimal saka unsur. Algoritma iki duwe siji kekurangan: kita kudu ngerti nilai minimal lan maksimal ing array. Ing ngisor iki minangka conto ngetung:
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;
}
Sampeyan bisa ngerti manawa ora trep yen kita kudu ngerti sadurunge nilai minimal lan maksimal. Lan kita duwe algoritma liyane ing kene: radix sort. Aku mung bakal nampilake algoritma ing kene kanthi visual. Waca materi tambahan kanggo implementasine: Bahan:
Ya, wektune kanggo panganan cuci mulut - ngurutake cepet, salah sawijining algoritma pangurutan sing paling misuwur. Wis kerumitan logaritma: O(n log n). Algoritma ngurutake iki dikembangake dening Tony Hoare. Sing nggumunake, dheweke nemokake nalika manggon ing Uni Soviet, ing ngendi dheweke sinau terjemahan mesin ing Universitas Moskow lan ngembangake buku frasa Rusia-Inggris. Apa maneh, Jawa nggunakake versi sing luwih rumit saka algoritma iki ing Arrays.sort. Apa bab Collections.sort? Apa ora njupuk dipikir ing carane iku diurutake "ing hood"? Iki kode:
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);
}
}
Iki kabeh medeni banget, mula ayo digali. Kanggo input array ( int[]sumber ), kita nggawe rong tandha: kiwa ( L) lan tengen ( R). Sajrone telpon cara pisanan, padha cocog karo wiwitan lan pungkasan saka Uploaded. Banjur kita ngenali unsur poros, sing dijenengi kanthi tepat pivot. Sawise iki, tugas kita yaiku mindhah nilai sing luwih cilik tinimbang pivoting sisih kiwa pivot, lan sing luwih gedhe - ing sisih tengen. Kanggo nindakake iki, kita mindhah panandha dhisik Lnganti kita nemokake nilai sing luwih gedhe tinimbang pivot. Yen ora ana nilai sing luwih cilik, banjur
L dadi padha karo
pivot. Banjur kita mindhah
Rpanandha nganti kita nemokake nilai sing luwih cilik tinimbang
pivot. Yen ora ditemokake nilai sing luwih gedhe, banjur
Rdadi padha karo
pivot. Sabanjure, yen
Lpanandha sadurunge
Rpanandha utawa pas karo, banjur kita nyoba kanggo ngganti unsur yen
Lunsur kurang saka
Runsur. Banjur kita ngalih
Lmenyang tengen kanthi 1, lan kita ngalih
Rmenyang ngiwa kanthi 1. Nalika
Lpanandha pindhah ngluwihi
Rpanandha, tegese swapping wis rampung: nilai sing luwih cilik ana ing sisih kiwa
pivot, nilai sing luwih gedhe ing sisih tengen.
pivot. Sawise iki, kita nelpon cara ngurutake padha rekursif ing subarrays - saka awal bagean bakal diurutake menyang panandha tengen, lan saka panandha kiwa menyang mburi bagean bakal diurutake. Kok saka wiwitan tekan tandha tengen? Amarga ing pungkasan iterasi, pranyata tandha tengen obah cukup kanggo dadi wates sisih kiwa. Algoritma iki luwih rumit tinimbang ngurutake prasaja, mula paling apik kanggo nggawe sketsa. Njupuk kertas putih lan tulis: 4 2 6 7 3. Banjur tulisen
pivoting tengah, yaiku ing nomer 6. Bunder. Ing 4, nulis
L, lan ing 3, nulis
R. 4 kurang saka 6, 2 kurang saka 6. Kita pungkasane pindhah
Lmenyang
pivotposisi, amarga
Lora bisa liwat.
pivot, miturut kondisi. Tulisen maneh 4 2 6 7 3. Bunder 6 (
pivot) banjur lebokake
Ling ngisore. Saiki pindhah
Rtandha. 3 kurang saka 6, supaya sijine
Rpanandha ing 3. Wiwit 3 kurang saka 6 (
pivot), kita nindakake a
swap. Tulisen asile: 4 2 3 7 6. Bunder 6, amarga isih dadi
pivot. Penanda
Ling 3.
RPenandha ing 6. Elinga yen kita mindhah tandha nganti
Lobah ngluwihi
R. Pindhah
Lmenyang nomer sabanjure. Ing kene aku pengin njelajah rong kemungkinan: 1) kasus ing ngendi nomer penultimate yaiku 7 lan 2) kasus kasebut yaiku 1, dudu 7.
Yen nomer penultimate yaiku 1: Pindhah
Ltandha menyang 1, amarga kita bisa mindhah.
Langgere ing
Lpanandha nuduhake angka sing luwih cilik tinimbang
pivot. Nanging kita ora bisa ngalih
Rsaka 6, amarga kita mung bisa mindhah R yen
Rpanandha TCTerms kanggo nomer sing luwih saka
pivot. Kita ora nindakake a
swap, amarga 1 kurang saka 6. Tulis kahanan saiki: 4 2 3 1 6. Bunder 6 (
pivot).
Lpindah
pivotlan mandheg obah.
Rora obah. Kita ora nindakake swap. Shift
Llan
Rsiji posisi. Tulisen
Rtandha ing ngisor 1.
LTandhane ora ana watese. Amarga
Lmetu saka wates, kita ora nindakake apa-apa. Nanging, kita nulis 4 2 3 1 maneh, amarga iki sisih kiwa kita, kang kurang saka
pivot(6). Pilih anyar
pivotlan miwiti kabeh maneh :)
Yen nomer penultimate 7:Pindhah
Lpanandha menyang 7. Kita ora bisa mindhah panandha tengen, amarga iku wis pointing ing poros. 7 luwih gedhe tinimbang
pivot, mula kita nindakake
swap. Tulisen asile: 4 2 3 6 7. Bunder 6, amarga iku
pivot. Penanda
Lsaiki dipindhah menyang 7, lan
Rpanandha dipindhah menyang 3. Iku ora nggawe pangertèn kanggo Ngurutake bagean saka
Lkanggo mburi, amarga ana mung 1 unsur. Nanging, kita ngirim bagean saka 4 menyang
Rpanandha kanggo ngurutake. Kita milih a
pivotlan miwiti maneh :) Ing kawitan marketing, iku uga koyone yen sampeyan nambah akèh nilai witjaksono menyang
pivot, banjur sampeyan bakal break algoritma. Nanging ora kaya ngono. Sampeyan bisa mikirake kombinasi sing angel lan ing kertas gawe uwong yakin yen kabeh iku bener lan gumun yen tumindak sing prasaja kasebut bisa ngetrapake mekanisme pangurutan sing bisa dipercaya. Siji-sijine kekurangan yaiku algoritma pangurutan iki ora stabil. Amarga swap bisa ngganti urutan relatif saka unsur identik yen salah siji saka unsur kasebut ditemoni sadurunge
pivotsadurunge unsur liyane diganti menyang bagean sadurunge
pivot.
Garis ngisor
Ndhuwur, kita ndeleng set "gentleman" saka algoritma ngurutake sing diimplementasikake ing Jawa. Algoritma umume migunani, saka sudut pandang sing diterapake lan babagan sinau babagan mikir. Sawetara luwih prasaja, sawetara luwih rumit. Wong pinter mbela disertasi kanggo sawetara. Kanggo wong liya, dheweke nulis buku super kandel. Muga-muga materi tambahan bakal mbantu sampeyan sinau luwih akeh, amarga artikel iki mung ringkesan sing wis dadi bobote. Lan tujuane kanggo nyedhiyakake introduksi cilik. Sampeyan uga bisa nemokake introduksi kanggo algoritma yen maca
"Grokking Algoritma ". Aku uga kaya dhaptar lagu saka Jack Brown:
Keputusan AQA 1 1.01 Nelusuri Algoritma . Kanggo nyenengake, sampeyan bisa ndeleng visualisasi algoritma nalika
ngurutake.visualgo.net .
GO TO FULL VERSION