Блочная сортировка (Корзинная сортировка, Bucket sort) - алгоритм
сортировки, в которой сортируемые элементы делятся на конечное число
отдельных блоков (корзин). Каждый блок затем сортируется отдельно, либо
рекурсивно тем же методом, либо иным другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.
Реализация на C
list sort(list s, typekey min, typekey max) { int i; typekey div, maxb[M], minb[M]; list head[M], t; struct rec aux; list Last;
div = (max - min) / M; /* Find dividing factor */ if(div == 0) div = 1;
for(i = 0; i < M; ++i) head[i] = NULL; /* Place records in buckets */
while(s != NULL){ i = (s->k - min) / div; if(i < 0) i = 0; elseif(i >= M) i = M - 1; t = s; s = s->next; t->next = head[i]; if(head[i] == NULL) minb[i] = maxb[i] = t->k; head[i] = t; if(t->k > maxb[i]) maxb[i] = t->k; if(t->k < minb[i]) minb[i] = t->k; }/* sort recursively */
t = &aux; for(i = 0; i < M; ++i) if(head[i] != NULL){ t->next = sort(head[i], minb[i], maxb[i]); t = Last; } return aux.next; }
Реализация на C++
#include <iostream.h>
class element //element { public: int value; element *next; element() { value=NULL; next=NULL; } };
class bucket //bucket containing a perticular range of values { public: element *firstElement; bucket() { firstElement = NULL; } };
void main() { int lowend=0; // minimum element int highend=100; //max element int interval=10; //number of intervals const int noBuckets=(highend-lowend)/interval; //number of buckets required bucket *buckets=new bucket[noBuckets]; bucket *temp;
cout<<"--------The Elements to be Sorted using Bucket sort are ------------------\n"; int array[]={12,2,22,33,44,55,66,77,85,87,81,83,89,82,88,86,84,88,99};
for(int j=0;j<19;j++) //sending elments into appropriate buckets { cout<<array[j]<<endl; element *temp,*pre; temp=buckets[array[j]/interval].firstElement; if(temp==NULL)//if it is the first element of the bucket { temp=new element; buckets[array[j]/interval].firstElement=temp; temp->value=array[j]; } else { pre=NULL; while(temp!=NULL) //move till the appropriate position in the bucket { if(temp->value>array[j]) break; pre=temp; temp=temp->next; } if(temp->value>array[j]) //if the new value is in betwen or at the begining { if(pre==NULL) //insertion at first if the bucket has elements already { element *firstNode; firstNode=new element(); firstNode->value=array[j]; firstNode->next=temp; buckets[array[j]/interval].firstElement=firstNode; } else //insertion at middle { element *firstNode; firstNode=new element(); firstNode->value=array[j]; firstNode->next=temp; pre->next=firstNode; } } else// if the new value is to be created at last of bucket { temp=new element; pre->next=temp; temp->value=array[j]; }
} }
cout<<"------------------------The Sorted Elements Are---------------\n"; for(int jk=0;jk<10;jk++) { element *temp; temp= buckets[jk].firstElement; while(temp!=NULL) { cout<<"*"<<temp->value<<endl; temp=temp->next; } } cout<<"--------------------------------END--------------------------------\n";
