Sıralama, nesneler üzerinde gerçekleştirdiğimiz temel işlemlerden biridir. Çocuklukta bile, çocuklara düşünme becerilerini geliştirirken sıralama yapmaları öğretilir. Bilgisayarlar ve yazılımlar istisna değildir. Java'da çok çeşitli sıralama algoritmaları vardır . Ne olduklarını ve nasıl çalıştıklarını kontrol etmenizi öneririm. Ya bir gün bir röportajda onlardan biri sorulursa?
giriiş
Öğeleri sıralama, bir geliştiricinin bilmesi gereken algoritma kategorilerinden biridir. Ben okuldayken bilgisayar bilimi bir zamanlar ciddiye alınmadıysa, bugünün öğrencileri sıralama algoritmalarını uygulayabilmeli ve anlayabilmelidir. Temel algoritmalar, en basitleri, bir for döngüsü kullanılarak uygulanır . Doğal olarak, bir dizi gibi bir öğe koleksiyonunu sıralamak için, bir şekilde koleksiyonu gözden geçirmeniz gerekir. Örneğin:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
Bu kod parçası hakkında ne söylenebilir? int iDizinin son elemanı olan 0'dan indeksi ( ) değiştirdiğimiz bir döngümüz var . Aslında, dizideki her elemanı alıp içeriğini yazdırıyoruz. Dizide ne kadar çok öğe varsa, kodun bitmesi o kadar uzun sürer. Yani, if , programın ne zaman çalıştırılacağına göre iki kat daha uzun süreceği nöğe sayısıdır . Programımızın tek bir döngüsü varsa, yürütme süresi doğrusal olarak artar: ne kadar çok öğe varsa, yürütme süresi o kadar uzun olur. Yukarıdaki algoritmanın doğrusal zamanda (n'nin doğrusal bir fonksiyonu) çalıştığı ortaya çıktı. Bu gibi durumlarda, algoritmanın karmaşıklığının "O(n)" olduğunu söylüyoruz. Bu gösterim aynı zamanda "büyük O" veya "asimptotik davranış" olarak da adlandırılır. Ama sadece hatırlayabilirsin " n = 10n = 5
En basit sıralama algoritması (kabarcık sıralama)
Diyelim ki bir dizimiz var ve onu yineleyebiliriz. Harika. Şimdi artan düzende sıralamaya çalışalım. Bu ne anlama gelir? Bu, verilen iki öğeyi (örneğin, a = 6, b = 5) yeniden düzenlememiz gerektiği ave bif'in (if )' aden büyük olduğu anlamına gelir . Bir koleksiyonla çalışmak için bir dizin kullandığımızda (dizide olduğu gibi) bu ne anlama gelir? Bu, a indeksine sahip eleman, indekse ( ) sahip elemandan daha büyükse , elemanların yer değiştirmesi gerektiği anlamına gelir. Yer değiştirmenin farklı yolları vardır. Ancak basit, anlaşılır ve hatırlaması kolay bir teknik kullanacağız: ba > bbarray[a] > array[b]
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Şimdi aşağıdakileri yazabiliriz:
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));
Gördüğünüz gibi, öğeler gerçekten değiştirildi. İndeks 1 ile başladık, çünkü dizinin sadece bir elemanı varsa, array[i] < array[i-1]indeks için ifade geçersizdir 0. Bunu yapmak aynı zamanda bizi dizinin hiç elemanının olmadığı veya sadece bir elemanının olduğu durumlardan korur ve kodun daha iyi görünmesini sağlar. Ancak ortaya çıkan dizi hala sıralanmamıştır, çünkü sıralama yapmak için bir geçiş yeterli değildir. Sıralanmış bir dizi elde edene kadar geçişleri tekrar tekrar gerçekleştireceğimiz başka bir döngü eklememiz gerekecek:
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));
Böylece ilk sıralama algoritmamızı bitirdik. whileDaha fazla iterasyona gerek olmadığına karar verene kadar dış döngüyü ( ) tekrarlıyoruz . Varsayılan olarak, her yeni yinelemeden önce, dizimizin sıralandığını ve artık döngüye ihtiyacımız olmadığını varsayıyoruz. Buna göre, öğeler arasında sırayla hareket ediyoruz ve bu varsayımı kontrol ediyoruz. Ancak öğeler sıralı değilse, öğeleri değiştiririz ve artık öğelerin doğru sırada olduğuna dair hiçbir garantimiz olmadığını anlarız. Bu, başka bir yineleme gerçekleştirmemiz gerektiği anlamına gelir. Örneğin, sahip olduğumuzu varsayalım [3, 5, 2]. 5daha fazlası 3- her şey yolunda. Ama 2daha azdır 5. Ancak, [3, 2, 5]başka bir geçiş gerektirir, çünkü3 > 2ve değiştirilmeleri gerekir. Döngü içinde döngü kullandığımız için algoritmamızın karmaşıklığı artar. nÖğeler verildiğinde, , n * nyani O(n^2). Buna ikinci dereceden karmaşıklık denir. Genel olarak, tam olarak kaç yinelemeye ihtiyaç duyulacağını bilemeyiz. Bir algoritmanın karmaşıklık ifadesi, en kötü durumda karmaşıklığın nasıl arttığını gösterir. Yani eleman sayısı değiştikçe yürütme süresinin ne kadar artacağını gösterir n. Kabarcık sıralama, en basit ve en verimsiz sıralama algoritmalarından biridir. Ayrıca bazen "aptal sıralama" olarak da adlandırılır. Bu konuyla ilgili materyal:
Diğer bir sıralama algoritması ise seçim sıralamasıdır. Aynı zamanda ikinci dereceden bir karmaşıklığa sahiptir, ancak daha sonra buna daha fazla değineceğiz. Yani fikir basit. Her geçişte en küçük öğeyi seçip başa kaydırıyoruz. Ek olarak, her geçiş bir adım sağa doğru başlar. Başka bir deyişle, ilk geçiş sıfırıncı elemandan başlar, ikinci geçiş birinciden vb. Şuna benzer:
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));
Bu sıralama kararsızdır, çünkü özdeş öğeler (öğeleri sıralamak için kullandığımız karakteristik açısından) göreli konumlarını değiştirebilir. Seçim sıralamasıyla ilgili Wikipedia makalesinde iyi bir örnek var . Bu konuyla ilgili materyal:
Ekleme sıralaması ayrıca ikinci dereceden karmaşıklığa sahiptir, çünkü yine bir döngü içinde bir döngümüz vardır. Ekleme sıralamasını farklı kılan nedir? Bu sıralama algoritması "kararlıdır". Bu, aynı öğelerin göreli sıralarını değiştirmeyeceği anlamına gelir. Yine sıralama yaptığımız özellikler açısından özdeş demek istiyoruz.
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));
Mekik sıralaması
Başka bir basit sıralama algoritması daha var: mekik sıralama. Bu aynı zamanda çift yönlü balon sıralaması veya kokteyl çalkalayıcı sıralaması olarak da bilinir. Bu alternatif isimler bize mekik türünün uzay mekiği ile ilgili olmadığını söylüyor. İleri geri hareket eden bir şey hakkında. Şimdi bu algoritmayı düşündüğünüzde bunu düşünebilirsiniz. Algoritmanın özü nedir? Algoritmanın özü, öğeleri değiştirerek ve diğer yönde kalan öğelerden herhangi birinin değiştirilmesi gerekip gerekmediğini kontrol ederek soldan sağa yinelememizdir.
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));
Bir başka basit sıralama algoritması da kabuk sıralamadır. Bunun özü kabarcık sıralamaya benzer, ancak her yinelemede karşılaştırılan öğeler arasında farklı bir boşluk vardır. Her yinelemede ikiye bölünür. İşte bir uygulama:
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));
Bu basit sıralama algoritmalarına ek olarak, daha karmaşık sıralama algoritmaları da vardır. Örneğin, birleştirme sıralaması. Dikkat edilmesi gereken iki şey var. İlk olarak, özyineleme burada imdadımıza yetişir. İkincisi, algoritmanın karmaşıklığı artık alıştığımız gibi ikinci dereceden değil. Bu algoritmanın karmaşıklığı logaritmiktir. Bu olarak yazılır O(n log n). Öyleyse uygulayalım. İlk olarak, sort yöntemine özyinelemeli bir çağrı yazacağız:
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);
}
}
Şimdi uygulamamıza main action'ı ekleyelim. İşte süper yöntemimiz:
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);
}
Örneğimizi çağırarak çalıştırabiliriz.mergeSort(array, 0, array.length-1). Gördüğünüz gibi, süreç, sıralanması gereken bölümün başlangıç ve bitiş göstergeleriyle birlikte bir girdi dizisini kabul etmeye indirgenir. Sıralama başladığında, bunlar dizinin başı ve sonudur. Ardından diziyi böleceğimiz indeks olan ayırıcıyı hesaplıyoruz. Dizi 2 parçaya bölünebiliyorsa, dizinin iki yarısı için yinelemeli olarak sort yöntemini çağırırız. Sıralanmış bölümü ekleyeceğimiz bir yardımcı tampon hazırlıyoruz. Ardından, sıralanacak bölümün başında dizini ayarlayın ve boş arabelleğin her bir öğesinde yürümeye başlayın ve onu en küçük öğelerle doldurun. Dizinin işaret ettiği öğe, sınırlayıcının gösterdiği öğeden küçükse, öğeyi tampona koyar ve dizini kaydırırız. Aksi takdirde, sınırlayıcı tarafından işaret edilen öğeyi arabelleğe yerleştirir ve sınırlayıcıyı kaydırırız. Sınırlayıcı, sıralanan bölümün sınırlarının dışına çıktığı anda veya tüm diziyi doldurduğumuzda, belirtilen aralık sıralanmış olarak kabul edilir.Bu konuyla ilgili materyal:
Bir başka ilginç sıralama algoritması da sayma sıralamasıdır. Buradaki algoritmik karmaşıklık O(n+k), neleman sayısı ve kbir elemanın maksimum değeridir. Bu algoritmanın bir eksikliği var: dizideki minimum ve maksimum değerleri bilmemiz gerekiyor. İşte sayma sıralamasına bir örnek:
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;
}
Minimum ve maksimum değerleri önceden bilmemiz gerektiğinde bunun çok sakıncalı olduğunu anlayabilirsiniz. Ve burada başka bir algoritmamız daha var: sayı tabanı sıralaması. Algoritmayı burada sadece görsel olarak sunacağım. Uygulama için ek materyallere bakınız: Malzemeler:
Pekala, tatlı zamanı - en ünlü sıralama algoritmalarından biri olan hızlı sıralama. Logaritmik karmaşıklığı vardır: O(n log n). Bu sıralama algoritması Tony Hoare tarafından geliştirilmiştir. İlginç bir şekilde, bunu Moskova Üniversitesi'nde makine çevirisi eğitimi aldığı ve Rusça-İngilizce bir konuşma kılavuzu geliştirdiği Sovyetler Birliği'nde yaşarken icat etti. Dahası, Java bu algoritmanın daha karmaşık bir sürümünü Arrays.sort. Peki ya Collections.sort? İşlerin "başlık altında" nasıl sıralandığına neden bir göz atmıyorsunuz? İşte kod:
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);
}
}
Bunların hepsi çok korkutucu şeyler, o yüzden derine inelim. Giriş dizisi ( int[]kaynak ) için iki işaretçi oluşturuyoruz: sol ( L) ve sağ ( R). İlk yöntem çağrısı sırasında, dizinin başına ve sonuna karşılık gelirler. Ardından, uygun bir şekilde adlandırılan pivot öğesini tanımlarız pivot. pivotBundan sonra görevimiz, solundan daha küçük değerleri pivotve daha büyükleri - sağa taşımaktır . LBunu yapmak için önce işaretçiyi değerinden büyük bir değer bulana kadar hareket ettiririz pivot. Daha küçük bir değer bulunmazsa, o zaman
L eşit olur
pivot.
RArdından , değerinden daha küçük bir değer bulana kadar işaretçiyi hareket ettiririz
pivot. Daha büyük bir değer bulunmazsa, o zaman
Reşit olur
pivot. Ardından,
Lişaretçi işaretçiden önceyse veya onunla çakışıyorsa, eleman elemandan küçükse
Relemanları değiştirmeye çalışırız . Sonra 1 sağa kaydırıyoruz ve 1 sola kaydırıyoruz. İşaretçi işaretçinin ötesine geçtiğinde , bu takasın tamamlandığı anlamına gelir: daha küçük değerler , öğesinin solunda , daha büyük değerler sağındadır.
LRLRLRpivotpivot. Bundan sonra, sıralanacak bölümün başından sağ işaretçiye ve sol işaretçiden sıralanacak bölümün sonuna kadar aynı sıralama yöntemini alt diziler üzerinde yinelemeli olarak çağırıyoruz. Neden baştan doğru işaretleyiciye? Çünkü bir iterasyon sonunda sağ işaretçinin sol kısmın sınırı olacak kadar hareket ettiği ortaya çıkıyor. Bu algoritma, basit sıralamadan daha karmaşıktır, bu yüzden onu çizmek en iyisidir. Beyaz bir kağıt alın ve şunu yazın: 4 2 6 7 3. Sonra
pivotortasına, yani 6 rakamının altına yazın. Yuvarlak içine alın. 4'ün altına yazın
Lve 3'ün altına yazın
R.
L4, 6'dan az, 2, 6'dan az. Pozisyona geçiyoruz
pivotçünkü
Lgeçemiyoruz.
pivot, duruma göre. Tekrar 4 2 6 7 3 yazın. 6'yı (
pivot) daire içine alın ve
Laltına koyun. Şimdi
Rişaretçiyi hareket ettirin. 3, 6'dan küçüktür, bu nedenle
Rişaretçiyi 3'ün üzerine koyun. 3, 6'dan (
pivot) küçük olduğu için a yaparız
swap. Sonucu yazın: 4 2 3 7 6. 6'yı daire içine alın çünkü hala
pivot. İşaretçi
L3'te.
Rİşaretçi 6'da. İşaretçileri 'nin
Lötesine geçene kadar hareket ettirdiğimizi unutmayın
R.
LBir sonraki numaraya geçin . Burada iki olasılığı araştırmak istiyorum: 1) sondan bir önceki sayının 7 olduğu durum ve 2) 7 değil, 1 olduğu durum. Sondan bir
önceki sayı 1 ise: İşaretçiyi 1'e getirin
L, çünkü hareket edebiliriz
Lsürece
Lişaretinden daha küçük bir sayıyı işaret eder
pivot.
RAncak 6'dan uzaklaşamayız çünkü R'yi ancak işaretçi
R'den büyük bir sayıyı gösteriyorsa hareket ettirebiliriz
pivot. a yapmıyoruz
swapçünkü 1, 6'dan küçüktür. Şu anki durumu yazınız: 4 2 3 1 6. Daire 6 (
pivot).
Lgeçer
pivotve hareket etmeyi durdurur.
Rhareket etmiyor Takas yapmıyoruz. Kaydırma
Lve
Rbir pozisyona göre.
Rİşaretçiyi 1'in altına yazın.
Lİşaretçi sınırların dışında. Çünkü
Lsınırların dışında, hiçbir şey yapmıyoruz.
pivotAma yine 4 2 3 1 yazarız, çünkü bu bizim (6)' dan küçük olan sol tarafımızdır . Yeniyi seçin
pivotve her şeye yeniden başlayın :)
Sondan bir önceki sayı 7 ise:İşaretçiyi 7'ye getirin
L. Sağ işaretçiyi hareket ettiremiyoruz çünkü o zaten pivotu işaret ediyor. 7 büyüktür
pivot, bu yüzden a yaparız
swap. Sonucu yazın: 4 2 3 6 7. 6'yı yuvarlak içine alın çünkü
pivot. İşaretçi
Lşimdi 7'ye kaydırıldı ve işaretçi 3'e kaydırıldı . Parçayı baştan sona
Rsıralamak mantıklı değil çünkü sadece 1 eleman var. Ancak 4'ten olan kısmı sıralama için işaretçiye
Lgönderiyoruz .
Ra'yı seçip
pivotbaştan başlıyoruz :) İlk bakışta şuna eşit bir sürü değer eklerseniz öyle görünebilir.
pivot, o zaman algoritmayı bozarsınız. Ama durum böyle değil. Zor kombinasyonlar düşünebilir ve kağıt üzerinde kendinizi her şeyin doğru olduğuna ikna edebilir ve bu kadar basit eylemlerin bu kadar güvenilir bir sıralama mekanizması uyguladığına hayret edebilirsiniz. Tek dezavantajı, bu sıralama algoritmasının kararlı olmamasıdır. Çünkü bir takas, özdeş elemanların göreceli sırasını değiştirebilir, eğer bunlardan biriyle daha önce karşılaşılırsa,
pivotdiğer eleman önceki parçaya takas edilir
pivot.
Alt çizgi
Yukarıda, Java'da uygulanan bir "centilmen" sıralama algoritmaları setine baktık. Algoritmalar genellikle hem uygulamalı bir bakış açısından hem de nasıl düşünüleceğini öğrenmek açısından faydalıdır. Bazıları daha basit, bazıları daha karmaşık. Bazıları için akıllı insanlar tezlerini savundu. Diğerleri için süper kalın kitaplar yazdılar. Umarım ek materyaller daha fazla öğrenmenize yardımcı olur, çünkü bu makale zaten önemli olduğu ortaya çıkan bir genel bakıştır. Ve amacı küçük bir giriş sağlamaktır.
"Grokking Algoritmaları " nı okursanız, algoritmalara bir giriş de bulabilirsiniz .
Ayrıca Jack Brown: AQA Decision 1 1.01 Tracing an Algorithm oynatma listesini de beğendim . Eğlenmek için sıralamada algoritma görselleştirmelerini görebilirsiniz
.görselgo.net .
GO TO FULL VERSION