Mərtəbəli çeşidləmə alqoritmi: Redaktələr arasındakı fərq

Silinən məzmun Əlavə edilmiş məzmun
Yeni səhifə: 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ə...
(Fərq yoxdur)

10:47, 22 may 2017 versiyası

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.


  1. include <stdio.h>
  2. define MAX 5
  3. 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;

}

R-05. Mərtəbəli çeşidləmə alqoritmi (C dilində)

Kateqoriya:Çeşidləmə alqoritmi