0

With the likes of the other n2 sorting algorithms like Bubble, Selection, and Insertion which 'worst case' does 18 element compares, or so, on a 10 element array in order to get 2 elements in order, I 'sort of' found one that does this with measly 13 element compares! Though this is a constant pace; there is no 'worst case', in a sense.

Not really ground breaking as it's only 40% faster than Bubble, maybe 50% if I revise the code, and it's slower than Selection. However, in theory, it's the fastest n2 algorithm in terms of number of compares. The downfall is that it does a lot of switches in practice.

I achieve this by first doing compares of every other two elements. 'Pairing'.
x cmp x[i+1]; i+=2;
With this I know for a fact that the 'set' of the latter and former of compared elements contain both the highest and lowest elements, which I called the extremes. It's just a matter of looking for them: Selection. Voila!

I guess where I'm getting at is does this already exist? Or is this just a convoluted variant of an existing one? I'd like to get some extra credit but I wouldn't want to submit a used idea. Also, what do you think?

I may have written it a bit 'cryptic' as to maybe minimize random ripoffs. lol

Edited by asrockw7: n/a

3
Contributors
4
Replies
5
Views
5 Years
Discussion Span
Last Post by asrockw7
0

I may have written it a bit 'cryptic' as to maybe minimize random ripoffs.

Let's start with this. You're not going to make money off of this algorithm, and the bragging rights are tangential to devising a solid algorithm. I wouldn't worry about anyone ripping off your idea, but being cryptic certainly makes it difficult for interested parties to use it if it applies to their problem or help answer your question.

I achieve this by first doing compares of every other two elements. 'Pairing'.

Given your cryptic description, I'd say you've come up with a variant of Shell sort. Or at the very least, an algorithm that moves in the same direction as Shell sort by grouping elements in a way that speeds up the process.

0

I know I won't make money off it. I don't know, it felt right at the time. lol Okay, I'll extend it.

OMG I can't edit it. Okay, I'll do it here.

So basically I sort the array initially in pairs:
x cmp x[i+1]; i+=2;
x[0] cmp x[1], x[2] cmp x[3],... Like so

Inherently, those of the indexes 0, 2, 4,... and 1, 3, 5... will contain either the highest or lowest element depending on how you compare each pair. So now that we know that, we can just search through both sets and put them in their rightful place: at both ends of the array. Then we just increment the first marker and decrement the last marker of the array and repeat the process.

You end up with an array being slowly sorted from each end meeting down the middle. If you end up with an odd number of elements, you just compare the odd one with the second to the last one:
x[n-1] opposite cmp x[n] such that the x[n] will be part of the latter set, along with indexes 0, 2, 4,... We still maintain the certainty that both sets will contain the extremes.

Edited by asrockw7: n/a

0
void pair_sort(int *array, size_t start, size_t end){
    size_t x, y;
    int temp;
    for(x = start, y = start+1; y <= end; y+=2, x+=2){
        if(array[x] > array[y]){
            temp = array[x];
            array[x] = array[y];
            array[y] = temp;
        }
    }
    y-=2; // Because +=2 is applied to y on terminating loop; therefore is always greater than end.
    if(y < end){ // Means an odd number of elements; When even: y == end
        if(array[end] > array[y]){
            temp = array[end];
            array[end] = array[y];
            array[y] = temp;
        }
    }
    return;
}
void look_and_place(int *array, size_t start, size_t end){
    size_t low = start, high = start+1; // assuming the first elements are the extremes. Selection Sort
    int temp;
    /* look */
    for(size_t x = start+2; x <= end; x+= 2){ // x is low
        if(array[x] < array[low]){
            low = x;
        }
    }
    for(size_t y = start+3; y <= end; y+= 2){ // y is high
        if(array[y] > array[high]){
            high = y;
        }
    }
    /* place */
    temp = array[start];
    array[start] = array[low];
    array[low] = temp;

    temp = array[end];
    array[end] = array[high];
    array[high] = temp;

    return;
}
void mysort_iter(int *array, size_t size){
    size_t start = 0, end = size-1;
    while(start < end){
        pair_sort(array, start, end);
        look_and_place(array, start, end);
        start++;
        end--;
    }
}
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.