Şubat 1021

Radix Sort

Radix Sort algoritması, sayıları sıralamaya yarayan bir sıralama algoritmasıdır. Tarihte ilk kullanımı 1887 yılında Herman Hollerith’un 1887 yılındaki kataloglama makinesi çalışmalarına dayanmaktadır. Karakter katarları ve tarihler de sayma sayısı olarak temsil edilebildiklerinden (ASCII), radix sort sayılar yanından karakter katarlarını da sıralayabilir. Sıralama işlemi O(kN) zamanda gerçeklenir. N: Veri kümesinde yer alan eleman sayısı, k: Veri kümesinde yer alan elemanların en büyük basamak sayısı Basamakları kullanarak sıralama işlemi yapılır. İlk olarak en küçük basamağa (en sağ) göre sıralanır. En büyük basamağa doğru ilerlenir. Her basamakta sıralama işlemi tekrarlanır. Böylece elimizde küçükten büyüğe (ya da büyükten küçüğe – isteğe bağlı) sıralanmış veri kümesi kalmış olur.   Örnek C++ kodu: #include <iostream.h> #include <stdlib.h> #include <string.h> void radix (int byte, long N, long *source, long *dest) { long count[256]; long index[256]; memset (count, 0, sizeof (count)); for ( int i=0; i<N; i++ ) count[((source[i])>>(byte*8))&0xff]++; index[0]=0; for ( i=1; i<256; i++ ) index[i]=index[i-1]+count[i-1]; for ( i=0; i<N; i++ ) dest[index[((source[i])>>(byte*8))&0xff]++] = source[i]; } void radixsort (long *source, long *temp, long N) { radix (0, N, source, temp); radix (1, N, temp, source); radix (2, N, source, temp); radix (3, N, temp, source); } void make_random (long *data, long N) { for ( int i=0; i<N; i++ ) data[i]=rand()|(rand()<<16); } long data[100]; long temp[100]; void main (void) { make_random(data, 100); radixsort (data, temp, 100); for ( int i=0; i<100; i++ ) cout << data[i] << '\n'; } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } Kaynak: www.brpreiss.com www.cubic.org Tags: , | Categories: Algoritma | C++