Quicksort algorithm over long long numbers:
import random
import time
def partition(values, left, right, pivotidx):
pivot = values[pivotidx]
values[right], values[pivotidx] = values[pivotidx], values[right]
storeidx = left
for idx in range(left, right):
if values[idx] < pivot:
values[idx], values[storeidx] = values[storeidx], values[idx]
storeidx += 1
values[storeidx], values[right] = values[right], values[storeidx]
return storeidx
def _doquicksort(values, left, right):
if right > left:
pivotidx = (left+right)//2
pivotidx = partition(values, left, right, pivotidx)
_doquicksort(values, left, pivotidx)
_doquicksort(values, pivotidx + 1, right)
return values
def quicksort(nums):
return _doquicksort(nums, 0, len(nums) - 1)
def main():
nums = [random.getrandbits(64) for i in range(1000000)]
timeit = time.time()
nums = quicksort(nums)
timeit = time.time() - timeit
print('time =', timeit)
main()
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define ARRAYSIZE 1000000
long partition(long long *values, long left, long right, long pivotidx) {
long long temp, pivot;
long storeidx, idx;
pivot = values[pivotidx];
temp = values[right];
values[right] = values[pivotidx];
values[pivotidx] = temp;
storeidx = left;
for(idx = left; idx<right; idx++) {
if (values[idx] < pivot) {
temp = values[idx];
values[idx] = values[storeidx];
values[storeidx] = temp;
storeidx++;
}
}
temp = values[storeidx];
values[storeidx] = values[right];
values[right] = temp;
return storeidx;
}
long long *_doquicksort(long long *values, long left, long right) {
long pivotidx;
if (right > left) {
pivotidx = (left + right) / 2;
pivotidx = partition(values, left, right, pivotidx);
_doquicksort(values, left, pivotidx);
_doquicksort(values, pivotidx + 1, right);
}
return values;
}
long long *quicksort(long long *nums) {
return _doquicksort(nums, 0, ARRAYSIZE-1);
}
int main() {
long i;
clock_t timeit;
long long *nums;
nums = malloc(sizeof(long long)*(ARRAYSIZE+1));
for(i=0; i<ARRAYSIZE; i++) {
nums[i] = (long long)rand();
}
timeit = clock();
nums = quicksort(nums);
timeit = clock() - timeit;
printf("time = %f\n", (float)(timeit) / CLOCKS_PER_SEC);
}
Python Time = 3.5579
C Time = 0.2170
Relationship = 3.5579 / 0.2170 = 16.4 : 1