Sevgili yapraam. Bu aralar sağ kulağım sağır. Sadece sol kulağımla duyduğum için kendimi yarım insan gibi hissediyorum.Bunu nedense belirtmek istedim.
Geçenlerde running time hesabı ve notasyon muhabbetinden kısaca bahsetmiştim. Kısaca bahsetmiştim çünkü bu konuları işledikçe iyice aklınıza oturacağını düşünüyorum ve Sorting algorithm dediğimiz sıralama algoritmalarına giriş yapıyorum.
İçinde integer,char,String vs şeklinde değişkenlerin olduğu tek boyutlu bir dizi düşünelim(Mevzuyu kapmanız için tek boyutlu diziden girdim.). Bu dizi içindeki elemanları artan veya azalan şekilde. En az running time'ı kullanarak sıralayabileceğimiz algoritmalar sıralama algoritmasıdır.
String,char vs gibi harf alan değişkenlerde alfabetik sıraya bakılacağını biliyosunuzdur heralde.Neyse,
Sıralama algoritmalarına neden ihtiyaç duyarız?
Büyük miktarda verilerimiz olduğunu düşünelim(veritabanı vs. gibi) Eğer verilerimiz karmaşık bir sıralama içindeyse aradığımız veriye ulaşmak çok fazla vaktimizi alabilir. Ama bir sıralamaya işimiz çok kolaylaşır.
Aynı zamanda N elemanlı bir dizide sıralama algoritmalarının notasyonu(karmaşıklığı) O(Log N)'dir.
Sıralama algoritmalarında in place(yerinde) ve Stability(kararlılık) dediğimiz 2 kavram vardır;
In-place = Bir sıralama algoritması O1 düzeyinde bellek gerektiyorsa bu algoritma in-place'dir.
Stability = Bunu örnekle anlatırsam daha iyi olur(benim için). Misal elimizde 1. ve 2. sınıf öğrencilerinin karmaşık sırada olduğu bir dizi var ==> "2 veli","1ece","1halil","2ayşe","2fatma""1semih" vs vs şekilde .
Eğer bu dizi hem sınıflarına göre hemde isimler alfabetik sıralıysa. Algoritma stability bir algoritmador.
Ama bu dizi sadece sınıflara göre sıralı ama isimler karışıksa bu algoritma stabillity değildir.
Stability'i anladınız ama in-place'i anlamadınız sanırım yapraklarım. Ama halledicez.
Algoritma türlerine yavaştan el atalaım. Bu derste 3 çeşit sıralama algoritmasından bahsedeceğim sana yapraam;
1.Bubble sort(kabarcık sıralama)
2.Selection sort(seçip sıralama)
3.Insertion sort(eklemeli sıralama)
-Bubble sort-
İlk anlatacağım sıralama algoritması olan bubble sort verileri sıralamaya yarar.(zaaaaaaa xd)
Asıl soru verileri nasıl sıralar?
ilk veriden başlayarak, dizi içindeki bir veriyle hemen sonra gelen veriyi karşılaştırır. Eğer verimiz bir sonrakinden büyükse yerlerini değiştirir(artan sıralama, azalan olsaydı tam tersini yapardı)
Bubble sort'un genel mantığı bu şekildedir.
Bir örnekle anlatayım;
A dizisi içinde 12,62,2,5 elemanları olduğunu varsayalım ve bunu bubble sort içine sokup sıralayalım.
12,62,2,5 ====> ilk durum
Sıralamaya sokalım.
12<62 ? evet. ozaman dokunma. 62<2? hayır yer değiştir. 62<5 hayır. yer değiştir. ve ikinci durum
12,2,5,62 =====> 2. durum
12<2? hayır. yer değiştir. 12<5? hayır. yer değiştir. 12<62 ? evet. ozaman dokunma.
2,5,12,62 =======> 3. durum
Ve algoritmamız sıralandı. Bilmem anlatabildimmi.
Bir tanede örnek java metodu yazalım şuraya;
Public void BubbleSort(int A[],int N){
// A sıralanacak dizinin adı, N dizinin eleman sayısı,
for (int i=0;i<N,i++){
//en baştan kontrole başla
for(int j=1,j<(N-i),j++){
// sıralanmayan bölümü en baştan tekrar kontrol et.
if(A[j-1]<A[j]) swap(A[j-1],A[j];//sonraki eleman sırasızsa swap(değiştir.)
}// ilk for biter
}// ikinci for biter
}//method biter
kjkjkj
Örnek kodumuzda bu şekilde arkadaşlar. Algoritmamız için;
-Stability ? Yes.
-in-place ? Yes,
- Notasyon =O(N2)
Bubble sort bukadar bikaç kere çalıştırarak mantığını sizde kavrarsınız zaten. Gelelim 2 numaraya
Bu algoritmaları hızlı hızlı geçiyorum. ilerde çok taşaklı konular var çünkü
- Selection Sort-
Sıralama fantazilerinden bir diğeride selection sort'dur. Peki bunda mantık nasıldır?
Verilen dizide en küçüğü bulup en başa koyar, daha sonra geri kalanlar arasından en küçüğü bulup en başın bir sonrasına koyar, sonra yine geri kalanları tarar arasından en küçüğü bulup bir sonraki yerine koyar.. bu işlem böyle sayılar sıralanana kadar sürer gider.
Gelelim örneğimizde;
Yine bir A dizimiz olsun içinde yine 12,62,2,5 sayıları olsun ve yine bunları sıralayalım. Yalnız bu kez selection kullanalım.
12,62,2,5 =======> ilk durum
Sıralamaya sokalım
ilk sayı 12, devam 2. sayı 62, 62>12 oyüzden devam. 3. sayı 2, 12>2 at hafızaya, son sayı 5, 5<2 olmadığı için en başa 2'yi koy 12'yide 2'nin yerine koy amk zaten değiştirecez.
2,62,12,5 =======> ikinci durum
Sıralamaya devam.
artık ilk sayıyı siktir ettik. karşılaştırmaya 2. sayıdan başlıyoruz. ikinci durumda ilk sayı 62. devam, ikinci sayı 12, 62>12 12'yi attık hafızaya. 3. sayı 5, 5<12 ve 2. durumun en küçüğü 5 at koyalım bunuda yerine.
2,5,12,62 =======> üçüncü durum
işte böyle böyle sayıları sıraya sokuyoruz.
Gelelim örnek java metodumuza;
public static void selectionSort(int[] A) {
int i, j, minIndex, tmp; // gerekli değişkenlerimizi tanımlayalım.
int n = A.length;// n değişkenini dizimizin eleman sayısına eşitledik(bunlar hep ön hazırlık)
for (i = 0; i < n - 1; i++) { //
minIndex = i; //sıralı bölümü belirledik.(en küçüğü koyduktan sonra. bir sonrakinden //başlıyoruz ya
for (j = i + 1; j < n; j++)
if (A[j] < A[minIndex])// dizide en küçük olanın indeksini belirliyoruz
minIndex = j; // belirledik
if (minIndex != i) {// burdada yerleri değiştiriyoruz.
tmp = A[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
}
-Stability ? Yes.
-in-place ? Yes,
- Notasyon =O(N2)
Gençler selection sort'ta kısaca bu şekilde. Gelelim sıradaki muhabbetimize...
- Insertion sort -
Her yerde bu algoritmayı kağıt oyunu oynarken kartlarınızı sıralama muhabbetinden örnek vererek anlatırlar. Bende maalesef öyle anlatıcam. (Çünkü güzel bi örnek amk)
Herneyse batak oynadığınızı düşünün elinize önce sinek 2 geldi aldınız, daha sonra sinek 5 geldi 2'nin sağına koydunuz, sonra sinek 3 geldi 2 ve 5'in arasına koydunuz. daha sonra sinek 4 geldi onuda 3 ile 5'in arasına koydunuz. bu durumu birde diziyle ifade edeyim.
A dizisi;
ilk durum ; 2 // sonra 5'i ekledik
ikinci durum : 2,5// şimdi 3 geldi
üçüncü durum:2,3,5 // şimdide 4 geldi
son durum :2,3,4,5
yani sayıyı kendinden küçük olanın hemen sonrasına koyup dizinin geri kalanının indekslerini 1 arttırıyoruz.
Örnek metodumuzuda yazalım bakalım;
public static void InsertionSort(int A[], int N){
int j, P, Tmp;
for(P = 1; P < N; P++ ) {
Tmp = A[ P ];// geçici değişkenimiz dizinin P. sırasındaki eleman olur
for(j = P; j > 0 && A[ j - 1 ] > Tmp; j-- ){// eğer sıradaki elemanımız bir öncekinden
// küçükse işlemlere başlar
A[ j ] = A[ j - 1 ]; // döngü boyunca küçük olandan büyükleri bir sonraki indeks'e
// atar
}
A[ j ] = Tmp;// küçük olanıda hakkettiği yere koyar
}
}
-Stability ? Yes.
-in-place ? Yes,
- Notasyon = O(N2)
Evet sıralama algoritmalarımız bukadar. Bunların dışında quicksort,mergesort vs vs bi dünya daha sıralama algoritması vardır. Onlarıda araştırmanızı tavsiye ederim.
Yapraklarım bi sonraki derste sevişmek ümidiyle...
Hiç yorum yok:
Yorum Gönder