Azərbaycanca
Deutsch
日本語
Lietuvos
සිංහල
Türkçe
Українська
United State
Sıralama algoritması, bilgisayar bilimlerinde ya da matematikte kullanılan, verilen bir listenin elemanlarını belirli bir sıraya sokan algoritmadır. En çok kullanılan sıralama türleri, sayı büyüklüğüne göre sıralama ve alfabetik sıralamadır. Sıralama işleminin verimli yapılması, arama ve birleştirme algoritmaları gibi çalışması için sıralanmış dizilere gereksinim duyan algoritmaların başarımının yüksek olması için önemlidir. Sıralama algoritmaları bilgisayarlarda tutulan verilerin düzenlenmesini ve insan kullanıcı tarafından daha rahat algılanmasını da sağlar.
Sıralama algoritmaları, tanımı çok yalın olmasına karşın çözümü çok karmaşık olan bir işi gerçekleştirdikleri için, üzerinde en fazla araştırma yapılan bilgisayar bilimi konularından biridir. Çoğu kişi sıralama sorununu çözülmüş bir sorun olarak görse de, yeni sıralama algoritmaları üzerinde araştırmalar sürmektedir. Örneğin kütüphane sıralaması ilk olarak 2004 yılında ortaya atılmıştır. Sıralama algoritmaları, sayılarının çok olması ve değişik yaklaşımlar sunmaları nedeniyle özellikle giriş düzeyindeki bilgisayar bilimleri derslerinde büyük O gösterimi ve veri yapıları gibi temel algoritma kavramlarının açıklanması amacıyla yaygın biçimde kullanılırlar.
Sıralama Algoritmaları
Bilgisayar bilimlerinde kullanılan sıralama algoritmaları genellikle aşağıdaki ölçütlere göre sınıflandırılır:
- Hesaplama karmaşıklığı: Dizideki öğelerin karşılaştırılmasının en iyi, ortalama ve en kötü başarımının dizinin boyutu (n) cinsinden gösterilmiş halidir. Olağan uygulamalarda sıralama algoritmalarının iyi durum başarımı O(n log n) ve kötü durum başarımı ise Ω(n²)'dir. Bir sıralama algoritmasının istenen karmaşıklığı O(n)'dir. Yalnızca soyut bir anahtar karşılaştırması yapan bütün sıralama algoritmaları en kötü durumda her zaman Ω(n log n) karşılaştırma yaparlar.
- Yer Değiştirme Karmaşıklığı (yerinde sıralama algoritmaları için).
- Bellek (ve diğer donanım kaynaklarının) Kullanımı: Bazı sıralama algoritmaları dizinin içerdiği öğelerin dizinin saklandığı alanda sıralar. Böylece sıralanan öğeler dışında yalnızca O(1) ya da O(log n)'lik bir ek bellek alanı gerekir. Bazı algoritmalar ise verinin geçici olarak saklanması için dizinin tutulduğu alanın dışında ek bellek alanlarına gereksinim duyar.
- Özyineleme: Bazı algoritmalar ya özyinelemeli ya da özyinelemesiz çalışırken, birleştirmeli sıralama gibi bazı algoritmalar iki biçimde de uygulanabilir
- Kararlılık
- Kaşılaştırma sıralaması olup olmama: Bir karşılaştırma sıralaması sıralanacak veriyi, bir karşılaştırma işlemi kullanarak, karşılaştırarak inceler.
- Genel Yöntem: Araya sokma, değiştirme, seçme, birleştirme vb. Değiştirme sıralamalarına kabarcık sıralaması ve hızlı sıralama örnek olarak gösterilebilir. Yığın sıralaması ise seçme sıralamalarındandır.
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. Başka bir deyişle, bir sıralama algoritması kararlı olduğunda, eğer R ve S gibi içerdiği değer aynı olan iki öğe bulunduran asıl dizide, R, S' den önce geliyorsa, sıralanmış dizide de R, S'den önce olur.
Dizinin içinde birbirine eşit değerler içeren öğeler birbirlerinden ayırt edilemiyorsa (örneğin sayılar ya da harfler gibi değerler öğenin kendisini oluşturuyor ise) kararlılık bir sorun değildir. Ancak aşağıda gösterildiği gibi sayı çiftleri, her çiftin virgülden önceki sayısına göre sıralanacağı düşünülürse kararlılık sorunu ortaya çıkar.
(4, 1) (3, 7) (3, 1) (5, 6)
Bu durumda, 2 değişik sonuç mümkündür; ilk çözüm sıralama anahtarlarının değerleri aynı olan öğelerinin sırasını korur, ikincisi ise korumaz:
(3, 7) (3, 1) (4, 1) (5, 6) (sıra korunmuş) (3, 1) (3, 7) (4, 1) (5, 6) (sıra değişmiş)
Kararsız sıralama algoritmaları sıralama anahtarlarının değerleri aynı olan öğelerin dizi içindeki sırasını değiştirebilir ancak kararlı sıralama algoritmaları asla değiştirmez. Kararsız sıralama algoritmaları özellikle kararlı olacak biçimde uygulanabilir. Bunu yapmanın bir yolu yapay olarak anahtar karşılaştırmasını anahtarlarının değerleri birbirine eşit olan iki öğenin durumunu belirlemek için asıl listedeki konumlarını ölçüt olarak kullanacak biçimde genişletmektir. Ancak asıl dizideki öğe sırasının hatırlanması çoğu zaman ek saklama alanı gerektirir.
Sıralama Algoritmalarının Listesi
Aşağıdaki tablolarda n dizideki sıralanacak olan eleman sayısını gösterir. "Ortalama" ve "En Kötü" kolonları ilgili durumlardaki karmaşıklığı, "Bellek" kolonu ise listenin sıralanabilmesi için listenin bellekte kapladığı alandan ne kadar daha fazla saklama alanı gerektiğini gösterir.
Karşılaştırma ile Sıralayan Sıralama Algoritmaları
| Adı | Ortalama | En Kötü | Bellek | Kararlı mı? | Yöntem | Diğer Açıklamalar | |
|---|---|---|---|---|---|---|---|
| Kabarcık Sıralaması | — | O(n²) | O(1) | Evet | Değiştirme | ||
| Kokteyl Sıralaması | — | O(n²) | O(1) | Evet | Değiştirme | ||
| Tarak Sıralaması | O(n log n) | O(n log n) | O(1) | Hayır | Değiştirme | Küçük boyutta kodla uygulanabilir | |
| Cüce Sıralaması | — | O(n²) | O(1) | Evet | Değiştirme | ||
| Seçmeli Sıralama | O(n²) | O(n²) | O(1) | Hayır | Seçme | Kararlı bir sıralama olarak uygulanabilir | |
| Eklemeli Sıralama | O(n + d) | O(n²) | O(1) | Evet | Ekleme | d ters çevirme sayısıdır ve O(n²)'dir | |
| Shell Sıralaması | — | O(n log² n) | O(1) | Hayır | Ekleme | ||
| Ağaç Sıralaması | O(n log n) | O(n log n) | O(n) | Evet | Ekleme | Kendini dengeleyen bir ikili arama ağacında kullanıldığında | |
| Kütüphane Sıralaması | O(n log n) | O(n²) | O(n) | Evet | Ekleme | ||
| Birleştirmeli Sıralama | O(n log n) | O(n log n) | O(n) | Evet | Birleştirme | ||
| Yerinde Birleştirmeli Sıralama | O(n log n) | O(n log n) | O(1) | Evet | Birleştirme | Örnek uygulamasını gösteren sayfa: [1] | |
| Yığın Sıralaması | O(n log n) | O(n log n) | O(1) | Hayır | Seçme | ||
| Rahat Sıralama | — | O(n log n) | O(1) | Hayır | Seçme | ||
| Hızlı Sıralama | O(n log n) | O(n²) | O(log n) | Hayır | Bölümlendirme | Yalın uygulamaları O(n) kadar bir alan kullanır; ortada bir pivot kullanılırsa en kötü durumda O(n log n) olabilir | |
| İçgözlemle Sıralama | O(n log n) | O(n log n) | O(log n) | Hayır | Melez | Standart Şablon Kütüphanelerinin çoğunda kullanılır | |
| Sabır Sıralaması | — | O(n²) | O(n) | Hayır | Ekleme | O(n log n) zamanda bütün en uzun artan altdizileri bulur | |
| İplik Sıralaması | O(n log n) | O(n²) | O(n) | Evet | Seçme |
Karşılaştırmadan Sıralayan Sıralama Algoritmaları
Aşağıdaki tablo karşılaştırma kullanmadan sıralama yapan sıralama algoritmalarını göstermektedir. Bu algoritmalar karşılaştırma yapmadıkları için karmaşıklıklarınınO(n log n) gibi bir alt sınırı yoktur. Tabloda gösterilen karmaşıklıklar sıralanacak listedeki eleman sayısı (n), her bir anahtarın boyutu (k) ve uygulama tarafından kullanılan parça boyutu (k) cinsiden yazılmıştır. Algoritmaların pek çoğu anahtar boyutunun bütün satırlarda özgün anahtar değerleri olmasını sağlayacak kadar büyük ve n << 2k ('<<' = "çok daha küçük") olduğunu varsayar.
| Adı | Ortalama | En Kötü | Bellek | Kararlı mı? | n << 2k ? | Diğer Açıklamalar |
|---|---|---|---|---|---|---|
| Güvercin Yuvası Sıralaması | O(n+2k) | O(n+2k) | O(2k) | Evet | Evet | |
| Kova Sıralaması | O(n•k) | O(n²•k) | O(n•k) | Evet | Hayır | Elemanların dizide düzenli olarak dağıldığını varsayar. |
| Sayarak Sıralama | O(n+2k) | O(n+2k) | O(n+2k) | Evet | Evet | |
| En anlamsız Basamağa göre sıralama | O(n•k/s) | O(n•k/s) | O(n) | Evet | Hayır | |
| En anlamlı Basamağa göre sıralama | O(n•k/s) | O(n•(k/s)•2s) | O((k/s)•2s) | Hayır | Hayır | |
| O(n•k/log(n)) | O(n•(k - log(n)).5) | O(n) | Hayır | Hayır | Asimtotlar n << 2k varsayımına dayanır, ancak algoritmanın buna gereksinimi yoktur. |
Verimsiz Sıralama Algoritmaları
Aşağıdaki tablo çok verimsiz oldukları ya da özel bir donanım gerektirdikleri için gerçek hayatta kullanılması olumlu sonuçlar vermeyecek sıralama algoritmalarını göstermektedir.
| Adı | Ortalama | En Kötü | Bellek | Kararlı mı? | Karşılaştırma sıralaması mı? | Diğer Açıklamalar |
|---|---|---|---|---|---|---|
| Saçma sıralama | O(n × n!) | ∞ | O(1) | Hayır | Evet | Knuth karıştırması kullanılarak ortalama zamanı |
| (Rastgele değiştirmeli sıralama) | O(n × n!) | ∞ | O(1) | Hayır | Evet | Ortalama zamanı sonuşmayan biçimde saçma sıralamanın yarısıdır |
| O(n2.71) | O(n2.71) | O(log n) | Hayır | Evet | ||
| N/A | N/A | — | N/A | Hayır | Özel donanım gerektirir | |
| O(n) | O(n) | O(log n) | Hayır | Evet | Sayı, yapılan değişiklik sayısıdır | |
| O(log n) | O(log n) | O(n•log n) | Evet | Hayır | O(n•log n) boyutunda özel bir devre gerektirir |
Ayrıca bakınız
Dış bağlantılar
- Ardışık ve koşut sıralama algoritmaları13 Aralık 2012 tarihinde Wayback Machine sitesinde .
- Ricardo Baeza-Yates'in sıralama algoritmaları sayfası14 Mart 2008 tarihinde Wayback Machine sitesinde .
- 'Algoritmalar sözlüğü, veri yapıları ve sorular'24 Haziran 2005 tarihinde Wayback Machine sitesinde .
- Slightly Skeptical View on Sorting Algorithms22 Ekim 2012 tarihinde Wayback Machine sitesinde .
- Sorting Revisited15 Nisan 2008 tarihinde Wayback Machine sitesinde .
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Siralama algoritmasi bilgisayar bilimlerinde ya da matematikte kullanilan verilen bir listenin elemanlarini belirli bir siraya sokan algoritmadir En cok kullanilan siralama turleri sayi buyuklugune gore siralama ve alfabetik siralamadir Siralama isleminin verimli yapilmasi arama ve birlestirme algoritmalari gibi calismasi icin siralanmis dizilere gereksinim duyan algoritmalarin basariminin yuksek olmasi icin onemlidir Siralama algoritmalari bilgisayarlarda tutulan verilerin duzenlenmesini ve insan kullanici tarafindan daha rahat algilanmasini da saglar Yigin Siralamasi nin rastgele uretilmis sayilari nasil siraladigini gosteren ornek Algoritmanin ilk asamasinda dizinin ogeleri yigin yapisini olusturmak icin yeniden duzenlenir Siralama algoritmalari tanimi cok yalin olmasina karsin cozumu cok karmasik olan bir isi gerceklestirdikleri icin uzerinde en fazla arastirma yapilan bilgisayar bilimi konularindan biridir Cogu kisi siralama sorununu cozulmus bir sorun olarak gorse de yeni siralama algoritmalari uzerinde arastirmalar surmektedir Ornegin kutuphane siralamasi ilk olarak 2004 yilinda ortaya atilmistir Siralama algoritmalari sayilarinin cok olmasi ve degisik yaklasimlar sunmalari nedeniyle ozellikle giris duzeyindeki bilgisayar bilimleri derslerinde buyuk O gosterimi ve veri yapilari gibi temel algoritma kavramlarinin aciklanmasi amaciyla yaygin bicimde kullanilirlar Siralama AlgoritmalariBirlestirmeli siralama nin rastgele uretilmis sayilari gosteren noktalari nasil siraladigini gosteren ornek Bilgisayar bilimlerinde kullanilan siralama algoritmalari genellikle asagidaki olcutlere gore siniflandirilir Hesaplama karmasikligi Dizideki ogelerin karsilastirilmasinin en iyi ortalama ve en kotu basariminin dizinin boyutu n cinsinden gosterilmis halidir Olagan uygulamalarda siralama algoritmalarinin iyi durum basarimi O n log n ve kotu durum basarimi ise W n dir Bir siralama algoritmasinin istenen karmasikligi O n dir Yalnizca soyut bir anahtar karsilastirmasi yapan butun siralama algoritmalari en kotu durumda her zaman W n log n karsilastirma yaparlar Yer Degistirme Karmasikligi yerinde siralama algoritmalari icin Bellek ve diger donanim kaynaklarinin Kullanimi Bazi siralama algoritmalari dizinin icerdigi ogelerin dizinin saklandigi alanda siralar Boylece siralanan ogeler disinda yalnizca O 1 ya da O log n lik bir ek bellek alani gerekir Bazi algoritmalar ise verinin gecici olarak saklanmasi icin dizinin tutuldugu alanin disinda ek bellek alanlarina gereksinim duyar Ozyineleme Bazi algoritmalar ya ozyinelemeli ya da ozyinelemesiz calisirken birlestirmeli siralama gibi bazi algoritmalar iki bicimde de uygulanabilir Kararlilik Kasilastirma siralamasi olup olmama Bir karsilastirma siralamasi siralanacak veriyi bir karsilastirma islemi kullanarak karsilastirarak inceler Genel Yontem Araya sokma degistirme secme birlestirme vb Degistirme siralamalarina kabarcik siralamasi ve hizli siralama ornek olarak gosterilebilir Yigin siralamasi ise secme siralamalarindandir Kararlilik Kararli siralama algoritmalari siralanacak dizinin icinde degerleri birbirine esit olan ogelerin birbirlerine gore olan konumlarini korur Baska bir deyisle bir siralama algoritmasi kararli oldugunda eger R ve S gibi icerdigi deger ayni olan iki oge bulunduran asil dizide R S den once geliyorsa siralanmis dizide de R S den once olur Dizinin icinde birbirine esit degerler iceren ogeler birbirlerinden ayirt edilemiyorsa ornegin sayilar ya da harfler gibi degerler ogenin kendisini olusturuyor ise kararlilik bir sorun degildir Ancak asagida gosterildigi gibi sayi ciftleri her ciftin virgulden onceki sayisina gore siralanacagi dusunulurse kararlilik sorunu ortaya cikar 4 1 3 7 3 1 5 6 Bu durumda 2 degisik sonuc mumkundur ilk cozum siralama anahtarlarinin degerleri ayni olan ogelerinin sirasini korur ikincisi ise korumaz 3 7 3 1 4 1 5 6 sira korunmus 3 1 3 7 4 1 5 6 sira degismis Kararsiz siralama algoritmalari siralama anahtarlarinin degerleri ayni olan ogelerin dizi icindeki sirasini degistirebilir ancak kararli siralama algoritmalari asla degistirmez Kararsiz siralama algoritmalari ozellikle kararli olacak bicimde uygulanabilir Bunu yapmanin bir yolu yapay olarak anahtar karsilastirmasini anahtarlarinin degerleri birbirine esit olan iki ogenin durumunu belirlemek icin asil listedeki konumlarini olcut olarak kullanacak bicimde genisletmektir Ancak asil dizideki oge sirasinin hatirlanmasi cogu zaman ek saklama alani gerektirir Siralama Algoritmalarinin ListesiAsagidaki tablolarda n dizideki siralanacak olan eleman sayisini gosterir Ortalama ve En Kotu kolonlari ilgili durumlardaki karmasikligi Bellek kolonu ise listenin siralanabilmesi icin listenin bellekte kapladigi alandan ne kadar daha fazla saklama alani gerektigini gosterir Karsilastirma ile Siralayan Siralama Algoritmalari Adi Ortalama En Kotu Bellek Kararli mi Yontem Diger AciklamalarKabarcik Siralamasi O n O 1 Evet DegistirmeKokteyl Siralamasi O n O 1 Evet DegistirmeTarak Siralamasi O n log n O n log n O 1 Hayir Degistirme Kucuk boyutta kodla uygulanabilirCuce Siralamasi O n O 1 Evet DegistirmeSecmeli Siralama O n O n O 1 Hayir Secme Kararli bir siralama olarak uygulanabilirEklemeli Siralama O n d O n O 1 Evet Ekleme d ters cevirme sayisidir ve O n dirShell Siralamasi O n log n O 1 Hayir EklemeAgac Siralamasi O n log n O n log n O n Evet Ekleme Kendini dengeleyen bir ikili arama agacinda kullanildigindaKutuphane Siralamasi O n log n O n O n Evet EklemeBirlestirmeli Siralama O n log n O n log n O n Evet BirlestirmeYerinde Birlestirmeli Siralama O n log n O n log n O 1 Evet Birlestirme Ornek uygulamasini gosteren sayfa 1 Yigin Siralamasi O n log n O n log n O 1 Hayir SecmeRahat Siralama O n log n O 1 Hayir SecmeHizli Siralama O n log n O n O log n Hayir Bolumlendirme Yalin uygulamalari O n kadar bir alan kullanir ortada bir pivot kullanilirsa en kotu durumda O n log n olabilirIcgozlemle Siralama O n log n O n log n O log n Hayir Melez Standart Sablon Kutuphanelerinin cogunda kullanilirSabir Siralamasi O n O n Hayir Ekleme O n log n zamanda butun en uzun artan altdizileri bulurIplik Siralamasi O n log n O n O n Evet SecmeHizli Siralama nin uygulanmasi sirasindaki davranisi Yatay cizgiler secilen pivot elemanlari gosterir Kabarcik siralamasi nin rastgele uretilmis sayilari nasil siraladigini gosteren bir ornekEklemeli Siralama nin rastgele uretilmis sayilari nasil siraya dizdigini gosteren bir ornek Karsilastirmadan Siralayan Siralama Algoritmalari Asagidaki tablo karsilastirma kullanmadan siralama yapan siralama algoritmalarini gostermektedir Bu algoritmalar karsilastirma yapmadiklari icin karmasikliklarininO n log n gibi bir alt siniri yoktur Tabloda gosterilen karmasikliklar siralanacak listedeki eleman sayisi n her bir anahtarin boyutu k ve uygulama tarafindan kullanilan parca boyutu k cinsiden yazilmistir Algoritmalarin pek cogu anahtar boyutunun butun satirlarda ozgun anahtar degerleri olmasini saglayacak kadar buyuk ve n lt lt 2k lt lt cok daha kucuk oldugunu varsayar Adi Ortalama En Kotu Bellek Kararli mi n lt lt 2k Diger AciklamalarGuvercin Yuvasi Siralamasi O n 2k O n 2k O 2k Evet EvetKova Siralamasi O n k O n k O n k Evet Hayir Elemanlarin dizide duzenli olarak dagildigini varsayar Sayarak Siralama O n 2k O n 2k O n 2k Evet EvetEn anlamsiz Basamaga gore siralama O n k s O n k s O n Evet HayirEn anlamli Basamaga gore siralama O n k s O n k s 2s O k s 2s Hayir HayirO n k log n O n k log n 5 O n Hayir Hayir Asimtotlar n lt lt 2k varsayimina dayanir ancak algoritmanin buna gereksinimi yoktur Verimsiz Siralama Algoritmalari Asagidaki tablo cok verimsiz olduklari ya da ozel bir donanim gerektirdikleri icin gercek hayatta kullanilmasi olumlu sonuclar vermeyecek siralama algoritmalarini gostermektedir Adi Ortalama En Kotu Bellek Kararli mi Karsilastirma siralamasi mi Diger AciklamalarSacma siralama O n n O 1 Hayir Evet Knuth karistirmasi kullanilarak ortalama zamaniRastgele degistirmeli siralama O n n O 1 Hayir Evet Ortalama zamani sonusmayan bicimde sacma siralamanin yarisidirO n2 71 O n2 71 O log n Hayir EvetN A N A N A Hayir Ozel donanim gerektirirO n O n O log n Hayir Evet Sayi yapilan degisiklik sayisidirO log n O log n O n log n Evet Hayir O n log n boyutunda ozel bir devre gerektirirAyrica bakinizAlgoritma Listesi Buyuk O Gosterimi Veri yapilariDis baglantilarArdisik ve kosut siralama algoritmalari13 Aralik 2012 tarihinde Wayback Machine sitesinde Ricardo Baeza Yates in siralama algoritmalari sayfasi14 Mart 2008 tarihinde Wayback Machine sitesinde Algoritmalar sozlugu veri yapilari ve sorular 24 Haziran 2005 tarihinde Wayback Machine sitesinde Slightly Skeptical View on Sorting Algorithms22 Ekim 2012 tarihinde Wayback Machine sitesinde Sorting Revisited15 Nisan 2008 tarihinde Wayback Machine sitesinde