How to determine the fastest sorting algorithm out of two?

Question

I have two algorithms.

1.

 void sort3(int *mass, int size)
{
    int i = 0;
    int j = size - 1;
    int temp;
    int mid = mass[size / 2];
    do
    {
        while (mass[i] < mid)
        {
            i++;
        }
        while (mass[j] > mid)
        {
            j--;
        }
        if (i <= j)
        {
            temp = mass[i];
            mass[i] = mass[j];
            mass[j] = temp;
            i++;
            j--;
        }
    } while (i <= j);

    if (j > 0)
    {
        sort3(mass, j + 1);
    }
    if (i < size)
    {
        sort3(&mass[i], size - i);
    }
}

2.

void sort4_prepare(int *mass, int size)
{
    int middle, start_left, start_right, last;
    int *work_mas = new int[size];
    middle = size / 2;
    start_left = 0;
    start_right = middle;
    last = size;
    for (int j = 0; j < last; j++)
    {
        if ((start_left < middle) && ((start_right >= last) || (mass[start_left] < mass[start_right])))
        {
            work_mas[j] = mass[start_left];
            start_left++;
        }
        else
        {
            work_mas[j] = mass[start_right];
            start_right++;
        }
    }
    for (int j = 0; j < last; j++)
        mass[j] = work_mas[j];
    delete[] work_mas;
};

void sort4(int *mass, int size)
{
    if (size > 1)
    {
        sort4(mass, size / 2);
        sort4(&mass[size / 2], size - size / 2);
        sort4_prepare(mass, size);
    }
}

I also have an array of 1000 random numbers sorted from maximum to minimum. Which of the algorithms will sort the array from minimum to maximim faster? I have done some tests and I think that it is the first one, but I don't know how to prove it. However, in some cases the second one would be faster than the first, and that makes me a little bit unsure in the tests.

why not repeat 10000 times each time with a random array, and measure the total time? — trincot
– trincot, Commented Oct 17, 2017 at 19:02
Mathematics cannot help, as the atomic durations of each operation are not known and depend on implementation (compiler & processor) aspects. You could look into determining the time complexity, but that is no guarantee that one algo will run faster than another for a given input, only that one will run faster when the input is large enough (which could be very large). — trincot
– trincot, Commented Oct 17, 2017 at 19:19

trincot · Accepted Answer · 2017-10-17 19:46:02Z

sort3 is an implementation of QuickSort which has a O(n²) time complexity in the worst case, but O(nlogn) on average.

sort4 is an implementation of MergeSort which has a performance of O(nlogn) both in worst and average case.

However, this does not mean that sort4 is guaranteed to be faster for your array of 1000 numbers, even in Quicksort's worst case scenario. It only means that for some category of arrays (the Quicksort's "worst case" kind of arrays), there exists an array size above which sort4 will be faster. Nothing can be said about the time needed to sort any arrays on average, as they both have the same time complexity on average.

Furthermore, you'll have no clue which size it is above which Mergesort will perform better on Quicksort's "worst case" arrays, as this depends on implementation issues: for example, one compiler may compile your code in a way that the delete operation in sort4 is very costly in terms of time, and so for most reasonably sized arrays, sort3 might turn out to be always faster. This is not far-fetched, as indeed, sort4 differs from sort3 in that it needs to create an extra array to copy values into, to then delete that array again. This is overhead that sort3 does not have.

The only practical way to determine whether on average one function sorts faster than the other for a given array size, is to get a statistical measure: repeat the sort operation a number of times that is representative on some randomly populated arrays, and measure the time difference. But the outcome of such test can well be different when run on different configurations.

Collectives™ on Stack Overflow

How to determine the fastest sorting algorithm out of two?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related