CODEWITHSUNDEEP
calgorithmselection-sort
Guk
Guk

Reputation: 71

In selection sort, descending array's performance is faster than ascending array. why?

I ran selection sort algorithm with a sorted array(ascending order) and a unsorted array(decending order) in C visual studio. The result was performance of a unsorted array is faster than one of a sorted array in large size.

I think it's very ridiculous. Doesn't selection sort always take constant time depends on array size? Why is this??

This is selectionsort. And I ran this with n = 100,000 to 1,000,000. I increased it by 100,000 for every run.

int main() {
    int array[1000000]; //1,000,000
    int i = 100000; //100,000
    int n = 100000; //100,000
    for (int k = 0; k < 10; ++k) {
        insert_ascending(array, n); //stuff elements in ascending order
        //time check
        sort(array, n);

        insert_decending(array, n); //stuff elements in descending order
        //time check
        sort(array, n);

        n += i;
    }
}
void selectionSort(int *list, const int n)
{
    int i, j, indexMin, temp;

    for (i = 0; i < n - 1; i++)
    {
        indexMin = i;
        for (j = i + 1; j < n; j++)
        {
            if (list[j] < list[indexMin])
            {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    } 
}

Upvotes: 1

Views: 739

Answers (1)

Antti Haapala -- Слава Україні
Antti Haapala -- Слава Україні

Reputation: 133998

Here goes my 0.02 €.

I could see a 4 % speed difference favouring the descending array over ascending array in unoptimized code on GCC. My hypothesis is that it is caused by the

if (list[j] < list[indexMin]) {
    indexMin = j;
}

being compiled to

        ...
        jge     .L4
        mov     eax, DWORD PTR [rbp-8]
        mov     DWORD PTR [rbp-12], eax
.L4:
        add     DWORD PTR [rbp-8], 1

i.e. it is not a branch prediction failure - for the ascending case the jge always branches, and for the descending case it never branches. The jge taking the branch does take more cycles than actually updating the index variable in cache.

Of course, if you compile with optimization enabled, the ascending code wins.

Upvotes: 3

Related Questions