Algoritma - Linked list(bağlı listeler)

Gençler nasılsınız ? Uzun süredir buralara birşeyler karalamıyordum. Vize haftasındaydım. O sebepten dolayı böle bi sıkıntı yaşadık. Neyse konuya girelim;

Aslında yapraam okulda bana derste öğretilen sırayla konuları buraya yazmak istiyordum ama. Finallere az kaldı ve anlayamadığım çok konu var. O yüzden önemli konuları öne aldım. Daha sonra daha önemsiz olan konuları burda yazıcam. Yani sonuçta data structures and algorithms dersinde ne öğrendiysem burda yazmış olacağım ama sırasız şekilde olucak.

Bugün sizlere benim ciddi şekilde anamı ağlatan linked list yapısından söz edicem. Nedir linked list ?

Şöyle, linked list içinde aynı arrayde olduğu gibi veri depolarız ve ordan çağırırız fln. Ama linked list arrayden biraz daha farklıdır.
Mesela ;

- Array'in aksine kapasite sorunu yaşamazsın.

- Array'in aksine birden fazla veri türünü depolayabilirsin

- linked listte araya eleman ekleme,silme,vs daha hızlıdır

- sıralama muhabbeti daha hızlıdır.

gibi gibi..

- Linked list mantığı -

Array içinde veri saklıyorsak. Array içindeki her elemanın bir sırası vardır. ve ordan sırayla çağırırız. Ama linked list içinde mantık tamamen farklıdır. Linked listte her eleman kendinden sonrakine bağlıdır. Şimdi tabi aklınıza nasıl ne alaka amk gibi sorular geliyordur. Ama aydınlatıcam merak etmeyin. Bir resimle sizi aydınlatmaya çalışayım;

Buraki örnek son derece basit bir linked list örneği, sadece numara ve isim değişkeni tutuyoruz.Bir grubumuz olduğunu düşünün ve her yeni kayıda sıradaki numarayı verdiğimizi düşünün. 

Linked listte verilerini tuttuğumuz elemana node (düğüm) adını veririz. Mesela yukarıdaki resimde bir node içinde nelerimiz var;

- int no // kişinin numarasını tutuyor

- int name // kişinin adını tutuyor

- next // burdada bir sonraki node'un adresini tutuyor

Gençler!! Burdaki önemli nokta, Her node hafızada bir yere koyulur ve ordan çağırılır. mesela head yani ilk node'umuz hafızada ID21 adında bir yerde duruyor. sonra geçici bir p objesi oluşturduğumuzu düşünelim. içinde p.no = 1, p.name=ali,p.next = null bulunsun ve p objemizde ID54 içinde olsun mesela, head.next=p dediğimiz zaman, head ID54 içinde bulunan objeye bağlıdır anlamı çıkıyor.

Şimdi yukarıdaki resimde gördüğünüz gibi her eleman kendinden sonrakine bağlı. Burda önemli nokta head'i değiştirmememiz lazım. Çünkü bir elemana ulaşacağımız zaman head'den başlayıp sırayla gidicez. Mesela head'de 1. sıradaki adamın ismi var ve biz 6. sıradaki adamın ismini öğrenmek istiyoruz ozaman zaman, Head'den yani 1 numaradan başlayarak  teker teker numaralara bakar ve 6. sıraya geldiği zaman onun içindeki name değişkeninin değerini bize döndürür.

İsterseniz resimdeki muhabbeti koda dökelim biraz daha anlaşılır olsun. Sonra methodlara devam ederiz.

linked listi yazmak için 3 tane farklı class'a ihtiyaç duyuyorum ben;

1. main methodumun olduğu class.

2. node'umun içinde tutacağım veri türlerinin olduğu class

3. linked list'imin ve linked list methodlarının olduğu class.

önce node'umun olduğu class'tan başlayayım muhabbete;

Yukarda gördüğün üzere yapraam, next objesi person olarak tanımlı yani, next içinde name,no ve next var. Bir sonraki adresi tutabilmesi için;

gelelim linked list'imin olduğu class'a ;

Burda head ilk node'umuzu tutacağımız yer. head'den başlayıp next'ine sonra next'tin nextine fln derken last'a kadar gelicez işte. last her eleman eklediğimizde değişecektir dansöz gibi.

birde add methodunu koyim şuraya aynı demo1 class'ı içinde;

Şimdi anlatayım; p adında geçici bir person oluşturuyoruz eklenecek veriyi içinde tutuyor. next'i haliyle null.

Eğer bu linked list'e ekleyeceğimiz ilk elemansa yani head =null ise, linked listimizin ilk elemanıda(head), son elemanıda(last) p'nin içindeki değerdir. 

Eğer listeye ekleyeceğimiz ilk eleman değilse (yani head doluysa), Burda önemli bir nokta var, 

last.next = p kodunu yazdığımız zaman, head'inde last'ında next'ine ekleme yapar, eğer nextlerinin içindede değerler varsa, null olan next'e kadar gelir ve p'nin içindeki değerleri o next'in içine atar, Nedenini sorarsanız bende bilmiyorum. Ama öğrenicem öğrenince editlerim.

Neyse daha sonrada son elemanı(last) yine gelen p değerine eşitleriz.

Birde listeleme methodunu ekliyim sonra onun üzerinden devam edelim;

Yine birtane geçici tmp adında person oluşturuyoruz ve onu head'e eşitliyoruz. Bunu yapmamızın sebebi head'le oynamamak çünkü listemiz head'den başlıyor ve sanki iple birbirine bağlı gibi gidiyor.

Şu an tmp içinde ilk elemanlar var yani head.no, head.name, head.next. tmp.next'in içinde head.next ve tmp.next.next içindede head.next.next var nse fazla karıştırmayım bunu.

Daha sonra en baştan başlıyoruz işte teker teker node içindeki değerleri yazdırıp methoddan çıkıyoruz.

Main methoduda paylaşayımda sıkıntı yaşamayalım.

Buraya birşey yazmama gerek yok zaten koddan anlarsınız.

Bu muhabbetleri tamamen kaptığınıza eminseniz linked listle ilgili diğer meselelere giricem;

Şimdi iyi amk güzel yaptık bişiler. yukarıdaki kodlarla teker teker elemanların numarasını ve isimlerini yazdırırız. Ama belli bir sırayla yazmaz, ve aynı numarayı tekrar verir. Yani işimiz tam bitmedi. Misal verelim bir grubumuz var ve grup içinde herkesin özel bir numarası var, hani Tc kimlik numarası gibi düşünün, birine verilen numarayı başkasına veremeyelim. birde listemiz küçükten büyüğe sıralı olsun.

Linked list bu konuda bize güzel bir katkı sağlar, mesela listede 1.diego ve 7. emre var. Biz 3 numara volkanı eklicez listeye, ozaman linked list'in güzel bir durumu devreye giriyor ve. araya elemanı ekliyor.Tabi methodu kodu fln varda, mantığı şöyle;

İşte resimdede gördüğünüz gibi, sıraya göre araya sokar, no1'i no3'e bağlar no3'de no7'ye bağlar. no3 eklenmeden önce no1, no7'ye bağlıydı. Gerekli kodu atim bakalım;

İlk durumda. Eğer listemizde eleman yoksa ilk elemanı ekleyelim;

Eğer listede eleman yoksa ilk elemanı ekledik. Peki liste doluysa? ozaman işler karışıo amk sıralı koyucaz. aynı sayıdan varsa eklemicez fln fln fln;

Yapraam ekleme muabbetide bu şekilde.

Amk şimdide silmeyi anlatayım. Mesela grubumuzda 4 numaralı elemana uyuz olduk. siktir ettik gruptan ama bilgisayardaki listedende çıkartıp işi resmiyete dökmek istiyoruz. Ozaman yapılacak hareket şöyle;

 Yapraam benim yapacaklarım bu kadar. Sonraki derslerde diğer linked list çeşitlerine bakıcaz. Bu anlattığım tek yönlü bağlı listeydi bu arada. Yani eleman sadece kendinden sonrakinin verisini içinde tutuo.

Algoritma - Linear ve Binary search algoritmaları

Naber yapraam nasılsın ?

"Bu arabayı görüyormusun ? Bu araba senin olabilir.
Gaza gelme amk bilgisayar mühendisliğinden mezun olanlara bu arabadan vermiolar. Ama orda aldıığın eğitimle kendini zorlarsan bu arabalardan bir tane alabilirsin."



Evet bir üstte gördüğünüz şey benim kendimi motive etme sebebim gençler. Bu tarz bir araba alıp bu tarz arabası olanların yaşadığı bir hayat yaşama hayaliyle bu amk bölümünü okuyorum. yoksa sanırım bırakabilirdim bu bölümü. Neyse

Bu bölümde sizde searching algoritmalarından bahsedicem bahsedebildiğim kadar.

- Linear Search -
Linear search, Türkçesiyle doğrusal arama. Ama siktir edin siz Türkçesini linear search olarak aklınızda kalsın amk.
Arkadaşlar bu linear search adındanda anlaşıldığı gibi bir dizi içinde arama algoritmasıdır.
Bir dizi içersinde bir öğeyi dizinin ilk öğesinden son öğesine kadar teker teker karşılaştırarak arama işlemi yapar Eğer sayıyı bulursa işte fantaziye göre dizideki yerini söyler veya sayının dizi içinde olduğunu söyler veya her ikisinide kullanıcıya geri değer olarak döndürür. Eğer sayımız dizi içinde yoksa yine fantaziye göre bir değer döndürür. Biz -1 değeri döndürücez.

Notasyonu tahmin edeceğiniz gibi O(N)'dir. Yanlış hatırlamıyorsam.

Önemli bir nokta var unutmadan izah edeyim. Linear search genelde dizinin sırasız olduğu durumlarda tercih edilir. Dizinin sıralı olduğu durumlar için daha işe yarar olan binary search'ü kullanırız.

Bi mantık yazalım şuraya
- aranan değeri 'b' değişkeninin içine at
-A[] dizisinin 0. elemanından n.(son) elemanına kadar bir döngüye sok
-A[i] == b , ise değeri döndür
-else -1 değeri döndür.

Kaptınız sanırım işin mantığını ? Birde örnek kod yazalımda iyicene yerine otursun amk.

static int linear(int[] n , int c){

for(int i = 0; i<n.length ; i++){ // işte dizinin boyutu boyunca arıyoruz.
if (n[i]==c) return i; // eğer elemanı bulursa elemanın dizideki yerini döndürüyor.
}

return -1; // bulamazsa -1 değeri döndürüyor.
}

Yapraam linear search kaba taslak bukadar. Çeşitli fantazilere göre değiştirebilirsin tabi. Gelelim diğer searching muhabbetine..

- Binary search -

Öncelikle Şunu aklında çıkarma. Binary search yapacaksan dizindeki elemanlar sıralı olmak zorunda!

Bunu belirttiğime göre gönül rahatlığıyla binary searchden bahsedebilirim artık.

İşin mantığı şu şekilde, Örneğin sözlükten bir kelimenin anlamına bakacaksınız. Sözlükte kelimeler bildiğiniz gibi alfabetik olarak sıralıdır. Bu sebeple kafanıza göre bir sayfa açarsınız sonra kelime hangi harfle başlıyorsa ona göre sayfanızı sağa veya sola çevirirsiniz, nihayetinde kelimenizi bulursunuz.

Algoritmamızın çalışma stilide buna benzerdir. Önce dizinin ortanca sayıdan ikiye böler. Eğer aranan değer ortanca sayıdan küçükse küçük tarafı yine ortadan büyük küçük diye ikiye böler. Sonra yine böler, yine böler ve en sonunda aradığımız elemanı bulur. Eğer aradığımız eleman dizide yoksa. -1 veya kafasına göre bir değer döndürür geriye.

Binary search genelde recursive(kendini çağıran method) algoritmasıdır. bunun recursive kodunu atıcam bu yüzden ama internette while ile yapılanınıda gördüm onuda koyucam nolur nolmaz diye.

Herneyse gelelim örnek koda ;

static int Binary(int[] n , int first, int last, int src){/* Şimdi burda n dizimiz, first dizinin ilk index'i (yani 0), last dizinin son indexi(yani n.lentgh), src ise dizi içinde aradığımız değer */

  if ( first <= last){ int middle = (last+first)/2; // burda önce ortadaki indexi buluyoruz haliyle

  if (src == n[middle]) { return middle;}  /* eğer orta indexin içindeki değer aradığımız değer eşitse,
   index değerini geri döndürüyoruz */

  else if(src <n[middle]) return Binary(n,first,middle-1,src); /* eğer aradığımız değer ortadaki indexin altında bir sayıysa, orta indexin 1 altındaki değerle methodumuzu tekrar çağırıyoruz(yani dizinin küçük olan yarısına geçiyoruz( bu işlemi bir çok kez tekrar eder eğer çok sayı varsa))*/

  else return Binary(n,middle+1,last,src);/*eğer aradığımız değer orta index değerinden büyükse ortadakinin bir fazlasından başlayıp dizinin son indexine kadar olan bölüme geçiyoruz*/

  }
   return -1;  // eğer aradığımız değer yoksa -1 değerini döndürüyoruz.
}

Birde elemanın teki bunu while döngüsü ile yapmış. Onuda atayım belki lazım olur.

Burda bilmediğimiz bir takım kodlar olabilir comparable vs gibi ; Comparable bir super classdır, içinde compareTo gibi methodları barındırır. Bir çeşit sıralama işlemi yapar. İnternetten kullanımını rahatlıkla bulabilirsiniz.

Evet gençler searching algoritmalarımız bu kadardı. Bir sonraki derste görüşmek üzere. Öpüyorum..

Algoritma - Recursive algorithm

Naber yapraam nasılsın? benim durum aynı değişen bişi yok. Sıradan amk. Kafamı bulandırıp derslerimi engellediği için içkide içmiyorum artık. Bakalım sonumuz nolucak

Bugün yapraam sana Recursive(özyinelemeli) algoritma türünden bahsedicem. Recursive algoritmalar, halletmesi gereken işleri bölebileceği en küçük parçaya kadar bölüp sonra tekrardan toplayan algoritmalardır. Şimdi tabi pek bişey anlamamış olabilirsin. Ama anlıcaksın yapraam merak etme.

Recursive mantığı methodun içinde tekrardan kendisini çağırmasından ibarettir. Basit bir örnek vermek gerekirse;

Misal 1'den 4'e kadar olan sayıları toplatan bir algoritma yazalım. Bunu for döngüsüyle rahatlıkla yazabiliriz. Eğer bu şekilde yaparsak iterative olur. Peki recursive ile nasıl yaparız.

Önce fikir sahibi olmanız açısından bir çizimim var. Daha sonrada örnek kodu koyucam;

Şimdi napıyoruz burda ?
      girilen değer '1' olana kadar hep method içinde sayının 1 eksiğiyle methodu tekrardan çağırıyoruz. n değerimi 1 olduğu zamanda toplayarak sayıları ilk methodumuza kadar geri döndürüyoruz.

Şimdide içerdeki gerekli kodları gireyim.

Public Static Void main(String args[]){

  int x = Sum(4);  // Methodumuzu çağırıyoruz

  println(“Sum: ” + x); // Sonrada methodumuzdan dönen değeri(1+2+3+4) yazdırıyoruz.

} /* end-main */

Peki methodun içinde ne var ?

Static int Sum(int n){

  int partialSum = 0; // teker teker sayıları toplayacağımız integer, değişken

  if (n == 1) return 1; // eğer sayı 1 ise toplayarak dönmeye başla

  partialSum = Sum(n-1);// burda n değerimiz 1 olana kadar sayımızı 1 azaltarak method içinde                                                  //method çağırıyoruz

  return partialSum + n; // en son method(n'in 1 olduğu)'dan başlayarak toplaya toplaya ilk                                       //methodumuza dönüyoruz. eğer ilk methoddaysak değeri main methoda döndürüyoruz

}

Bilmem anlatabildim mi yapraam? okadar uğraştım resim fln çizdim amk. sizde biraz anlamaya çalışın.

Neyse genel mantık olarak recursive algoritması budur. Arkadaşlar, dostlar, gardaşlar, Recursive algoritması son derece güçlü ve hızlı bir türdür, bir çok sıkıntılı durumda hayat kurtarır bu yüzden bu algoritma türünü iyi irdelemeniz lazım. Bunun için bir kaç örnek daha yazıcam buraya. Ama bu sefer resim fln çizemem amk. Sadece mantığını yazıp örnek kodu koyucam.

İlk örneğimiz bir değerin kuvvetini yazdıran bir recursive algoritma olsun. 

Önce işin mantığını kavrayalım. Algoritmamız napıcak ? girilen değeleri önce en ilk kuvvet olan 1'e kadar açıcak ondan sonrada sayıyı çarpa çarpa geri döndürücek. Eğer sayının kuvveti 0 ise 1 değerini geri döndürücek.

Main method yazmama gerek olmadığını düşünüyorum.

double Power(double a, int n){

  double partialResult; // yine tabi parçalı bir sonuç değişkeni koyalım. teker teker çarpması için

  if (n == 0) return 1; // eğer sayımızın kuvveti 0 ise 1 değerini döndür

  else if (n == 1) return a; // eğer sayımızın kuvveti 1 ise sayımızı döndür.

  partialResult = Power(a, n-1); // işte burda methodu çağırıyoruz. n değeri 1 olana kadar method //içinde tekrar tekrar method açıyor ve sonunda n 1 olunca sayımızı döndürmeye başlıyor.

//dönen sayıyıda parçalı çarpım işlemimize eşitliyor.

  return partialResult*a;  // son olarakda sayımızla parçalı çarpımımızı kuvvet kadar çarpıp methodları

çarparak teker teker kapatıyor. ve geri döndürüyor.

}

Kapiş ? Bence anladın yapraam. Sadece biraz daha dikkatli incelemen gerekiyor.

Son örneğimizde fibonacci sayılarından gelsin madem amk.

Fibonacci sayıları bildiğiniz gibi bir sayı dizisidir, ama nasıl bir sayı dizisidir, bir sayının kendinden 

önceki sayıyla toplamının kendinden sonraki sayıya eşit olduğu bir sayı dizisidir. Yani;

0,1,1,2,3,5,8,13 ... diye giden sayı dizileri işte

Örneğin 40. fibonacci sayısını bulan bir algoritma yazalım. 

ilk iki örnek için ne var bunda amk ben bunu for döngüsüyle flnda 2 dakkada yazarım fln diyebilirsin.

Hadi yapraam yiyosa bunu yaz forla amk. Bunda sike sike recursive algoritma kullanman gerekli.

Neyse gelelim methodumuza, Ne demiştik? fibonacci dizisinde bir sayı kendisinden önceki 2 sayının toplamına eşittir dimi. Genel mantık olarak bunu alırsak çok rahat bir şekilde işin içinden çıkarız.

int Fibonacci(int n){

  if (n == 0) return 0; // eğer n değeri 0 ise hiç kurcalama n değerini döndür.

  if (n == 1) return 1; // eğer değerimiz 1 ise  1 döndürerek bir üstteki methoda çık

  return Fibonacci(n-1) + Fibonacci(n-2); /* şimdi genç bu bölümü iyi kavraman lazım gördüğün gibi burda 2 defa method çağırıyor. Önce değer 1 olana kadar n sayısını küçültüyor. n sayısı 1 olduktan sonra 1 değerini döndürüp n'in 2 olduğu bir üst methoda çıkıyor. sonra ikinci duruma geçiyor yani Fibonacci(n-2) durumuna. Burdada n = 2'ydi n-2'den 0 değeryile yine bir alt methoda iniyor. ordan 0 değeriyle geri dönüyor ve sonuçta 1 + 0  değerini alıp bir üst duruma geçiyor ve aynı işlemleri tekrarlıyor. */

} 

İnşallah anlatabilmişimdir. Biz 40. fibonacci sayısını istediğimiz için toplamda 300.000.000'dan fazla kez işlem yapılır. 

Bu recursive muhabbetini şimdilik burda bitiriyorum. Bir sonraki yazımdada yine recursivden faydalanarak linear ve binary searh algoritmalarından bahsedicem. Sizleri öpüyorum. Kendinize iyi bakın. Banada sevabına bi manita ayarlayın ya.

Algoritma - Sorting

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...

Algoritma- Running time ve notasyon

   Sevgili yaprak. Yaptığım hesaba göre biram bitmeden bu konuyuda aradan çıkartırım heralde. Zaten benimde sıkıntı yaşadığım bi konuydu burda tekrar üzerinden geçerim iyi olur bence amk.
   Saat gecenin 2.20si ve aşırı uykum olduğu için doğrudan konuya giriyorum amk.(Bide yarın eskişehire gidicem amk. Uyumam lazım yani )
   Neyse Running time konudanda anlayacağınız gibi programın ne kadar çalışacağı sorusunu cevaplar. Şimdilik running time için bukadar yeterli bence.
   Big O Notation dediğidimiz o notasyonu ise, Kendi yazdığımız kodların. hazır olan algoritmaların veya işlevsel operasyonların(linked list vs.) karşılaştırılmasında kullanılır ve önemli olabilecek düzeydedir.
       Big O bi çeşit gösterim türüdür, Bunun çeşitli türevleride vardır: O , θ, Ω notasyonları
Bu notasyonlar arasına çeşitli farklılıklar vardır kısaca:
                                                                      -Big O üst sınır(algoritmanının çalışacağı en kötü durum)
                                                                      -Big θ ortalama durum
                                                                      -Big Ω alt sınır(algoritmanın çalışacağı en iyi durum)
Bu türler içinde genelde bigO notasyonunu kullanacağımız için diğerlerini bu düzeyde bilmemiz yeterlidir. gelelim big O notasyonuna;
Şimdi gençler big O notasyonu dediğim gibi en kötü durum için geçerlidir yani örneğin 1,2,3,4,5,6 elemanlarının olduğu bir dizide get methodunu çalıştırırsak bu kod sike sike en kötü durumu çalıştırır çünkü 6 en son elemanldır ve dizinin içine girebileceği en fazla miktarda girecektir kapiş?
Şu running time meselesini biraz daha ayrıntılı inceleyelimde kafalarda soru işareti kalmasın amk.
Aşağıda vereceğim kodun running time durumuna bir bakalım;
     int sum(int A[],int N){
       int sum = 0;                        ----> 1 kez çalışır
        for (int i=0;i <N,i++({      -----> N  kez çalışır                  Yandaki metod görüleceği üzere
            sum += A[i];                 -----> N kez çalışır                    2N+2 kez çalışır. bu metodun
               }                                                                                   running time'ıdır.
return sum;                               ------> 1 kez çalışır.                  T(N) = 2N+2 ile gösterilir.
}
Yukarıdaki metod için ;
                                          En iyi çalışma süresi (Best case) = N 1 olursa 2*1+2= 4
                                          Ortalama çalışma süresi(average case) =  2N/2+2 = N+2
                                          En kötü çalışma süresi(Worst case) = 2N+2
Genel çalışma prensibi budur.
Aklınızın bir köşesinde bulunmasını istediğim bir diğer nokta;
             iç içe 2 döngü varsa ve ikiside N'e kadar sürüyorsa kod n2 kadar çalışır eğer üç tane döngü olursa iç içe ozaman n3 kadar çalışır. Ne bilim belki lazım olur. belirteyim dedim.

Şimdi yapraam tekrardan notasyon konusuna dönmek istiyorum. Bu arada kişisel gelişiminiz için bu videoyada bakmanıza fayda var http://www.youtube.com/watch?v=gjRc8QwsR8k

Neyse Big O notation dediğimiz en kötü durumu gösteren notasyon türünün mantığı şudur genel gösterim O(N) veya O(n2) veya O(1) vs vs.. türlerindedir ama asla O(2+N) veya O(2N) şekillerinde gösterilmez. Nedenini sormayın amk notasyon gösterim prensibi bu.
Örneğim bir kaç metoddan oluşan bir kod dizimiz var ve ;
                                                                                                1. metod 1 kere
                                                                                                2.  metod N kere
                                                                                                3. metod n2 kere
                                                                                                4. metod 2n2 kere çalışıyor.
Ozaman bu kodun notasyonu O(n2) 'dir kuvveti en büyük olanı notasyonun içine yazarız. N ile birlikte sabit sayı koymayız
Notasyonun genel mantığı budur.
Genel notasyon gösterim türleri ve hiyerarşisine gelecek olursak;
İsim                           Gösterim
Sabit ===========> O(1)
LOG LOG =======> O(loglogN)  -> Tahminsel arama
Logaritmik =======> O(LogN) -> iyi arama algoritmalarının tipik zamanı
Doğrusal =========> O(N) ->N tane veriyi girmek için gereken zaman
N LOG N ========> O(NlogN) -> Çoğu sıralama algoritması
Karesel =========> O(n2) -> veri miktarı azsa

hiyerarşiye gelicek olursak => O(n2) > O(n log n) > O(n) > O(log n) > O(1)
Şimdide güzel bir örnekle bu konuyu kapatalım (Şimdilik)
for(i = 0 ; i< n ; i++ ){
 mesaj = "Yapraam" + i; // n kere O(1)
}
// Ara sonuç:  O(n)
mesaj = "Merhaba yapraam"; // O(1)
int x = 10; // O(1)
// Ara sonuç: O(n) + 2*O(1)

for(i = 0 ; i< n ; i++ ){

 mesaj = "Merhaba"; // O(1)
 mesaj = "Yapraam" + i; // O(1)
 // n kere 2*O(1)
}
// Ara sonuç: O(n) + 2*O(1) + 2*O(n)
// Ara sonuç: 3*O(n) + 2*O(1)
// Sonuç: O(n)

Yapraklarım notasyon ve running time meselesi kabataslak bu şekildedir. İlerleyen zamanlarda daha ayrıntılı giriş yapıcam merak etmeyin.

Algoritma - Giriş

    Evet yapraam bu ders nispeten diğer derslere göre daha ilgimi çekio. en azından bölümle programlamayla ilgili. AMA bu dersin boktan,zor ve aynı zamanda ingilizce olduğu gerçeğini değiştirmiyor. tabi.
   Bu arada blog yazarken bira içmeye karar verdim. Kenardanda müzik çalıyor. Yani güzel bir ortam olmaya başladı.Balkonda bi sigara içeyimde devam edelim.
   Neyse konuya gireyim amk. Eğer kaliteli bir yazılımcı olmak istiyorsan bu algoritma muhabbetini iyi kavraman gerekiyor. Neden diye soracak olursan cevabı açık;
   Programlama dillerinde bir kod bölümü yazdığın zaman bunların pc içinde ne kadar sürede işleneceği çok önemlidir. Götün kalkmasın senin kıçı kırık başlangıç düzeyindeki kodlarından bahsetmiyorum. eğer ilerde büyük çaplı uygulamalara girişirsen önemlidir.  Peki neden önemlidir?
   Şundan önemlidir. Bir uygulama  çalıştığı zaman atıyorum 2 saniyede çalışmasıyla 5 saniyede çalışması arasında büyük fark vardır (Bu saniyeleri daha sonra running time konusunu yazarken anlatıcam neyse). Eğer kodun 5 saniyede çalışırsa programın YAVAŞ damgası yer ve zamanın hızlı gençlerinin ilgisini çekmez.İşte algoritmalar bu yüzden önemlidir. Yazdığın programın pcyi kasmıcak şekilde hızlı çalışması konusunda sana yardımcı olurlar.

Algoritma konusu için bukadar giriş yeter.
Bu arada;
http://www.youtube.com/watch?v=LgDQMm1blno  bu videonun hangi korku filminden olduğunu bilen biri yazarsa iyi olur ya. korku filmlerini severim.

Günün meselesi

        Carpe-diem bi hayat felsefesinden (neredeyse) asosyal olan pc mühendisliği hayatına geçmek her gün aynı düzeyde acıtıo mını sikim. Ama sike sike bu amk bölümünü okumam gerekio. Çünkü okuyup başarılı olamazsam çok daha boktan ve sıkınıcı bi hayatın beni beklediği açık yani.
     Herneyse pc mühendisliği öle okuyayım anlayayım yapayım tarzı bi bölüm değil. Anlamak için extra dediğimiz şeylerden yapmak gerekio. Bende öğrendiğim konuyu burda sanki birine anlatıyomuşcasına tekrar yazmaya karar verdim. Hem belki birilerinede faydam olur amk.

      Adaletine sokim içki içip bişeyler yapmak varken nelerle uğraşıyorum...