Dizileri sıralamak

DİZİLERİ SIRALAMAK

Veri sıralamak (örneğin, verileri artan ya da azalan bir sırada yerleştirmek) en önemli bilgisayar uygulamalarından biridir. Bir banka, bütün çekleri hesap numarasına göre sıralayarak her ay sonunda bankanın hesaplarını yapmaktadır. Telefon şirketleri, abonelerini soyadı ve adlarına göre sıralayarak onlara ulaşmayı kolaylaştırmaktadır. Hemen hemen tüm organizasyonlar, verileri ve bazı durumlarda da oldukça büyük verileri sıralamak zorundadır. Veri sıralama, bilgisayar bilimlerinde yoğun araştırmalara konu olan ilgi çekici bir konudur. Bu ünitede belki de en basit sıralama yöntemlerini tartışacağız. Alıştırmalarda ve 12.ünitede daha yüksek performans sağlayan karmaşık yöntemlerden de bahsedeceğiz.

Performans İpuçları 6.5
Genellikle en basit algoritmalar, en zayıf olanlarıdır. Bunların özelliği kolaylıkla yazılmaları,test edilmeleri ve hatalarının kolay ayıklanmasıdır. Ancak daha karışık algoritmalara, maksimum performansı gerçekleştirmek için ihtiyaç duyulur.

Şekil 6.5, 10 elemanlı a dizisinin(9.satır) elemanlarının değerlerini artan bir sırada dizmektedir. Bu tekniğe kabarcık sıralama ( buble sort ) denir çünkü en küçük değer, dizinin en üstüne bir su kabarcığı gibi çıkmakta, büyük değerler ise dizinin sonuna doğru çökmektedir. Bu teknik dizide bir çok tur yaptıracaktır. Her turda eleman çiftleri karşılaştırılır. Eğer bir çift artan sırada ise ( ya da değerleri eşitse), değerleri olduğu gibi bırakılır. Eğer çift azalan bir sırada ise dizinin içinde değerleri yer değiştirilir.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

/* Şekil 6.15: fig06_15.c
Bu program bir dizinin değerlerini
artan sıraya sokar */
#include <stdio.h>
#define BOYUT 10
 
int main( )
{
int a[ BOYUT ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
int i, tur, tut;
 
printf( "Veriler orjinal sırasında\n" );
 
  for ( i = 0; i <= BOYUT - 1; i++ )
      printf( "%4d", a[ i ] );
 
  for ( tur = 1; tur <= BOYUT - 1; tur++ ) /* turlar */
      for ( i = 0; i <= BOYUT - 2; i++ ) /* bir tur */
          if (a[i]>a[i+1] ) { /*bir karşılaştırma*/
              tut = a[ i ]; /* bir değiştirme */
a[ i ] = a[ i + 1 ];
a[ i + 1 ] = tut;
}
 
printf( "\nVeriler artan sıralamada \n" );
 
  for ( i = 0; i <= BOYUT - 1; i++ )
      printf( "%4d", a[ i ] );
 
printf( "\n" );
 
return 0;
}

Veriler orjinal sırasında
2 6 4 8 10 12 89 45 37
Veriler artan sıralamada
2 4 6 8 10 12 37 45 89

Şekil 6.15 Bir diziyi kabarcık sıralama ile düzenlemek.

Program önce a [0] ile a [1]'i, daha sonra a [1] ile a [2]'yi, daha sonra a [2] ile a [3]'ü karşılaştırmakta ve bu şekilde a [8] ile a [9]'u karşılaştırana kadar devam etmektedir. On eleman olmasına rağmen dokuz karşılaştırmanın yapıldığına dikkat ediniz. Karşılaştırmaların yapılma yöntemi yüzünden büyük bir değer tek bir turda dizide aşağıya doğru bir çok pozisyon ilerleyebilirken, küçük bir değer yukarıya doğru yalnızca tek bir pozisyon ilerleyebilir. İlk turda, en büyük değerin dizinin en alttaki elemanı olan a[9]'a gitmesi garanti altına alınmıştır. İkinci turda, ikinci en büyük değerin a[8]'e gideceği garantidir. Dokuzuncu turda, dokuzuncu en büyük değerin a[1]'e gitmesi garantidir. Bu, en küçük değeri a[0]'da bırakır, böylece dizinin 10 elemanı olmasına rağmen diziyi sıralamak için yalnızca 9 geçiş gereklidir.

Sıralama, yuvalı for yapıları (17 ile 25.satırlar arası) sayesinde yapılmaktadır. Eğer bir yer değiştirme gerekliyse bu, aşağıdaki üç atama sayesinde yapılır:

1
2
3

tut = a [i];
a [i] = a [i+1];
a [i+1] = tut;

Bu atamalardaki tut değişkeni, değerlerin yeri değiştirilirken değerlerden birini geçici olarak tutabilmek için kullanılır. Yer değiştirme aşağıdaki gibi yalnızca iki atama yapılarak gerçekleştirilemez.

1
2

a [i] = a [i+1];
a [i+1] = a [i];

Örneğin, eğer a [ i ]'nin değeri 7 ve a [ i+1 ]'in değeri 5 olsaydı, ilk atamadan sonra her iki değerde 5 olacak ve 7 değeri kaybolacaktı. Bu sebepten, tut değişkeni gibi fazladan bir değişkene ihtiyaç duyarız.

Kabarcık sıralamanın en önemli özelliği yazılmasının kolay oluşudur. Buna rağmen kabarcık sıralama yavaş çalışır. Bu, büyük diziler sıralanırken gözle görünür hale gelir. Alıştırmalarda kabarcık sıralamanın daha etkili versiyonlarını araştıracağız. Şu ana kadar kabarcık sıralamadan daha etkili yöntemler geliştirilmiştir. Bunlardan bir kaçını ileride inceleyeceğiz. Daha teknik kurslar sıralama ve arama konularını daha detaylı bir şekilde incelemektedir.