• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Mar 29th, 2020 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <time.h>
4. typedef void (*gen)(int*, int);
5. void generate_random(int*, int);
6. void generate_sorted(int*, int);
7. void generate_sorted_reverse(int*, int);
8. void generate_almost_sorted(int*, int);
9. void generate_almost_sorted_reverse(int*, int);
10. void insertionSort(int*, int);
11. void printArray(int*, int);
12. double timetest (int*, int, gen);
13. void swap(int* a, int* b) {
14.     int tmp = *a;
15.     *a = *b;
16.     *b = tmp;
17. }
18.
19. void generate_random(int* arr, int n) {
20.     //  You can experiment with the modulo value.
21.     //  The bigger number the less duplicates in the array.
22.     for(int i = 0; i < n; ++i) arr[i] = lrand48() % 1000000;
23. }
24.
25. void generate_sorted(int* arr, int n) {
26.     for(int i = 0; i < n; ++i) arr[i] = i;
27. }
28.
29. void generate_sorted_reverse(int* arr, int n) {
30.     for(int i = 0; i < n; ++i) arr[i] = n - i;
31. }
32.
33. void generate_almost_sorted(int* arr, int n) {
34.     //  initialize sorted array
35.     for(int i = 0; i < n; ++i) arr[i] = i;
36.     //  Make some swaps to disturb the order
37.     //  Experiment with different # of swaps
38.     for(int i = 0; i < 100; ++i) {
39.         int j = lrand48() % n;
40.         int k = lrand48() % n;
41.         while(j == k) k = lrand48() % n;
42.         swap(&arr[j], &arr[k]);
43.     }
44. }
45.
46. void generate_almost_sorted_reverse(int* arr, int n) {
47.     //  initialize array sorted in reverse order
48.     for(int i = 0; i < n; ++i) arr[i] = n - i;
49.     //  Make some swaps to disturb the order
50.     //  Experiment with different # of swaps
51.     for(int i = 0; i < 100; ++i) {
52.         int j = lrand48() % n;
53.         int k = lrand48() % n;
54.         while(j == k) k = lrand48() % n;
55.         swap(&arr[j], &arr[k]);
56.     }
57. }
58.
59.
60. int partition(int * tab, int l, int h) {
61.     int pivot = tab[h];
62.     int i = l;
63.     int j = i;
64.     while(j < h) {
65.         if(tab[j] < pivot) {
66.             swap(&tab[j], &tab[i]);
67.             i += 1;
68.         }
69.         j += 1;
70.     }
71.     swap(&tab[i], &tab[h]);
72.     return i;
73. }
74. void Qsort(int * tab, int l, int h){
75.     if(l < h) {
76.         int pivot = partition(tab,l,h);
77.         Qsort(tab,l,pivot-1);
78.         Qsort(tab,pivot+1,h);
79.     }
80. }
81.
82. void printArray(int* arr, int n) {
83.     for (int i = 0; i < n; ++i)
84.         printf("%d ", arr[i]);
85.     printf("\n");
86. }
87. double timetest (int* arr, int n, gen fgen) {
88.
89.     clock_t t0, t1;
90.     fgen(arr, n);
91.
92.     //  Wait for clock() roll over before starting
93.     t0 = clock();
94.     while (t0 == (t1 = clock()));
95.
96.     t0 = t1;
97.     Qsort(arr, 0, n-1);
98.     t1 = clock();
99.
100.     return (t1 - t0) * (1.0 / CLOCKS_PER_SEC);
101. }
102. int main() {
103.
104.     FILE *output = fopen("wyniki","w");
105.     srand48(time(0));
106.     for(int i = 1000;i <= 10000;i += 1000){
107.         int *arr = malloc(i * sizeof(int));
108.         double d1 = timetest(arr, i, generate_random);
109.         fprintf(output, "%12.6f\n","co", d1);
110.         free(arr);
111.     }
112.
113.     return 0;
114. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top