CODEWITHSUNDEEP
cperformancealgorithmsortingquicksort
user2272255
user2272255

Reputation: 45

Quick sort runtime speed concerns

I am having something that troubles me. I have my implementation of a quick sort algorithm, but when I test it on an array of integers that has over 30 elements, sorting takes, in my opinion to long. Sometimes even more than 10 seconds, unlike with selection sort, insertion sort and bubble sort, which are faster on 10000 elements than quick sort on 100 elements.

Here is my solution, please give advice :)

void kvikSort(int a[], int l, int d) {
    int i, k;

    if (l >= d)
        return;

    k = l;
    swap(&a[l], &a[(l + d) / 2]);

    for (i = l + 1; i <= d; i++)
        if (a[i] < a[l])
            swap(&a[++k], &a[i]);
    swap(&a[l], &a[k]);

    kvikSort(a, 0, k-1);
    kvikSort(a, k+1, d);

}

EDIT: I am using GCC v 4.7.2 on my Linux Mint 14, proc: intel core2duo e7400

EDIT: My other algorithms:

void selectionSort(int a[], int n) {
    int i, j, min;

    for (i = 0; i < n - 1; i++) {
        min = i;
        for (j = i + 1; j < n; j++)
            if (a[j] < a[min])
                min = j;
        if (min != i)
            swap(&a[min], &a[i]);
    }
}


void insertionSort(int a[], int n) {
    int i, j;

    for (i = 0; i < n - 1; i++)
        for (j = i + 1; j > 0 && a[j] < a[j-1]; j--)
            swap(&a[j], &a[j-1]);
}


void bubbleSort(int a[], int n) {
    int i, j;

    for (i = n - 1; i > 0; i--)
        for (j = 0; j < i; j++)
            if (a[j] > a[j+1])
                swap(&a[j], &a[j+1]);
}


void swap(int *i, int *j) {
    int tmp;

    tmp = *i;
    *i = *j;
    *j = tmp;
}

EDIT: Maybe I should mention that in my test program I am first outputing randomly generated array to a text file, then sorted array to another text file. So it is certainly running slow, but that's not the problem, the problem is that quick sort runs a lot slower than the rest.

Upvotes: 1

Views: 375

Answers (2)

RBarryYoung
RBarryYoung

Reputation: 56735

Here's the problem:

void kvikSort(int a[], int l, int d) {
int i, k;

if (l >= d)
    return;

k = l;
swap(&a[l], &a[(l + d) / 2]);

for (i = l + 1; i <= d; i++)
    if (a[i] < a[l])
        swap(&a[++k], &a[i]);
swap(&a[l], &a[k]);

>>> kvikSort(a, 0, k-1);
kvikSort(a, l, k-1);
kvikSort(a, k+1, d);

Upvotes: 1

Daniel Fischer
Daniel Fischer

Reputation: 183888

Your first recursive call

kvikSort(a, 0, k-1);

has the wrong lower bound, it should be

kvikSort(a, l, k-1);

With a lower bound of 0, you re-sort the initial part of the array again and again.

Upvotes: 4

Related Questions