Web Programlama

Web Programlama

DERS PROGRAMI
Web Programlama 301 Ders Programı
Sınava Gir

Hızlı Sıralama (Quicksort) Algoritması

Lisans: Creative Commons 26.11.2020 tarihinde güncellendi
Bakabileceğiniz Etiketler: Eğitmen: Geleceği Yazanlar Ekibi

Genel olarak kabarcık sıralama yer değiştirme sıralaması ve seçme sıralaması yöntemlerinden daha etkin bir sıralama algoritmasıdır ve hızlı sıralama (quicksort) adıyla bilinir. Quicksort algoritması sıralanacak diziyi iki parçaya ayırır ve bu parçalama işlemi alt parçalar için de sürdürülür. Bu özelliğiyle quicksort algoritması özyineli (rekürsif, ing: recursive) nitelikteki bir algoritmadır.

 

Algoritmanın ilerleyişi

Sıralanacak olan dizi a1,a2,…..an dizisi olsun. Bu liste içinden bir elemanı seçelim (bu seçme işlemi çeşitli şekillerde gerçekleştirilebilir; en basiti ilk elemanı seçmek şeklinde olabilir). Liste içinden seçtiğimiz elemana pivot eleman ya da ayırıcı eleman (separator) adı verilir. Bu elemanı p ile gösterelim. a dizisinin p'den küçük olan elemanları bir sol alt liste içine (bu listeye L adını verelim) ve p'den büyük olan elemanları da bir sağ alt liste içine yerleşecektir. Bu sağ alt listeye de R adını verelim. Bu durumda a listesi,

a⇒ L , p , R

şeklinde 3 parçadan oluşmuş bir biçime dönüştürülür.

L içindeki tüm elemanlar p'den daha küçük ya da ona eşittir. R içindeki tüm elemanlar ise p'den büyüktür. p ise dizi içinde doğru yere yerleşmiştir.

a dizisi:

Bu işlemi daha sonra L ve R alt listelerine de uygulamak gerekir. Yani aynı sistematiğe göre L içinden bir pivot (p) seçilerek bundan küçük olanlar bir L' ve bundan büyük olanlar da bir R' alt listesi içinde toplanır. Aynı şey R listesi için de gerçekleştirilir. Aynı parçalama işleminin sürekli olarak alt listelere de uygulanması algoritmanın rekürsif karakterini göstermektedir.

Herhangi bir alt listede 0 ya da 1 tane eleman kalınca rekürsif işlem sona erecektir.

 

Algoritmanın ifadesi

qsort(x,b,s)
{x dizisi sıralanacaktır. Bu dizi xb,xb+1,..xs şeklindedir}
begin
if s > b begin { sıralanacak eleman mevcuttur}

P pivot elemanını liste içinden seç(mesela ilk eleman olabilir) ve x dizisini aşağıdaki biçimde parçala!

Xb,...xk , p, xk+1,...xb
qsort(x,b,k)
qsort(x,k+2,b)
end
end

Yöntemi bir örnek dizi üzerinde açıklayalım. Sıralanacak dizi aşağıdaki gibi olsun:

Pivot eleman olarak dizinin ilk elemanı seçilsin:

p=A(1)=45

Bu durumda A dizisi 45'ten küçük olanları içeren bir L ve 45'ten büyük olanları içeren bir R dizisine parçalanacaktır:

Daha sonra ise L ve R'ye de aynı işlem uygulanacaktır.

 

Hızlı sıralama algoritması için geliştirilen JavaScript programının listesi

<html>
<head>
<TITLE>İÇİNDEKİLER</TITLE>
</head>
<body bgColor="lightpink" text="darkblue">
<SCRIPT LANGUAGE="JavaScript">
var a=new Array(11);
document.write("<H3>"+"QUICKSORT SIRALAMA ALGORİTMASI"+"</H3>");
document.write("<H3>"+"SIRALAMA ISLEMINDEN ÖNCEKİ DIZI"+"</H3>");
document.writeln( "<TABLE BORDER = '2' WIDTH = '50%'>" );
document.writeln( "<TR><TD WIDTH = '80'><B>İNDİS</B>"
+ "<TD><B>DEĞER</B></TR>" );
for ( i = 0; i < a.length; i++ )
{
a[i]=Math.floor(1+Math.random()*10000);
document.writeln( "<TR><TD>" + i + "<TD>" +
a[ i ] + "</TR>" );
}
document.writeln( "</TABLE>" );
HIZLI_SIRALA(a, 0, a.length-1);
document.write("<H3>"+"SIRALAMA ISLEMINDEN SONRAKİ DIZI"+"</H3>");
document.writeln( "<TABLE BORDER = '2' WIDTH = '50%'>" );
document.writeln( "<TR><TD WIDTH = '80'><B>İNDİS</B>"
+ "<TD><B>DEĞER</B></TR>" );
for ( i = 0; i < a.length; i++ )
{
document.writeln( "<TR><TD>" + i + "<TD>" +
a[ i ] + "</TR>" );
}
document.writeln( "</TABLE>" );
/* HIZLI_SIRALA adlı fonksiyon 3 argüman alıyor
İlk argüman sıralanacak elemanları içeren a dizisidir.
İkinci argüman dizinin başlangıç pozisyonunu ve 3. argüman ise dizinin son elemanını gösteriyor
HIZLI_SIRALA fonksiyonunun her çağrılışında dizinin farklı bir parçası işlem görecektir.*/
function HIZLI_SIRALA( a, sol, sag)
{var dur, son,u;
if (sol >= sag)
return;
u=Math.floor((sol+sag)/2);
DEGIS(a, sol, u);
/*Dizinin ortasındaki eleman pivot olarak alınıyor ve listenin en soluna kaydırılıyor. */
son = sol;
for (dur = sol + 1; dur <= sag; dur++)
if (a[dur] < a[sol])
DEGIS(a, ++son, dur);
DEGIS(a, sol, son);
HIZLI_SIRALA(a, sol, son-1);
HIZLI_SIRALA(a, son+1, sag);
}
/* DEGIS fonksiyonu dizi içindeki iki elemanın yerlerini değiştirmektedir.*/
function DEGIS(a, i, j)
{var t;
t = a[i];
a[i] = a[j];
a[j] = t;
}
</SCRIPT>
</body>
</html>

Sınava Gir