Mərtəbəli çeşidləmə alqoritmi

Mərtəbəli çeşidləmə alqoritmi (en. radix sorting algorithm) - çeşidləməni qruplaşdırılan elementlərlə, onların açarlarının ardıcıl komponentlərinə görə gerçəkləşdirən çeşidləmə alqoritmi. Məsələn, 0-dan 999-dək ədədlərin çeşidlənməsinə baxaq: birinci siyahı yüzlük mərtəbələrinə görə çeşidlənərək 10 siyahıya ayrılır, sonra bu siyahıların hər biri eyni zamanda onluq mərtəbələrinə görə çeşidlənərək 10 siyahıya ayrılır, və nəhayət, bu siyahıların hər biri təklik mərtəbəsinə görə çeşidlənir. Bu alqoritm, adətən, ikilik ədədlərin çeşidlənməsində daha səmərəli olur, çünki siyahılara ayırma, sadəcə, ədədlərin böyük bitlərinin müəyyənləşdirilməsiylə aparılır, siyahıların sayı isə heç vaxt ikidən artıq olmur.

Mərtəbəli çeşidləmə alqoritmi (C dilində):

include <stdio.h>
define MAX 5
define SHOWPASS

void print(int *a, int n) {

 int i;
 for (i = 0; i < n; i++)
   printf("%d\t", a[i]);

}

void radixsort(int *a, int n) {

 int i, b[MAX], m = a[0], exp = 1;
 for (i = 0; i < n; i++)
 {
   if (a[i] > m)
     m = a[i];
 }

 while (m / exp > 0)
 {
   int bucket[10] =
   {  0 };
   for (i = 0; i < n; i++)
     bucket[(a[i] / exp) % 10]++;
   for (i = 1; i < 10; i++)
     bucket[i] += bucket[i - 1];
   for (i = n - 1; i >= 0; i--)
     b[--bucket[(a[i] / exp) % 10]] = a[i];
   for (i = 0; i < n; i++)
     a[i] = b[i];
   exp *= 10;

   #ifdef SHOWPASS
     printf("\nPASS   : ");
     print(a, n);
   #endif
 }

}

int main() {

 int arr[MAX];
 int i, n;

 printf("Enter total elements (n < %d) : ", MAX);
 scanf("%d", &n);
 n = n < MAX ? n : MAX;

 printf("Enter %d Elements : ", n);
 for (i = 0; i < n; i++)
   scanf("%d", &arr[i]);


 printf("\nARRAY  : ");
 print(&arr[0], n);

 radixsort(&arr[0], n);

 printf("\nSORTED : ");
 print(&arr[0], n);
 printf("\n");

 return 0;

}

Ədəbiyyat

İsmayıl Calallı (Sadıqov), “İnformatika terminlərinin izahlı lüğəti”, 2017, “Bakı” nəşriyyatı, 996 s.

Radix Sort