sort::quicksort

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void outputArray(int *a, int len) {
int i;
for (i=0; i < len; i++)
printf("%i ", *(a + i) );
printf("\n");
}
void fillArray(int *a, int len) {
int i;
for (i=0; i < len; i++)
*(a + i) = i;
int x, y, var;
for ( i = 0; i < len; i++) {
x = rand() % len;
y = rand() % len;
var = *(a + y);
*(a + y) = *(a + x);
*(a + x) = var;
}
}
void sortArray(int *a, int len) {
int i, *data_small, *data_big, len_sml=0, len_big=0, median=0, count_sml = 0, count_big = 0;
median = rand() % len;
for (i = 0; i < len; i++)
if ( *(a + i) < *(a + median) )
len_sml++;
else
len_big++;
//printf("%i %i \n", len_sml, len_big);
data_small = malloc( sizeof(int) * len_sml );
data_big = malloc( sizeof(int) * len_big );
for (i = 0; i < len; i++)
if ( *(a + i) < *(a + median) ) {
*(data_small + count_sml) = *(a + i); count_sml++;
}
else {
*(data_big + count_big) = *(a + i); count_big++;
}
//outputArray(data_small, len_sml); // for debug
int x;
if (len_sml > 2)
sortArray(data_small, len_sml);
else
if ( ( *( data_small + 0) > *( data_small + 1) ) && ( len_sml > 1 ) ) {
x = *( data_small + 1);
*( data_small + 1) = *( data_small + 0);
*( data_small + 0) = x;
}
if (len_big > 2)
sortArray(data_big, len_big);
else
if ( ( *(data_big + 0) > *( data_big + 1) ) && ( len_big > 1 ) ) {
x = *( data_big + 1);
*( data_big + 1) = *( data_big + 0);
*( data_big + 0) = x;
}
for (i=0; i < len_sml; i++)
*( a + i ) = *( data_small + i );
for (i=0; i < len_big; i++)
*( a + i + len_sml ) = *( data_big + i );
free(data_small); data_small = 0;
free(data_big); data_big = 0;
}
//ritsuka nihuya ne ponyal
int main () {
clock_t *times;
int timed = clock() / (double) (CLOCKS_PER_SEC / 1000);
srand(time(NULL));
// initializate dynamic random array
int *data, length = 4096*2, i;
data = malloc( sizeof(int) * length );
fillArray(data, length);
timed = clock() / (double) (CLOCKS_PER_SEC / 1000) - timed;
printf("filling array time : %i\n", timed);
sortArray(data, length);
timed = clock() / (double) (CLOCKS_PER_SEC / 1000) - timed;
printf("sorting array time : %i\n", timed);
// outputArray(data, length);
// clear some data
free(data); data = 0;
return 0;
}