İçeriğe atla

Kabuk sıralaması

Kabuk sıralaması
Kabuk sıralama algoritması
SınıfSıralama algoritması
Veri yapısıDizi
Zaman karmaşıklığıO(n log² n), aralıkların dizilimine göre değişir
En iyiGenellikle değil
Alan karmaşıklığıO(n) toplam, O(1) yardımcı
Kabuk sıralaması algoritma renk çubukları

Shell sıralaması (İngilizce: Shell sort), bilgisayar bilimlerinde kullanılan bir sıralama algoritmasıdır. Eklemeli sıralama algoritmasının aşağıdaki iki gözlem kullanılarak genelleştirilmiş biçimidir:

  • Eklemeli sıralama, sıralanacak dizi zaten büyük oranda sıralıysa daha verimli çalışır.
  • Eklemeli sıralama, dizideki öğeleri her adımda yalnızca bir sonraki konuma aktardığından verimsizdir.

Algoritmanın Geçmişi

Shell sıralaması algoritmasının adı algoritmayı bulan kişi olan Donald Shell'den gelmektedir. Donald Shell algoritmayı 1959 yılında yayınlamıştır.

Uygulamalar

C/C++ dilinde yazılmış Shell sıralaması

Aşağıda C/C++ dilinde yazılmış, bir sayı dizisini Shell sıralaması algoritmasını kullanarak sıralayan bir program verilmiştir. 

/*

     SHELL SORT
     Written by erengencturk.net
*/

#include <stdio.h>

#define ELEMENTS 6

void shellsort(int A[],int max)
{
     int stop,swap,limit,temp,k;
   int x=(int)(max/2);
   while(x>0)
   {
        stop=0;
      limit=max-x;
      while(stop==0)
      {
           swap=0;
         for(k=0;k<limit;k++)
         {
              if(A[k]>A[k+x])
            {
                 temp=A[k];
               A[k]=A[k+x];
               A[k+x]=temp;
               swap=k;
            }
         }
         limit=swap-x;
         if(swap==0)
              stop=1;
      }
      x=(int)(x/2);
   }
}

int main()
{
  int i;
  int X[ELEMENTS]={5,2,4,6,1,3};
  printf("Unsorted Array:\n");
  for(i=0;i<ELEMENTS;i++)
            printf("%d ",X[i]);

  shellsort(X,ELEMENTS);
  printf("\nSORTED ARRAY\n");
  for(i=0;i<ELEMENTS;i++)
            printf("%d ",X[i]);

}

Java dilinde yazılmış Shell sıralaması

public static void shellSort(int[] a) {
    for (int i = a.length / 2; i > 0;
          i = (i == 2 ? 1 : (int) Math.round(i / 2.2))) {
        for (int i2 = i; i2 < a.length; i2++) {
            int temp = a[i];
            for (int j = i2; j >= i && a[j - i] > temp; j -= i){
                a[j] = a[j - i];
                a[j - i] = temp;
            }
        }
    }
}

Python dilinde yazılmış Shell sıralaması

  def shellsort(a):
      def increment_generator(a):
          h = len(a)
          while h != 1:
              if h == 2:
                  h = 1
              else: 
                  h = 5*h//11
              yield h

      for increment in increment_generator(a):
          for i in xrange(increment, len(a)):
              for j in xrange(i, increment-1, -increment):
                  if a[j - increment] < a[j]:
                      break
                  a[j], a[j - increment] = a[j - increment], a[j]
      return a

Dış bağlantılar

İlgili Araştırma Makaleleri

MPI (Message Passing Interface) bir bilgisayar iletişim protokolüdür. Dağıtık bellekli bir sistemde paralel program koşan düğümlerin arasındaki iletişim için kullanılan fiilen standart bir protokoldür. MPI uygulamaları Fortran, C, C++ ve Ada programlarından çağrılan kütüphane yordamlarından oluşur. MPI 'ın diğer eski mesaj geçirmeli kütüphanelere olan üstünlüğü taşınabilir (MPI pek çok dağıtık bellekli mimari üzerinde uygulanmıştır) ve hızlı (çünkü her bir uygulama üzerinde çalıştığı hardware için optimize edilmektedir) olmasıdır.

<span class="mw-page-title-main">Birleştirmeli sıralama</span>

Birleşmeli Sıralama, bilgisayar bilimlerinde derecesinde karmaşıklığa sahip bir sıralama algoritmasıdır. Girdi olarak aldığı diziyi en küçük hale gelene kadar ikili gruplara böler ve karşılaştırma yöntemi kullanarak diziyi sıralar.

<span class="mw-page-title-main">Seçmeli sıralama</span>

Seçmeli Sıralama, bilgisayar bilimlerinde kullanılan bir sıralama algoritmasıdır. Karmaşıklığı olduğu için büyük listeler üzerinde kullanıldığında verim sağlamaz ve genel olarak benzeri olan eklemeli sıralamadan daha başarısızdır. Seçmeli sıralama yalın olduğu ve bazı durumlarda daha karmaşık olan algoritmalardan daha iyi sonuç verdiği için tercih edilebilir.

<span class="mw-page-title-main">Hızlı sıralama</span>

Hızlı sıralama, günümüzde yaygın olarak kullanılan bir sıralama algoritmasıdır. Hızlı sıralama algoritması n adet sayıyı, ortalama bir durumda, karmaşıklığıyla, en kötü durumda ise karmaşıklığıyla sıralar. Algoritmanın karmaşıklığı aynı zamanda yapılan karşılaştırma sayısına eşittir.

<span class="mw-page-title-main">Yığın sıralaması</span>

Yığın Sıralaması, bilgisayar bilimlerinde kullanılan karşılaştırmaya dayalı bir sıralama algoritmasıdır. Uygulamada pek çok bilgisayarda hızlı sıralama algoritmasından daha yavaş çalışsa da en kötü durumda O(n log n) çalışma süresi vardır. Yığın sıralaması diziyi yerinde sıralar ancak kararlı bir sıralama algoritması değildir.

<span class="mw-page-title-main">Eklemeli sıralama</span> sıralama algoritma

Eklemeli Sıralama, bilgisayar bilimlerinde kullanılan ve sıralı diziyi her adımda öğe öğe oluşturan bir sıralama algoritmasıdır. Büyük dizilerle çalışıldığında hızlı sıralama, birleştirmeli sıralama ve yığın sıralaması gibi daha gelişmiş sıralama algoritmalarından daha verimsiz çalışır. Ancak buna karşın bazı artıları da vardır:

Cüce sıralaması, bilgisayar bilimlerinde kullanılan araya sokmalı sıralamaya benzer bir sıralama algoritmasıdır. Ara sokmalı sıralamadan farkı kabarcık sıralaması yönteminde olduğu gibi, bir elemanın sıralanan dizideki yerine birçok yer değiştirme yoluyla gelmesidir. Cüce Sıralaması adı algoritmanın yönteminin mitolojideki Hollanda cücelerinin (gnome) bir dizi çiçek saksısını sıraya diziş biçimine benzemesinden kaynaklanmaktadır.

<span class="mw-page-title-main">Kabarcık sıralaması</span>

Kabarcık Sıralaması, bilgisayar bilimlerinde kullanılan yalın bir sıralama algoritmasıdır. Sıralanacak dizinin üzerinde sürekli ilerlerken her defasında iki öğenin birbiriyle karşılaştırılıp, karşılaştırılan öğelerin yanlış sırada olmaları durumunda yerlerinin değiştirilmesi mantığına dayanır. Algoritma, herhangi bir değişiklik yapılmayıncaya kadar dizinin başına dönerek kendisini yineler. Adına "Kabarcık" sıralaması denmesinin nedeni büyük olan sayıların aynı suyun altındaki bir kabarcık gibi dizinin üstüne doğru ilerlemesidir.

Kokteyl sıralaması, bilgisayar bilimlerinde kabarcık sıralaması algoritmasına benzer bir sıralama algoritmasıdır. Kabarcık sıralamasından farkı sıralanacak listenin üzerinden tek yöne doğru değil iki yöne de geçerek öğeleri sıralamasıdır. Algoritmanın uygulanması kabarcık sıralaması algoritmasının uygulanmasından çok az daha zordur.

Tarak Sıralaması, ilk defa 1991 yılının Nisan ayında Stephen Lacey ve Richard Box tarafından Byte dergisinde duyurulmuş yalın bir sıralama algoritmasıdır. Kendisinden önce duyurulmuş kabarcık sıralaması algoritmasından başarılıdır ve karmaşıklıkta hızlı sıralama algoritmasıyla yarışır. Algoritmanın ana fikri listenin sonundaki küçük değerli öğelerin sayısını azaltmaktır. Kabarcık sıralaması algoritmasında sıralanacak listenin sonundaki küçük değerli öğelerin varlığı algoritmayı çok yavaşlattığı için tarak sıralamasında bu değerlerin sayısının azaltılması yoluna gidilmiştir.

İplik sıralaması bilgisayar bilimlerinde kullanılan bir sıralama algoritmasıdır. Sıralanacak olan dizinin, sıralanmış alt dizilerinin oluşturularak bu alt dizilerin birleştirilmesi yoluyla sonucun oluşturulması mantığına dayanır. Algoritmanın her bir aşamasında ana dizinin üzerinden geçilir ve bu diziden zaten sıralanmış olan bir dizi eleman çıkarılır. Çıkarılan bu eleman dizileri daha sonra birleştirilir.

Saçma sıralama veya rastgele sıralama, bilgisayar bilimlerinde yalnızca eğitim amaçlı olarak kullanılan verimsiz bir sıralama algoritması. Bir deste oyun kağıdı saçma sıralama algoritmasıyla sıralanmak istendiğinde, destenin sıralı olup olmadığına bakılır, eğer deste sıralı değilse havaya atılarak yere düşen kartlar toplanarak deste yeniden oluşturulur. Bu işlem deste sıralanana kadar sürer.

Sayarak sıralama bilgisayar bilimlerinde kullanılan ve kova sıralaması gibi sıralanacak dizinin içindeki değerlerin aralığının bilinmesi durumunda kullanılabilen bir sıralama algoritmasıdır. Sayarak sıralama algoritması dizideki değerlerin aralık bilgilerini yeni bir dizi oluşturmak için kullanır. Oluşturulan yeni dizinin her bir satırı ana dizide o satır numarasının değerine sahip ögelerin sayısını gösterir. Yeni dizideki öge değeri sayıları daha sonra ana dizideki tüm değerlerin doğru konuma konulması için kullanılır. Sayarak sıralama algoritması güvercin yuvası sıralamasından daha verimsiz bir algoritmadır.

<span class="mw-page-title-main">Fourier serisi</span>

Matematikte, Fourier serileri bir periyodik fonksiyonu basit dalgalı fonksiyonların toplamına çevirir.

Döngü açma, programın çalışmasını hızlandıran döngü dönüştürme yöntemlerinden biridir. Bu yöntem yazılan programın kod satır sayısını artırmaktadır. Döngülerdeki dönüşüm manuel olarak programcı tarafından yapılabileceği gibi kodlar derleyiciler tarafından da düzenlenebilmektedir.

Bilgisayar programlamada dinamik iletim, altyordam çağrılarının ilişkin altyordam başlangıç adresine dinamik olarak bağlanmasıdır. Bir diğer deyişle, dinamik iletim program metnindeki bir çağrı ile işletilen altyordamın programın çalışması sırasında birbirine bağlanması durumudur. Geri çağrı ve çokbiçimliliğin realize edilmesinde kullanılan bu bağlama yöntemi, yordamsal programlama dillerinde altyordam göstericileriyle gerçekleştirilirken, nesne yönelimli dillerde kalıtlama ve gerçekleştirme ilişkilerinin kullanılmasıyla otomatikman sağlanır. Altyordamların birinci sınıf dil öğesi olarak ele alındığı fonksiyonel programlama dillerinde ise, aynı işlevsellik altyordamların argüman olarak geçirilmesi ile sağlanabilir.

<span class="mw-page-title-main">For döngüsü</span> programa dillerinde yaygın kullanılan bir döngü

For döngüsü, programlama dillerinde temel olarak bir kod blokunu belirli bir sayıda ve üst üste çalıştırmak için kullanılan bir döngüdür. Döngü başlangıcında kullanılan değişkene döngü içinde müdahale edilerek tekrar sayısı değiştirilebilir. While döngüsüyle birlikte en çok kullanılan döngüdür.

İnkâr edilebilen şifreleme, kriptografi ve steganografide kullanıcılarına şifrelenmiş bir bilginin varlığını inandırıcı şekilde inkâr edebilme imkânını sunan, karşı tarafı aldatmak için kullanılan usuldur.

<span class="mw-page-title-main">FIFO algoritması</span>

FIFO algoritmasının mantığı basittir. Bellek yöneticisinin yeni bir sayfaya yer açmak için, hangi sayfayı dışarıda bırakacağını karar veren algoritmalardan biridir. Yönlendiriciye gelen ilk paket, iletilecek ilk pakettir.

Berlekamp-Massey algoritması, belirli bir ikili çıkış dizisi için en kısa doğrusal geri besleme kaydırmalı yazmacı (LFSR) bulan bir algoritmadır. Algoritma ayrıca rastgele bir alanda lineer olarak yinelenen bir dizinin minimum polinomunu da bulacaktır. Alan gereksinimi, Berlekamp-Massey algoritmasının sıfır olmayan tüm öğelerin çarpımsal bir tersi olmasını gerektirdiği anlamına gelir. Reeds ve Sloane, bir yüzüğü işlemek için bir uzantı sunar.


Bu sayfa, bu Vikipedi makalesine dayanmaktadır.
Metin, CC BY-SA 4.0 lisansı altında mevcuttur; ek koşullar uygulanabilir.
Görseller, videolar ve sesler kendi lisansları altında mevcuttur.