fork download
copy 
  1. #include <stdlib.h>
  2. #include <math.h>	/*Для floor*/
  3. #include <string.h> /*Для memset*/
  4. #include <stdio.h>
  5. #include <iostream>
  6.  
  7. struct list{
  8. 	double data;
  9. 	struct list *next;
  10. };
  11.  
  12. struct list * insert_front(struct list *root, int data ){
  13.     struct list *tmp = (struct list *)malloc(sizeof(struct list));
  14.  
  15.     if(tmp != NULL){
  16.         tmp->data = data;
  17.         tmp->next = root;
  18.         root = tmp;
  19.     }
  20.  
  21.     return root;
  22. }
  23.  
  24. struct list * sort(struct list *root){
  25.     struct list *new_root = NULL;
  26.  
  27.     while (root != NULL){
  28.         struct list *node = root;
  29.         root = root->next;
  30.  
  31.         if (new_root == NULL || node->data < new_root->data){
  32.             node->next = new_root;
  33.             new_root = node;
  34.         }else{
  35.             struct list *current = new_root;
  36.             while (current->next != NULL && !(node->data < current->next->data)){                   
  37.                   current = current->next;
  38.             }                
  39.  
  40.             node->next = current->next;
  41.             current->next = node;
  42.         }
  43.     }
  44.  
  45.     return new_root;
  46. }
  47.  
  48. void display(struct list *node){
  49.     for ( ; node != NULL; node = node->next) printf("%d ", node->data);
  50. }
  51.  
  52. void BucketSort(double a[], int n){
  53. 	if(a == NULL) return;
  54. 	int i, j;
  55. 	list **buckets = (list **)malloc(n*sizeof(list *));	/*Массив списков, сейчас содержит мусорок*/
  56. 	memset(buckets, 0, n*sizeof(list *));	/*Проинициализируем его*/
  57.  
  58. 	/*Вставить элемент a[i] в список buckets[floor(n*a[i])]*/
  59. 	for(i = 0; i < n; i++){
  60. 		int j = (int)floor(n*a[i]);
  61. 		buckets[j] = insert_front(buckets[j], a[i]);
  62. 	}
  63. 	/*Сортировка всех карманов методом вставок*/
  64. 	for(i = 0; i < n; i++){
  65. 		printf("\nbucket[%d]:\n", i);
  66. 		display(buckets[i]);
  67. 		buckets[i] = sort(buckets[i]);
  68. 	}
  69. 	/*Слияние всех карманов в один список*/
  70. 	j = 0;
  71. 	/*Цикл по всем карманам*/
  72. 	list *p;
  73. 	for(i = 0; i < n ; i++){
  74. 		printf("end loop\n");
  75. 		putchar('\n');
  76. 		if(buckets[i] != NULL){
  77. 			p = buckets[i];
  78. 			while(p != NULL){
  79. 				printf("bucket[%d]: data %d\n", i, p->data);
  80. 				a[j++] = p->data;
  81. 				p = p->next;
  82. 			}
  83. 		}else printf("bucket[%d] is empty\n", i);
  84. 	}
  85. }
  86.  
  87.  
  88. int main(void) {
  89. 	double v[10] = {0.3, 0.1, 0.71, 0.4, 0.1, 0.2, 0.7, 0.8, 0.5, 0.6};
  90.  
  91.  
  92. 	BucketSort(v, 10);
  93.  
  94. 	for(int i = 0; i < 10; i++)
  95. 		std::cout << v[i] << " ";
  96. 	std::cout << std::endl;
  97. 	return 0;
  98. }
  99.  
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
bucket[0]:

bucket[1]:
0 0 
bucket[2]:
0 
bucket[3]:
0 
bucket[4]:
0 
bucket[5]:
0 
bucket[6]:
0 
bucket[7]:
0 0 
bucket[8]:
0 
bucket[9]:
end loop

bucket[0] is empty
end loop

bucket[1]: data 0
bucket[1]: data 0
end loop

bucket[2]: data 0
end loop

bucket[3]: data 0
end loop

bucket[4]: data 0
end loop

bucket[5]: data 0
end loop

bucket[6]: data 0
end loop

bucket[7]: data 0
bucket[7]: data 0
end loop

bucket[8]: data 0
end loop

bucket[9] is empty
0 0 0 0 0 0 0 0 0 0
https://ideone.com/0b97qB
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!