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?
L eşit olur
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 i
Dizinin 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 = 10
n = 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 a
ve b
if'in (if )' a
den 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: b
a > b
b
array[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. while
Daha 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]
. 5
daha fazlası 3
- her şey yolunda. Ama 2
daha azdır 5
. Ancak, [3, 2, 5]
başka bir geçiş gerektirir, çünkü3 > 2
ve 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 * n
yani 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:
Seçim sıralaması
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ı
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));
Bu konuyla ilgili materyal:
Kabuk sıralaması
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 konuyla ilgili materyal:
Birleştirme sıralaması
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ırO(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:
Sayma sıralaması ve sayı tabanı sıralaması
Bir başka ilginç sıralama algoritması da sayma sıralamasıdır. Buradaki algoritmik karmaşıklıkO(n+k)
, n
eleman sayısı ve k
bir 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:
Hızlı sıralama
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
. pivot
Bundan sonra görevimiz, solundan daha küçük değerleri pivot
ve daha büyükleri - sağa taşımaktır . L
Bunu 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 zamanpivot
.
R
Ardı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
R
eşit olur
pivot
. Ardından,
L
işaretçi işaretçiden önceyse veya onunla çakışıyorsa, eleman elemandan küçükse
R
elemanları 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.
L
R
L
R
L
R
pivot
pivot
. 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
pivot
ortasına, yani 6 rakamının altına yazın. Yuvarlak içine alın. 4'ün altına yazın
L
ve 3'ün altına yazın
R
.
L
4, 6'dan az, 2, 6'dan az. Pozisyona geçiyoruz
pivot
çünkü
L
geçemiyoruz.
pivot
, duruma göre. Tekrar 4 2 6 7 3 yazın. 6'yı (
pivot
) daire içine alın ve
L
altına koyun. Şimdi
R
işaretçiyi hareket ettirin. 3, 6'dan küçüktür, bu nedenle
R
iş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
L
3'te.
R
İşaretçi 6'da. İşaretçileri 'nin
L
ötesine geçene kadar hareket ettirdiğimizi unutmayın
R
.
L
Bir 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
L
sürece
L
işaretinden daha küçük bir sayıyı işaret eder
pivot
.
R
Ancak 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
).
L
geçer
pivot
ve hareket etmeyi durdurur.
R
hareket etmiyor Takas yapmıyoruz. Kaydırma
L
ve
R
bir pozisyona göre.
R
İşaretçiyi 1'in altına yazın.
L
İşaretçi sınırların dışında. Çünkü
L
sınırların dışında, hiçbir şey yapmıyoruz.
pivot
Ama yine 4 2 3 1 yazarız, çünkü bu bizim (6)' dan küçük olan sol tarafımızdır . Yeniyi seçin
pivot
ve 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
R
sıralamak mantıklı değil çünkü sadece 1 eleman var. Ancak 4'ten olan kısmı sıralama için işaretçiye
L
gönderiyoruz .
R
a'yı seçip
pivot
baş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,
pivot
diğer eleman önceki parçaya takas edilir
pivot
.
GO TO FULL VERSION