Sıra | DOSYA ADI | Format | Bağlantı |
---|---|---|---|
01. | Yinelemeli Sıralama Algoritmaları | ppt | Sunumu İndir |
Transkript
1 Yinelemeli Sıralama Algoritmaları • İçerik – Kabarcık Sıralaması – Seçmeli Sıralama – Eklemeli Sıralama
2 Sıralama - Tanım
3 Neden Sıralama? • Bilgisayar bilimlerinde sıralama algoritmaları en sık kullanılan algoritmalardandır. – Büyük miktardaki veriye erişmek veya işlemek için kritik önem taşır. Örneğin veritabanı sistemleri. – Bazı karmaşık algoritmaların ilk adımıdır. • Veriye hızlı ulaşmak için sıralı tutulması yararlı olacaktır. • Eleman sayısı N alan dizide ikili arama yaparken karmaşıklığın O(log N) olmasını sağlar. • Dizideki k. Büyük elemanı ararken O(1) karmaşıklığında erişim sağlar. • Yenilenen değerleri bulmak kolaylaşır. • Dizindeki dosyalar genellikle sıralı saklanır. • Sözlükteki kelimeler sıralıdır.
4 Sıralama – Dikkat Edilmesi Gerekenler • Bellek: Sıralama algoritmaları sıralama yaparken ekstra bellek kullanırlar mı? – Sıralama sırasında verinin bir kısmını veya tamamını geçici olarak başka bir yere kopyalamamız gerekir mi? – Eğer sıralama algoritması O(1) düzeyinde bellek gerektiriyorsa, bu algoritmaya yerinde(in place) sıralama algoritması denir. • Kararlılık: Kararlı sıralama algoritmaları sıralanacak dizinin içinde değerleri birbirine eşit olan öğelerin birbirlerine göre olan konumlarını korur. – Ö.g. Verilen: İsme göre sıralı telefon rehberi . Ülkeye göre sıraladığımızda, her ülke kendi içinde isme göre de sıralı mı? – Veritabanı için son derece önemlidir – bir sonraki slayt
5 Kararlılık – Neden? • İsmi göre sıralı aşağıdaki veri kayıtları dikkate alındığında. Öğrenciler 1 veya 2. sınıfta (Ali, 1), (Mehmet, 2) (Nazan, 1), (Selim, 1), (Zeynep, 2) • Verilerimizi sınıfa göre sıralayalım (Ali, 1), (Nazan, 1), (Selim, 1), (Mehmet, 2) (Zeynep, 2) – Veriler sınıfa göre sıralı – Sınıftaki öğrenciler de kendi aralarında isme göre sıralı. – Elde edilen sonuç kararlı sıralama algoritmasının örneğidir. (Nazan, 1), (Ali, 1), (Selim, 1), (Zeynep, 2) (Mehmet, 2) – Veriler sınıfa göre sıralı – Fakat sınıftaki öğrenciler kendi aralarında isme göre sıralı değil. – Elde edilen sonuç kararsız sıralama algoritmasının örneğidir.
6 Kabarcık Sıralaması • Fikir: i ve i+1 inci elemanları karşılaştırılır ve eğer A[i] > A[i+1] ise yer değiştirilir. – Sıralı olmayan kısımda bastan sona kadar aynı şekilde işlemi tekrarla. • Örnek: Aşağıdaki sayıları sıralanacak olursa: – 21, 33, 7, 25 – Başla: 21 33 7 25 // Başlangıç durumu – Tekrar1: 21 7 25 33 // En büyük eleman sona geliyor(4. yer) – Tekrar2: 7 21 25 33 // En büyük 2. eleman 3. yere – Tekrar3: 7 21 25 33 // En büyük 3. eleman 2. yere – Tekrar4: 7 21 25 33 // En büyük 4. eleman 1. yere
7 Kabarcık Sıralaması /* tamsayılarda kabarcık sıralaması - sözde kod * A dizisi N tane tamsayı içeriyor */ BubbleSort(int A[], int N){ for(int i=0; i<N; i++) { /* Sıralanmayan kısımda baştan sona kadar*/ for(int j=1; j<(N-i); j++) { /* Yandaki eleman sırasızsa, degistir */ if( A[j-1] > A[j] ) DEGIS(A[j-1],A[j]); } //bitti-içteki for } //bitti-dıştaki for } //bitti-BubbleSort • Kararlı? • Yerinde? • Karmaşıklık = Evet Evet O(N2)
8 Seçmeli Sıralama • Kabarcık sıralaması kararlı ve yerinde , fakat karmaşıklık O(N2) – her adımda 1 den fazla eleman taşıyarak daha iyisini yapabilir miyiz? • Fikir: Dizide en küçük elemanı arayın ve A[1] ile yer değiştirin. Kalan elemanları tekrar arayın ve en küçüğü seçin ve A[2] ile yer değiştirin. Bu işlemi son elemana ulaşıncaya kadar tekrarlayın. • Örnek: Aşağıdaki diziyi sıralayın: – 21, 33, 7, 25 • Seçmeli sıralama karalı mı? – 7 yerine 33 olduğunu düşünelim Karalı değil • Yerinde mi? Evet. – Değişimde kullanılan temp değişkeni için gereken alan O(1). • Karmaşıklık? – N + N-1 + N-2 + … 1 = N*(N+1)/2 = O(N2)
9 Araya Sokma Sıralaması • Eğer ilk \k\ eleman sıralı ise ne yapabiliriz. – Ö.g. 4, 7, 12, 5, 19, 16 • Fikir: Bir sonraki elemanı uygun pozisyona yerleştir ve k+1 tane sıralı elamanın olsun. Bir sonrakini yerleştir k+2 tane sıralı elemanın olsun. Bu şekilde tüm elemanları diziye ekle. – 4, 5, 7, 12, 19, 16 – 4, 5, 7, 12, 19, 16 – 4, 5, 7, 12, 16, 19 Tamam! – Tüm dizi için, N-1 geçiş – Kart sıralamaya benzer: • Kartları almaya başlayın (eliniz boş) • Almaya devam edin. 8A102 Sağa kaydır
10 Araya Sokma Algoritması /* Tam sayılarda Araya Sokma Algoritması – Sözde kod A dizisinin N tane elemanı vardır */ InsertionSort(int A[], int N){ int j, P, Tmp; for(P = 1; P < N; P++ ) { Tmp = A[ P ]; for(j = P; j > 0 && A[ j - 1 ] > Tmp; j-- ){ A[ j ] = A[ j - 1 ]; // A[j-1] elemanı sağa kaydır } //bitti-içteki for A[ j ] = Tmp; // A[P] (= Tmp) için uygun yer bulundu } //bitti-dıştaki for } //bitti-InsertionSort • Yerinde (Tmp için O(1) yer gerekli) ve kararlı • Karmaşıklık: • En Kötü – Ters sıralı dizi = O(N2) • En iyi – Sıralı dizi = O(N).
11 Özet • Basit sıralama algoritmaları : – Kabarçık sıralaması - O(N2) – Seçmeli sıralama - O(N2) – Araya sokma sıralaması - O(N2) – Araya sokma sıralaması küçük boyutlu veri için (~20) pratikte en iyi sonucu verir.
Uygulama • Derste gördüğünüz sıralama algoritmalarını Java programlama dilinde yazınız. – 100 000 tane rastgele üretilen sayıyı her bir sıralama algoritmaları ile sıralayınız. – Sıralama için geçen süreyi gözlemleyiniz. – Süre ölçümü için bir sonraki slayt. 12
Uygulama (devam) • Çalışama süresi hesaplama – Java programlama dilinde bir işlemin ne kadar süreceğini ölçmek için aşağıdaki yapı kullanılabilir. 13 // kronometreyi başlat long bas = System.currentTimeMillis(); // işlemler yapılıyor. // kronometreyi durdur. long son = System.currentTimeMillis(); long gecenSure = son-bas; //milisaniye
Uygulama (devam) – Genel Yapı main(){ A[100000] = sayı üret kabarcık sıralaması için süre ölçümü seçmeli sıralama için süre ölçümü araya sokma sıralaması için süre ölçümü süreleri ekrana yazdır. } 14