Web Programlama

Web Programlama

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

Yer Değiştirme Sıralaması (Exchange Sort)

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

Anlaşılması en kolay olan sıralama yöntemlerinden biridir. Sıralamayı n elemanlı bir L listesi içinde yapacağımızı ve artan sıralama olacağını var sayıyoruz.

En başta veri listesinin ilk sırasındaki eleman ikinci ile karşılaştırılır. Sıralama artan türde sıralama ise ve L1>L2 ise, L1 ve L2 arasında yer değiştirme işlemi yapılır. Daha sonra L1 ile L3 karşılaştırılır ve gene artan sıralama yapılıyorsa ve L1>L3 ise, L1 ve L3 arasında yer değiştirme yapılır. Bu karşılaştırmalar ilk geçişte L1-L4, L1-L5 ve nihayet L1-Ln arasında yapılır. Birinci geçişin sonunda veri listesi içindeki en küçük veri en başa gelir.

İkinci geçiş ise, L2 ve L3'ün kaşılaştırmasıyla başlar ve L2>L3 ise yer değiştirme olur. Sonra L2-L4, L2-L5 ve nihayet L2-Ln karşılaştırmaları yapılır. İkinci geçişin sonunda ise veri içindeki en küçükten bir sonraki veri listenin ikinci yerine yerleşir.

Üçüncü geçişte L3-L4, L3-L5 ve nihayet L3-Ln karşılaştırmalarıyla listenin 3. yerine doğru eleman yerleştirilir.

Son geçiş n-1'nci geçiştir ve bu geçişte sadece Ln-1 ile Ln liste elemanları karşılaştırılır ve gerekiyorsa yer değiştirme yapılır.

n-1'nci geçiş sonunda liste sıralanmıştır.

 

Yer değiştirme algoritmasına örnek:

Yer değiştirme sıralaması yöntemini daha iyi anlayabilmek için algoritmayı örnek bir veri üzerinde çalıştıralım. Örnek veri aşağıdaki gibi olsun:

1. Geçiş (Pass)

45 ile 21 karşılaştırılır ve yer değiştirme yapılır:

21 ile 3 karşılaştırılır ve yer değiştirme yapılır:

3 ile 16 karşılaştırılır; yer değiştirme olmaz.

3 ile 8 karşılaştırılır; yer değiştirme olmaz.

1. geçiş sonunda L listesi

şeklindedir ve listedeki en küçük eleman en başa gelmiştir.

 

2. Geçiş

2. geçiş, 45 ile 21'in karşılaştırmasıyla başlar ve yer değiştirme olur:

 

3. Geçiş

 

4. Geçiş

45 ile 21 karşılaştırılır ve yer değiştirme olur:

Görüldüğü gibi 4. geçiş (n=5 ve n-1=4) sonunda veri sıralanmıştır.

 

İki elemanın yer değiştirmesi işlemi

Li ve Lj liste elemanları belli bir anda tek bir değer saklayabilirler. Bilgisayar belleğinde de durum böyle olacaktır; yani Li ve Lj ye birer bellek konumu ayrılacak ve burada birer değer saklanacaktır. Bir bellek konumuna yeni bir değer atanınca önceki değer silinecektir. Bir başka deyişle, Li nin değeri Lj'ye atansa, Lj'nin değeri silinecektir. Halbuki yer değiştirme yapabilmek için Lj'nin değerini de Li'ye atamamız gerekir. Bu durumda yardımcı bir alana ya da bellek alanına ihtiyacımız olacaktır. Bu yardımcı alana T diyelim. Buna göre yer değiştirme şu şekilde olacaktır:

  1. Önce Li nin değeri T'ye aktarılır:
  2. Sonra Lj nin değeri Li'ye aktarılır:

3) Nihayet T nin değeri Lj'ye aktarılır:

Böylece, Li ve Lj nin değerleri birbiriyle yer değiştirmiş olur. Bu işleme yer değiştirme (İng. Swap) işlemi denir.

 

Yer değiştirme sıralaması ile ilişkili program

<html>
  <head>
  <TITLE>İÇİNDEKİLER</TITLE>
    </head>
  <body bgColor="lightblue" text="darkblue">
<SCRIPT LANGUAGE="JavaScript">
	function SIRALAEXC(  a )
	{
		var i, j, t;

		i = 0;
		while( i < (a.length- 1) ) {
			j = i + 1;
			while( j < a.length) {
				if( a[i] > a[j] ) {
					t= a[i];
					a[i] = a[j];
					a[j] = t;
				}
				j++;
			}
			i++;
		}
	}

var dizi =[ 10, 23, 8, 253, 191, 711, 2, 27, 1, 813];
document.write("<H3>"+"SIRALAMA ISLEMINDEN ONCEKI DIZI"+"</H3>");
document.write("<H3>"+dizi.join("   ")+"</H3>");
SIRALAEXC( dizi);
document.write("<H3>"+"SIRALAMA ISLEMINDEN SONRAKİ DIZI"+"</H3>");
document.write("<H3>"+dizi.join("   ")+"</H3>");
</SCRIPT>
    </body>
  </html>

Sınava Gir