Quicksort (Hızlı sıralama)

Algoritmalar konusunda ilk yazımı bugünden başlıyorum.Üniversite 2. sınıfta tanıştığım sıralama algoritmalarından ilki hızlı sıralama…

İngilizce Adı Quick Sort

Ortalama O(n log n)

En kötü O(n²)

Bellek O(log n)

Kararlı mı? Hayır

Yöntem Karşılaştırma ile Bölümlendirme Şimdi Hızlı sıralama nedir. Öncelikle size gerçekten zevkli bir video ile sunmak istiyorum. Burada Hareketli bir şekilde izleyebilirsiniz 🙂

Şimdi burada ki resme bakın. Bir pivot sayımız olmalı ilk başta burada 5 bizim pivot sayımız ve bu sayıyı yerine yerleştiriyoruz.Pivot elemanımızın solunda hep küçük sağında hep büyük sayılar olup onlar karşılaştırılacak.5 tam ortaya yerleştikten ne kaldı sola 1 2 3 4 sayıları sağda ise 6 7 8 9 tabikide bu sayılar sıralımı değil. Amacımız pivot elemanı bulduktan sonra direk sol ve sağ tarafı sıralamak.Yukarda sıralama şeklini görüceksinizdir . Bu kadar aşağıda ise animasyon olarak gösterimi vardır.

 

Bu da kodumuz 🙂

//package hızlıSıralama;

import java.util.Arrays;

public class HızlıSıralama {
int[] arr = { 2, 17, -4, 42, 9, 26, 11, 3, 5, 28 };

void quickSort(int[] a, int altindis, int üstindis) {
// altindis o adımda sıralanan altdizinin ek küçük indisidir
// üstindis o adımda sıralanan altdizinin ek büyük indisidir

int i = altindis, j = üstindis, h;
// x terimi, mukayesenin yapılacağı mihenk’dir (pivot)
int x = a[(altindis + üstindis) / 2];
// Takas eylemiyle diziyi ayrıştırma
do {
while (a[i] < x)
i++;
while (a[j] > x)
j–;
if (i <= j) {
h = a[i];
a[i] = a[j];
a[j] = h;
i++;
j–;
}
} while (i <= j);
// yinelge (recursion)
if (altindis < j)
quickSort(a, altindis, j);
if (i < üstindis)
quickSort(a, i, üstindis);
}

public static void main(String[] args) {
HızlıSıralama qs = new HızlıSıralama();
System.out.println(“Sıralamadan önce: “);
System.out.println(Arrays.toString(qs.arr));
qs.quickSort(qs.arr, 0, 9);
System.out.println(“Sıralamadan sonra:”);
System.out.println(Arrays.toString(qs.arr));
}
}