Информация о карманной сортировке

#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
 
using namespace std;
 
// получить номер корзины
inline int getblock(int number){ 
    const int DENOMINATOR = 10;
    return number / DENOMINATOR;
}
 
/*
[url]http://ru.wikipedia.org/wiki/Блочная_сортировка[/url]
*/
 
 
int main()
{
    int mas[] = {29, 25, 3, 49, 9, 37, 21, 43}; //сортируемый массив
    int sizemas = sizeof(mas)/sizeof(int);
 
    const int row = 10;
    const int col = 10;
    vector<vector<int> > arr(row,vector<int>(col)); //корзины(карманы)
 
 
    //распределение по корзинам
    for (int i = 0; i < sizemas; ++i){
        int blocknumb = getblock(mas[i]);
        for (int j = 0; j < row; ++j){
            if (!arr[j][blocknumb]){
                 arr[j][blocknumb] = mas[i];
                 break;
            }
        }
    }
 
 
    //вывод корзин на экран
    for (int i = 0; i < row; ++i){
        for (int j = 0; j < col; ++j)
            cout <<  setw(4) << arr[i][j] ;
        cout<<endl;
    }
 
 
    //сортируем каждую корзину
 
    //вывод отсортированного массива
 
 
    return 0;
}

// To compile: mpicc -lm -o bucket bucket.c
 
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 
#include "mpi.h"
 
/*****************************************************************************/
// Routines used in the sequential implementation of the bucket sort
float* create_buckets(int nbuckets, int nitems);
void bucket_sort(float *data, int ndata, float x1, float x2, int nbuckets,
         float* bucket);
 
int check(float *data,int nitems) {
  double sum=0;
  int sorted=1;
  int i;
 
  for(i=0;i<nitems;i++) {
     sum+=data[i];
     if(i && data[i]<data[i-1]) sorted=0;
  }
  printf("sum=%f, sorted=%d\n",sum,sorted);
}
 
int compare(const void* x1, const void* x2);
/*****************************************************************************/
 
int main(int argc,char *argv[]) {
  // Specify here the full range that the data numbers can cover. We
  // may assume that all the numbers are positive definite
  const float xmin = 10.0;
  const float xmax = 250000;
  int nbuckets=1000;
  int nitems=100000;
  int i;
 
  if(argc==2) nitems=atoi(argv[1]);
 
  float *data=malloc(nitems*sizeof(float));
 
  for(i=0;i<nitems;i++)
    data[i]=drand48()*(xmax-xmin-1)+xmin;
 
  check(data,nitems);
 
  float *buckets=create_buckets(nbuckets,nitems);
  bucket_sort(data,nitems,xmin,xmax,nbuckets,buckets);
 
  check(data,nitems);
 
}
/*****************************************************************************/
 
// Sequential implementation of the bucket sort routine. The full
// range x1 to x2 will be divided into a number of equally spaced
// subranges according to the number of buckets. All the buckets are
// contained in the single one dimensional array "bucket".
void bucket_sort(float *data, int ndata, float x1, float x2, int nbuckets,
         float *bucket) 
{
  int i, count;
 
  // The range covered by one bucket
  float stepsize = (x2 - x1) / nbuckets;
 
  // The number of items thrown into each bucket. We would expect each
  // bucket to have a similar number of items, but they won't be
  // exactly the same. So we keep track of their numbers here.
  int* nitems = malloc(nbuckets * sizeof(int));
  for (i = 0; i < nbuckets; ++i) nitems[i] = 0;
 
  // Toss the data items into the correct bucket
  for (i = 0; i < ndata; ++i) {
 
    // What bucket does this data value belong to?
    int bktno = (int)floor((data[i] - x1) / stepsize);
    int idx = bktno * ndata + nitems[bktno];
 
    //printf("DATA %d %f %d %d\n", i, data[i], bktno, idx);
 
    // Put the data value into this bucket
    bucket[idx] = data[i];
    ++nitems[bktno];
  }
  
  // Sort each bucket using the standard library qsort routine. Note
  // that we need to input the correct number of items in each bucket
  count = 0;
  for (i = 0; i < nbuckets; ++i) {
    if(nitems[i]) {
      qsort(&bucket[i*ndata], nitems[i], sizeof(float), compare);
      memcpy(data,&bucket[i*ndata],nitems[i]*sizeof(float));
      data+=nitems[i];
    }
  }
 
  // Don't need the number of items anymore
  free(nitems);
  
}
 
/*****************************************************************************/
 
// Create a data array to hold the given number of buckets for the
// given number of total data items. All buckets are held contiguously
// in the
float* create_buckets(int nbuckets, int nitems)
{
  int i;
 
  int ntotal = nbuckets * nitems;
 
  // Pointer to an array of more pointers to each bucket
  float* bucket = calloc(ntotal, sizeof(float*));
  for (i=0; i<ntotal; ++i) bucket[i] = 0;
 
  // return the address of the array of pointers to float arrays
  return bucket;
}
 
/*****************************************************************************/
 
// The comparison function to use with the library qsort
// function. This will tell qsort to sort the numbers in ascending
// order.
int compare(const void* x1, const void* x2) {
  const float* f1 = x1;
  const float* f2 = x2;
  float diff = *f1 - *f2;
 
  return (diff < 0) ? -1 : 1;
}

#include <iostream>
#include <iomanip>
using namespace std;
 
#define NARRAY 8  /* array size */
#define NBUCKET 5 /* bucket size */
#define INTERVAL 10 /* bucket range */
 
struct Node 
{ 
    int data;  
    struct Node *next; 
};
 
void BucketSort(int arr[]);
struct Node *InsertionSort(struct Node *list);
void print(int arr[]);
void printBuckets(struct Node *list);
int getBucketIndex(int value);
 
void BucketSort(int arr[])
{   
    int i,j;
    struct Node **buckets;  
 
    /* allocate memory for array of pointers to the buckets */
    buckets = (struct Node **)malloc(sizeof(struct Node*) * NBUCKET); 
 
    /* initialize pointers to the buckets */
    for(i = 0; i < NBUCKET;++i) {  
        buckets[i] = NULL;
    }
 
    /* put items into the buckets */
    for(i = 0; i < NARRAY; ++i) {   
        struct Node *current;
        int pos = getBucketIndex(arr[i]);
        current = (struct Node *) malloc(sizeof(struct Node));
        current->data = arr[i]; 
        current->next = buckets[pos];  
        buckets[pos] = current;
    }
 
    /* check what's in each bucket */
    for(i = 0; i < NBUCKET; i++) {
        cout << "Bucket[" << i << "] : ";
        printBuckets(buckets[i]);
        cout << endl;
    }
 
    /* sorting bucket using Insertion Sort */
    for(i = 0; i < NBUCKET; ++i) {  
        buckets[i] = InsertionSort(buckets[i]); 
    }
 
    /* check what's in each bucket */
    cout << "-------------" << endl;
    cout << "Bucktets after sorted" << endl;
    for(i = 0; i < NBUCKET; i++) {
        cout << "Bucket[" << i << "] : ";
        printBuckets(buckets[i]);
        cout << endl;
    }
 
    /* put items back to original array */
    for(j =0, i = 0; i < NBUCKET; ++i) {    
        struct Node *node;
        node = buckets[i];
        while(node) {
            arr[j++] = node->data;
            node = node->next;
        }
    }
    
    /* free memory */
    for(i = 0; i < NBUCKET;++i) {   
        struct Node *node;
        node = buckets[i];
        while(node) {
            struct Node *tmp;
            tmp = node; 
            node = node->next; 
            free(tmp);
        }
    }
    free(buckets); 
    return;
}
 
/* Insertion Sort */
struct Node *InsertionSort(struct Node *list)
{   
    struct Node *k,*nodeList;
    /* need at least two items to sort */
    if(list == 0 || list->next == 0) { 
        return list; 
    }
    
    nodeList = list; 
    k = list->next; 
    nodeList->next = 0; /* 1st node is new list */
    while(k != 0) { 
        struct Node *ptr;
        /* check if insert before first */
        if(nodeList->data > k->data)  { 
            struct Node *tmp;
            tmp = k;  
            k = k->next; 
            tmp->next = nodeList;
            nodeList = tmp; 
            continue;
        }
 
        for(ptr = nodeList; ptr->next != 0; ptr = ptr->next) {
            if(ptr->next->data > k->data) break;
        }
 
        if(ptr->next!=0){  
            struct Node *tmp;
            tmp = k;  
            k = k->next; 
            tmp->next = ptr->next;
            ptr->next = tmp; 
            continue;
        }
        else{
            ptr->next = k;  
            k = k->next;  
            ptr->next->next = 0; 
            continue;
        }
    }
    return nodeList;
}
 
int getBucketIndex(int value)
{
    return value/INTERVAL;
}
 
void print(int ar[])
{   
    int i;
    for(i = 0; i < NARRAY; ++i) { 
        cout << setw(3) << ar[i]; 
    }
    cout << endl;
}
 
void printBuckets(struct Node *list)
{
    struct Node *cur = list;
    while(cur) {
        cout << setw(3) << cur->data;
        cur = cur->next;
    }
}
 
int main(void)
{   
    int array[NARRAY] = {29,25,3,49,9,37,21,43};
 
    cout << "Initial array" << endl;
    print(array);
    cout << "-------------" << endl;
 
    BucketSort(array); 
    cout << "-------------" << endl;
    cout << "Sorted array"  << endl;
    print(array); 
    return 0;
}

#include <iostream>
#include <iomanip>

using namespace std;

cout << endl;