Confusion about my QuickSort algorithm & Mergesort algorithm

Question

I am currently conducting empirical studies to evaluate the run-time complexities of the quicksort, and mergesort algorithms. To do this I run a random number generator that stores whatever amount of numbers I specify in a binary file. The ranges of those numbers are from 1-1,000,000.I then run tests of each algorithm starting from 100,000 numbers, incrementing by 50,000 each time, until 1,000,000 numbers are sorted on the last run. So 20 tests each. I have successfully completed each algorithm but my results are kind of puzzingly. This is a graph showing my results.

enter image description here

I understand that quicksort has a worst case of O(n2) time, but typically O(n·lg(n)) time. Mergesort has Θ(n·lg(n)) time.

Also I would like to note that when I started the timer I just used clock() from time.h, and calculated the time elapsed. I started my timer one line of code before I called my sorting function.

What I dont understand is how my graph shows mergesort is always double the time, and reaching triple the time to sort numbers compared to quicksort.

My only thought is that for my mergesort algorithm every time I divide my array in half I use malloc to create a new integer array for each half. Of course this means a large amount of calls are made to malloc considering the number sizes I am sorting.

int* mergeSort(int* nums, int size){

int* left; 
    int* right;
int middle = size/2;

if(size <= 1)
    return nums;

split(nums, size, &left, &right, middle);

//I dont understand why the code below wouldnt work in place of the split()
//when i run it, in main, nothing gets printed out. I guess i lose my pointer to the beginning of my array.
//left = nums;
//right = nums+middle;

left = mergeSort(left, middle);
right = mergeSort(right, size - middle);

merge(nums,left,right,middle,size - middle);
free(left);
free(right);
    return nums;
}

void split(int* nums, int size, int** left, int** right, int middle){

int *lft = (int*) malloc ((sizeof(int) * middle));
int *rght = (int*) malloc ((sizeof(int) * size - middle));
    int mid = middle;
    int upMid = size - middle;
int i;
for(i=0; i < mid; i++)
    lft[i] = nums[i];
for(i=0; i < upMid; i++)
    rght[i] = nums[i+middle];
    *left = lft;
    *right = rght;
}

void merge(int* num, int* left, int* right, int sizeLeft, int sizeRight){

int i,j,k,n;

i=j=k=0;
n=sizeLeft + sizeRight;

while(k < n){
    if(i< sizeLeft){
        if(j<sizeRight){
            insert(num,left,right,&i,&j,&k);
        }
        else{
            append(num, left, sizeLeft, &i, &k);
        }
    }
    else{
        append(num,right,sizeRight,&j,&k);
    }   
  }
}

void insert(int* num, int* left, int* right, int* i, int* j, int* k){

/*int i,j,k,n;*/

if(left[*i]<right[*j]){
    num[*k] = left[*i];
    (*i)++;
}
else{
    num[*k] = right[*j];
    (*j)++;
    }
 (*k)++;
}

void append(int* num, int* half, int sizeHalf, int* i, int* k){

while(*i < sizeHalf){
    num[*k]= half[*i];
    (*i)++; (*k)++;
 }
}

I would greatly appreciate any feedback on this question of mine, and any advice on maybe making my mergesort function more efficient. Thanks!!

Check out the Variants section of the Wikipedia article on mergesort for suggestions of ways to reduce the amount of space or copying. If space isn't an issue, one solution is to pre-allocate a NEW array the same length as the ORIGINAL, and then alternate whether your merges are combine (and append) sublists from ORIGINAL->NEW or from NEW->ORIGINAL. — pjs
– pjs, Commented Apr 18, 2015 at 23:38
Ahhh, thanks. I think what I will probably change is instead of allocating new arrays each time. I will just assign my *left and *right to the address of the expected value of each in the nums array. and just work on the numbers my shortening the view of my array. Hopefully I can get that to work correctly — St-rm
– St-rm, Commented Apr 19, 2015 at 0:16

KudoCC · Accepted Answer · 2015-04-19 13:08:10Z

0

I have implemented a merge sort algorithm, you can have a look. I malloc a bak array at the beginning of mergeSort and every merge use the it afterwards.

#include <string>
#include <stdlib.h>

void _mergeSort(int *array, int *bakArray, int len) ;

void mergeSort(int *array, int len)
{
    int *bak = (int *)malloc(sizeof(int)*len) ;
    _mergeSort(array, bak, len) ;
    free(bak) ;
}

void _mergeSort(int *array, int *bakArray, int len)
{
    if (len >= 2) {
        int leftLen = len/2 ;
        _mergeSort(array, bakArray, leftLen) ;
        _mergeSort(array+leftLen, bakArray, len-leftLen) ;
        int *pa = array ;
        int *pb = array+leftLen ;
        int aIndex = 0 ;
        int bIndex = 0 ;
        while (aIndex < leftLen && bIndex < len-leftLen) {
            int a = pa[aIndex] ;
            int b = pb[bIndex] ;
            if (a < b) {
                bakArray[aIndex+bIndex] = a ;
                ++aIndex ;
            } else if (a == b) {
                bakArray[aIndex+bIndex] = a ;
                bakArray[aIndex+bIndex+1] = a ;
                ++aIndex ;
                ++bIndex ;
            } else {
                bakArray[aIndex+bIndex] = b ;
                ++bIndex ;
            }
        }
        if (aIndex < leftLen) {
            memcpy(bakArray+aIndex+bIndex, pa+aIndex, sizeof(int)*(leftLen-aIndex)) ;
        } else if (bIndex < len-leftLen) {
            memcpy(bakArray+aIndex+bIndex, pb+bIndex, sizeof(int)*(len-leftLen-bIndex)) ;
        }
        memcpy(array, bakArray, sizeof(int)*len) ;
    }
}

static const int MaxArraySize = 100 ;
int main()
{
    srand(time(NULL)) ;
    int array[MaxArraySize] ;
    for (int i = 0 ; i < MaxArraySize; ++i) {
        array[i] = rand() % 10000 ;
    }
    mergeSort(array, MaxArraySize) ;
    for (int i = 0 ; i < MaxArraySize; ++i) {
        printf("%d ", array[i]) ;
    }
    printf("\n") ;
    return 0 ;
}

answered Apr 19, 2015 at 13:08

KudoCC

6,9721 gold badge26 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

St-rm Over a year ago

Thanks I appreciate your answer. I understand what you did to solve it but I just feel like there is something Im missing regarding the way my split function is written. Right now Im debugging it and my split function it now just sets left to point to the begining of my nums array, and right to point to the middle. I dont understand how this wouldnt yield the same results. I also dont know how to comment with a code example, so ill edit my post to show what i think should work too.

Collectives™ on Stack Overflow

Confusion about my QuickSort algorithm & Mergesort algorithm

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related