×

Welcome to TagMyCode

Please login or create account to add a snippet.
 

Sortowanie pozycyjne, przez zliczanie

0
0
 
0
Language: C
Posted by: Damian Pytkowski
Added: May 2, 2016 8:54 PM
Modified: May 3, 2016 1:06 PM
Views: 19
Tags: sort split join sortowanie radix counting
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <string.h>
  5. #include <math.h>
  6. #define SIZE 43000
  7.  
  8. void splitNumOnDigits(int input[],int output[][5]);
  9. void joinDigitsOnNum(int input[][5],int output[]);
  10. void drawNum(int output[]);
  11. void countingSort(int input[][5],int output[][5],int col);
  12. void addUp(int input[][5],int output[],int col);
  13. void fillZero(int arr[]);
  14. void radixSort(int start[]);
  15. void copyDigits(int input[][5],int output[][5],int rowA, int rowB);
  16. void main()
  17. {
  18.     int arr1[SIZE],arr2[SIZE],i;
  19.     clock_t c1,c2;
  20.     drawNum(arr1);
  21.     c1=clock();
  22.     radixSort(arr1);
  23.     c2=clock();
  24.     for(i=0;i<SIZE;i++)
  25.         printf("%d\n",arr1[i]);
  26.     printf("Czas: %d",c2-c1);
  27.  
  28. }
  29. void radixSort(int start[])
  30. {
  31.     int auxArr1[SIZE][5],auxArr2[SIZE][5],i,j;
  32.     int (*p)[5],(*q)[5],(*r)[5];
  33.     p=auxArr1;q=auxArr2;
  34.     splitNumOnDigits(start,auxArr1);
  35.     for(i=0;i<=5;i++){
  36.         countingSort(p,q,i);
  37.         r=p;
  38.         p=q;
  39.         q=r;
  40.     }
  41.     p=q;q=p;
  42.     joinDigitsOnNum(p,start);
  43. }
  44. void countingSort(int input[][5],int output[][5],int col)
  45. {
  46.     int addUpArr[10],i;
  47.     fillZero(addUpArr);
  48.     addUp(input,addUpArr,col);
  49.  
  50.     for(i=SIZE-1;i>=0;i--){
  51.         copyDigits(input,output,addUpArr[input[i][col]]-1,i);
  52.         addUpArr[input[i][col]]--;
  53.     }
  54. }
  55. void addUp(int input[][5],int output[],int col)
  56. {
  57.     int i;
  58.     for(i=0;i<SIZE;i++){
  59.         output[input[i][col]]+=1;
  60.     }
  61.     for(i=1;i<10;i++){
  62.         output[i]+=output[i-1];
  63.     }
  64. }
  65. void copyDigits(int input[][5],int output[][5],int rowA, int rowB)
  66. {
  67.     int i;
  68.     for(i=0;i<5;i++)
  69.         output[rowA][i]=input[rowB][i];
  70. }
  71. void joinDigitsOnNum(int input[][5],int output[])
  72. {
  73.     int i,j;
  74.     float aux;
  75.     for(i=0;i<SIZE;i++){
  76.         output[i]=0;
  77.         for(j=0;j<5;j++){
  78.             aux = input[i][j]*pow(10,j);
  79.             output[i]+=aux;
  80.         }
  81.         j=0;
  82.     }
  83. }
  84. void splitNumOnDigits(int input[],int output[][5])
  85. {
  86.     int i,j,aux;
  87.     for(i=0;i<SIZE;i++){
  88.         for(j=0;j<5;j++){
  89.             aux=input[i]%10;
  90.             input[i]-=aux;
  91.             output[i][j]=aux;
  92.             input[i]=input[i]/10;
  93.         }
  94.         j=0;
  95.     }
  96. }
  97. void drawNum(int output[])
  98. {
  99.     int i;
  100.     srand(time(NULL));
  101.     for(i=0;i<SIZE;i++)
  102.         output[i]=rand()%100000;
  103. }
  104. void fillZero(int arr[])
  105. {
  106.     int i;
  107.     for(i=0;i<10;i++)
  108.         arr[i]=0;
  109. }
  110.  

Write a comment

To post comments, please log in or register.