chocokanpan BLOG

東京Basic Technology勉強会[とべとべ]
http://tobe-tobe.kwappa.net/wiki/?event%2F2009-06-11%20vol.5

「C言語でバケットソート」という題で某所で発表してきました。
アルゴリズムとは何か、ソートとは何かこんな歳になって見つめ
直すきっかけとなりました。バケットソートは、単純な手順で
条件に合えば、高速。とても楽しんで組みました。仕事では、
使わない言語で組むのは、刺激があって良いですね。

おまけ：
バケットソートされた後に、FizzBuzz
%を使わないバージョン。

#define MAX 1000
#include <stdio.h>
#include <stdlib.h>

void bucketSort(int array[], int n) {
  int i, j;
  int count[n];

  // 箱の初期化
  for(i=0; i <= n; i++) {
    count[i] = 0;
  }

  // 箱詰め
  for(i=0; i <= n; i++) {
    (count[array[i]])++;
  }

  // 箱から取り出す
  for(i=0,j=0; i <= n; i++) {
    for(; count[i]>0; (count[i])--) {
      array[j++] = i;
    }
  }
}

void print_fizzbuzz(int num){

   if(num-15*(num/15)==0){
	  printf("FizzBuzz\n");
   }else if(num-5*(num/5)==0){
	  printf("Buzz\n");
   }else if(num-3*(num/3)==0){
	  printf("Fizz\n");
   }else{
	  printf("%d\n",num);
   }
   
}

int main() {
  int array[MAX] = {891, 235, 743, 381, 769, 79, 373, 967, 579, 502, 378, 496, 38, 129, 232, 206, 679, 827, 305, 640, 965, 47, 620, 411, 886, 768, 159, 150, 4, 318, 970, 279, 971, 16, 572, 682, 848, 593, 393, 138, 953, 818, 48, 824, 842, 791, 350, 764, 635, 734, 212, 917, 339, 95, 671, 449, 612, 775, 115, 866, 162, 343, 346, 312, 93, 617, 216, 867, 929, 495, 406, 850, 336, 846, 241, 936, 634, 303, 408, 773, 281, 472, 231, 309, 363, 1, 313, 371, 924, 200, 830, 450, 652, 8, 739, 933, 729, 493, 950, 160, 220, 639, 330, 735, 990, 777, 754, 147, 509, 736, 296, 486, 37, 310, 263, 919, 868, 137, 142, 143, 942, 726, 443, 479, 71, 599, 369, 388, 715, 583, 698, 966, 28, 684, 738, 519, 478, 806, 33, 161, 814, 939, 801, 597, 470, 474, 832, 663, 586, 525, 641, 195, 42, 815, 711, 977, 993, 794, 67, 434, 705, 22, 463, 997, 631, 103, 630, 875, 869, 132, 177, 175, 549, 100, 551, 24, 547, 826, 546, 527, 844, 327, 809, 604, 436, 319, 494, 691, 700, 430, 957, 520, 251, 770, 787, 940, 506, 610, 234, 723, 661, 555, 751, 847, 526, 333, 184, 468, 503, 259, 105, 911, 144, 386, 828, 654, 255, 974, 752, 242, 633, 622, 552, 658, 288, 256, 240, 201, 533, 402, 54, 951, 51, 131, 508, 765, 94, 491, 956, 58, 218, 239, 972, 712, 884, 414, 63, 165, 954, 569, 56, 524, 614, 316, 372, 991, 92, 432, 807, 672, 873, 139, 69, 31, 104, 356, 261, 664, 625, 266, 236, 70, 996, 577, 445, 471, 692, 492, 595, 804, 157, 638, 573, 498, 451, 894, 466, 191, 405, 304, 885, 627, 112, 761, 976, 771, 717, 61, 786, 485, 944, 389, 740, 822, 230, 320, 409, 14, 163, 984, 872, 122, 989, 986, 203, 98, 323, 779, 424, 130, 419, 985, 629, 988, 561, 693, 374, 541, 858, 96, 567, 983, 863, 276, 833, 91, 211, 680, 598, 455, 392, 73, 395, 979, 417, 584, 932, 183, 543, 923, 59, 286, 790, 534, 237, 758, 681, 819, 756, 749, 981, 741, 459, 782, 785, 968, 713, 898, 589, 278, 452, 11, 611, 744, 475, 607, 992, 274, 390, 945, 778, 530, 636, 745, 166, 123, 64, 30, 170, 416, 748, 836, 29, 724, 501, 360, 88, 709, 108, 762, 427, 128, 563, 946, 125, 145, 799, 780, 644, 180, 759, 403, 233, 915, 425, 862, 77, 623, 811, 871, 367, 647, 270, 490, 753, 298, 141, 146, 517, 825, 605, 565, 609, 197, 285, 353, 763, 999, 757, 489, 90, 678, 892, 737, 562, 74, 174, 821, 903, 469, 301, 246, 646, 476, 179, 557, 535, 78, 282, 558, 473, 257, 225, 114, 704, 348, 118, 845, 5, 260, 311, 616, 564, 359, 747, 536, 444, 456, 391, 532, 901, 796, 876, 229, 883, 688, 214, 677, 538, 412, 302, 719, 701, 689, 325, 447, 465, 198, 299, 889, 789, 315, 750, 637, 394, 656, 32, 795, 952, 574, 550, 831, 228, 366, 335, 483, 331, 62, 755, 962, 440, 994, 89, 540, 328, 649, 805, 116, 368, 273, 433, 294, 121, 720, 249, 181, 696, 370, 899, 437, 25, 75, 337, 480, 295, 853, 428, 207, 60, 918, 812, 909, 423, 458, 133, 40, 19, 9, 435, 980, 448, 902, 158, 648, 843, 357, 515, 568, 86, 306, 746, 326, 10, 169, 43, 513, 840, 733, 910, 289, 893, 321, 219, 613, 254, 358, 49, 221, 657, 687, 522, 415, 907, 189, 531, 173, 50, 410, 963, 267, 879, 134, 226, 111, 66, 580, 961, 659, 592, 578, 803, 995, 314, 510, 396, 537, 55, 153, 545, 683, 457, 332, 608, 352, 275, 398, 354, 253, 904, 400, 676, 926, 706, 948, 176, 685, 385, 556, 107, 250, 135, 851, 324, 399, 383, 300, 208, 44, 925, 272, 542, 407, 674, 497, 548, 421, 890, 539, 172, 222, 68, 566, 384, 690, 602, 727, 362, 511, 882, 102, 149, 816, 702, 943, 72, 528, 666, 178, 710, 152, 441, 721, 669, 835, 205, 896, 460, 559, 154, 344, 529, 922, 81, 293, 960, 188, 387, 959, 99, 351, 958, 645, 650, 264, 730, 185, 364, 632, 34, 76, 784, 662, 802, 560, 209, 856, 192, 361, 376, 855, 244, 186, 615, 340, 120, 317, 772, 707, 322, 829, 6, 164, 774, 308, 151, 793, 594, 938, 426, 148, 349, 878, 838, 718, 927, 667, 442, 52, 217, 20, 182, 224, 912, 920, 375, 668, 870, 860, 975, 897, 619, 329, 642, 651, 900, 252, 110, 155, 21, 248, 507, 570, 46, 655, 168, 905, 487, 213, 837, 26, 338, 880, 380, 544, 788, 725, 418, 852, 499, 80, 518, 290, 57, 585, 800, 670, 431, 18, 101, 708, 582, 167, 955, 277, 797, 914, 140, 521, 601, 27, 271, 84, 334, 516, 913, 382, 342, 404, 937, 798, 930, 245, 888, 618, 12, 987, 429, 877, 397, 973, 628, 699, 190, 307, 512, 297, 675, 934, 136, 15, 673, 783, 106, 269, 857, 347, 817, 591, 887, 500, 341, 482, 2, 606, 722, 576, 861, 265, 1000, 839, 484, 97, 665, 834, 714, 461, 505, 697, 65, 504, 227, 36, 247, 575, 119, 477, 87, 600, 864, 823, 728, 947, 874, 365, 117, 199, 895, 841, 292, 280, 969, 808, 39, 588, 284, 193, 781, 453, 742, 695, 124, 7, 23, 262, 291, 732, 467, 3, 792, 196, 849, 982, 514, 82, 194, 694, 553, 810, 223, 935, 439, 703, 928, 156, 820, 113, 85, 446, 916, 603, 767, 287, 454, 621, 204, 377, 462, 464, 210, 283, 581, 401, 590, 53, 587, 766, 215, 258, 865, 921, 949, 731, 35, 571, 941, 978, 596, 854, 17, 686, 760, 813, 379, 716, 931, 127, 964, 243, 438, 238, 41, 881, 481, 187, 624, 45, 554, 859, 626, 660, 83, 202, 776, 413, 906, 126, 488, 998, 653, 109, 422, 523, 268, 13, 643, 171, 355, 908, 345, 420};

  int i;
  for (i = 0;i < MAX;i++) {
    printf("%4d ",array[i]); 
  }
  printf("\n");

  bucketSort(array, MAX);

  for (i = 0;i < MAX;i++) {
	 print_fizzbuzz(array[i]);
  }
  printf("\n");

  return 0;
}