Yazar admin

Programlamanın temellerinden olan Algoritma kavramı ve konuları üzerine yayımladığımız makale serimize devam ediyoruz.
Bu bölümümüzde "Sıralama Algoritmaları"nı ele alacak, örneklerle detaylandırmaya çalışacağız.

---

Bilgisayar yazılım uygulamalarında ve sayısal sistem çözümlerinde verilerin sıralı olması bilgiyi kullanacak programlara ait algoritmaların gerçekleştirilmesini kolaylaştırır ve işlemin hızını artırır.

Çok değişik sıralama algoritmaları vardır. Seçilen veri modeli, kümedeki toplam veri sayısı, bilgilerin geliş sırası kullanılacak sıralama algoritmasını belirler. Sıralama algoritmaları şunlardır:

1. Araya sokma sıralaması (insertion)
2. Seçmeli sıralama (selection)
3. Kabarcık sıralaması (bubble)
4. Birleşmeli sıralama (merge)
5. Kümeleme sıralaması (heap)
6. Hızlı sıralama (quick)

Sıralama işlemi belirli bir bilgi parçasına dayanılarak yapılır.Bu bilgi parçasına anahtar sözcük(keyword) denir ve bu bir sayı olabileceği gibi sözcük ya da herikisi birden olabilir. Örnek:
Anahtar sözcük: soyad
Veysel Altın ………..Ali Bindal…………Sema Hal…………Yahya Kamil
20 17 18 25

Harici sıralama(external sorting): Sıralama işlemi disk disket gibi saklama birimlerinde tutulan dosyalar üzerinde yapılıyorsa verilen addır.

Dahili sıralama(internal sorting): Sıralama işlemi bellekte yapılıyorsa dahili olarak adlandırılır.

Dizinli dosya yapısı(indexed file structure): Uygulamada çok büyük boyutlu veriler dizinli dosyalarda tutulur. Dizinli dosyalarda rastgele gelen veriler belirli bir anahtar sözcüğe göre iç bellekte bir dizin tablosunda sıralı olarak tutulur. Sıralı bilgilere ulaşılacağı zaman bu dizin tablosundan kayıt numarası öğrenilerek dosya içindeki bilgiye doğrudan erişilir.

Sıralama algoritması Uygulandığı veri modeli Uygun bellek ortamı

1-Araya sokma sıralaması (insertion) bağlantılı liste,dizi dahili
2-Seçmeli sıralama (selection) Dizi,bağlantılı liste dahili,harici
3-Kabarcık sıralaması (bubble) dizi,bağlantılı liste dahili
4-Birleşmeli sıralama (merge) dizi,bağlantılı liste,liste dahili,harici
5-Kümeleme sıralaması (heap) bağlantılı liste,liste dahili
6-Hızlı sıralama (quick) dizi,ağaç dahili

Sıralama algoritmaları veri modellerine göre farklılık gösterirler. Genel olarak çok fazla yer değiştirme işlemine gereksinim duyan sıralama algoritmalarında uygun bellek ortamı dahilidir denebilir.

1-Araya sokma sıralaması (insertion): Dizi iki parça gibi düşünülür
a) Sıralı olan kısım ve
b) Henüz sıralanmamış olan kısım.

Sıralanmamış kısımdan elemanlar alınarak sıralı kısımda uygun yerde araya sokulur. Dolayısıyla bir kaydırma işlemi söz konusudur, tüm elemanlar yerlerinden kayacakları için harici sıralama uygun değildir.
Örnek:
Sıralanacak dizi: 7 3 5 8 2
Başlangıç durumu: [7] 3 5 8 2

1.Adım : [7 3] 5 8 2 [3 7] 5 8 2
2.Adım : [3 7 5] 8 2 [3 5 7] 8 2
3.Adım : [3 5 7 8] 2 [3 5 7 8] 2
4.Adım : [3 5 7 8 2] [2 3 5 7 8]

Çözüm 1:
1. başla
2. I=1
3. A(I) gir
4. if I=N ise 6.adıma git
5. I=I+1 ve 3.adıma git
6. K=1, I=1, B=0
7. if A(I)
8. B=A(I) A(I)=A(I+1) A(I+1)=B
9. I=I-1
10. if I=0 12.adıma git
11. 7.adıma git
12. K=K+1 I=K
13. if K=N-1 15.adıma git
14. 7.adıma git
15. I=1
16. A(I) yaz
17. if I=N ise 19.adıma git
18. I=I+1 16.adıma git
19. dur

Çözüm 2:
1. Başla
2. I=1 K=1
3. if A(I)
4. B=A(I) A(I)=A(I+1) A(I+1)=B K=0
5. if I=N-1 7.adıma git
6. I=I+1 ve 3.adıma git
7. if K=0 2.adıma git
8. I=1
9. A(I) yaz
10. if I=N 12.adıma git
11. I=I+1 ve 9.adıma git
12. dur

2-Seçmeli sıralama (selection):

Örnek 1:
Sıralanacak dizi: 7 3 5 8 2
Başlangıç durumu: [7] 3 5 8 2

1.Adım : 7 3 5 8 2 [2 ] 3 5 8 7 2 ile 7 yer değiştirdi
2.Adım : [2] 3 5 8 7 [2 3 ] 5 8 7 -
3.Adım : [2 3] 5 8 7 [2 3 5] 8 7 -
4.Adım : [2 3 5] 8 7 [2 3 5 7 ] 8 8 ile 7 yer değiştirdi
5.Adım : [2 3 5 7] 8 [2 3 5 7 8 ] son

Çözüm:
1. başla
2. I=1
3. A(I) gir
4. if I=N 6.adıma git
5. I=I+1 ve 3.adıma git
6. I=1, K=1, M=1
7. M=I EK=A(I) I=0
8. if EK
9. EK=A(I+1) K=I+1 J=1
10. I=I+1
11. if I=N 13.adıma git
12. 8.adıma git
13. if J=0 15.adıma git
14. A(K)=A(M) A(M)=EK
15. M=M+1
16. if M=N 18.adıma git
17. 7.adıma git
18. I=1
19. A(I) yaz
20. if I=N ise 22.adıma git
21. I=I+1 ve 19.adıma git
22. dur

Örnek 2:
Sıralanacak dizi: 23 18 42 7 57 38
Başlangıç durumu: [23] 18 42 7 57 38

1.Adım: 23 18 42 7 57 38 en küçük eleman A(4)=7
A(1) ile A(4) yer değiştirir
2.Adım: 7 18 42 23 57 38 en küçük eleman A(2)=18
Yerinde kalır
3.Adım: 7 18 42 23 57 38 en küçük eleman A(4)=23
A(3) ile A(4) yer değiştirir
4.Adım: 7 18 23 42 57 38 en küçük eleman A(6)=38
A(4) ile A(6) yer değiştirir
5.Adım: 7 18 23 38 57 42 en küçük eleman A(6)=42
A(5) ile A(6) yer değiştirir
6.Adım: 7 18 23 38 42 57 6.ve dizinin son elemanı
Yerinde kalır.

Bir sonraki makale konumuz "ARAMA ALGORİTMALARI"dır.