Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdlib.h>
- #include <stdio.h>
- #include <time.h>
- #define MAX 10000000
- int selectRandomPosition(int* target, int left, int right){
- srand((unsigned) time(NULL));
- int length = right - left + 1;
- int r = left + rand()%length;
- return r;
- }
- void ternarySplitQuickSort(int* target, int left, int right)
- {
- if(left>=right) return;
- int maxlen = right - left + 1;
- int same[MAX];
- int less[MAX];
- int more[MAX];
- int same_count = 0;
- int less_count = 0;
- int more_count = 0;
- int random_idx = selectRandomPosition(target, left, right);
- int pivot = target[random_idx];
- for(int i = 0; i < maxlen; i++) {
- if(target[i] < pivot) {
- less[less_count++] = target[i];
- } else if (target[i] > pivot) {
- more[more_count++] = target[i];
- } else {
- same[same_count++] = target[i];
- }
- }
- {
- int i = 0;
- for(int j = 0; j < less_count; j++) {
- target[i++] = less[j];
- }
- for(int j = 0; j < same_count; j++) {
- target[i++] = same[j];
- }
- for(int j = 0; j < more_count; j++) {
- target[i++] = more[j];
- }
- }
- // free(same); free(less); free(more);
- ternarySplitQuickSort(target, left, less_count);
- ternarySplitQuickSort(target, less_count + same_count - 1, right);
- }
- int main(int argc, char** argv){
- // Generate the running example array of size 12
- int n = 12;
- int target[12] = {48, 195, 12, 49, 198, 24, 99, 140, 48, 195, 12, 48};
- // Generate an array of random numbers
- // int n = 10000000; // array length
- // int* target;
- // target = (int *)malloc( sizeof(int) * n); // Use the heap to generate a long array
- // for(int i=0; i<n; i++) {
- // target[i] = rand()%256;
- // }
- clock_t sTime, eTime;
- sTime = clock();
- ternarySplitQuickSort(target, 0, n-1);
- eTime = clock();
- printf("Elapsed time = %f sec.\n", (float)(eTime - sTime)/(float)CLOCKS_PER_SEC);
- // Check if the target is sorted
- int sorted = 1;
- for(int i = 0; i < (n-1); i++){
- if( target[i] > target[i+1]) sorted = 0;
- }
- if (sorted == 1) printf("sorted\n");
- // free(target);
- return 0; // 0 means EXIT_SUCCESS
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement