Thread: What is this sorting technique?

I have an

Code:

 array[4] =  {5, 3, 9, 1}

I compare the first index with the second and if the second index is smaller then I'll swap the first index with the second.
After 1st pass I get:

Code:

  {3, 5, 9, 1}

I then compare the first index with the third index and if the third index is smaller then I'll swap. In this case it isn't.
I'll then compare the first index with the fourth index and if the fourth index is smaller I'll swap it with the first index.
After this pass I get:

Code:

 {1, 5, 9, 3}

I will then compare the second index with every index that follows so I'll get:

Code:

 {1, 3, 9, 5}

then

Code:

  {1, 3, 5, 9}

Can someone tell me the name of this sorting algorithm?
I'm trying to do some research on it but I don't have a name for it.

Originally Posted by Amrita Ramnauth

I then compare the first index with the third index and if the third index is smaller then I'll swap.

It should be "I then compare the original first index with the third index" since '5' (in your example) is now actually the second index after the first swap and so on. So I think you're trying to arrange the numbers in ascending order. Search by this term and it might be what you're looking for.

That sounds like a Selection Sort:

https://en.wikipedia.org/wiki/Selection_sort

Is this the algorithm you mean?

Code:

void mystery_sort(int a[], int n) {
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] > a[j]) {
                int t = a[i];
                a[i] = a[j];
                a[j] = t; 
            }
}

I also think it's a kind of selection sort, but an inefficient one that does too many swaps. In a normal selection sort you find the smallest element and swap it into the first position, then find the next smallest and swap it into the second position, etc. In your sort you swap every time you find a smaller element than the one currently in the first position, etc. The effect is the same in that the smallest element is moved to the first position, then the second smallest to the second position, etc.

A more usual selection sort:

Code:

void selection_sort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int k = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[k])
                k = j;
        int t = a[i];
        a[i] = a[k];
        a[k] = t; 
    }
}

Obviously selection_sort will be faster than mystery_sort since it implements essentially the same algorithm but does fewer swaps.

Yes it's like the selection sort but it's not as efficient as the selection sort. And the algorithm you posted for it is correct.
I just wanted to know if that sort exists and what's the name of it if you know.
I'm doing a comparison of it to the selection sort.

Originally Posted by Amrita Ramnauth

Yes it's like the selection sort but it's not as efficient as the selection sort. And the algorithm you posted for it is correct.
I just wanted to know if that sort exists and what's the name of it if you know.
I'm doing a comparison of it to the selection sort.

If it has a name it would be something like "stupid selection sort".

I'm trying to sort 500k random numbers in my codeblocks compiler which I call from a .txt file. When I run the program it just gives me a blinking pointer to the top and does nothing. Any idea of what's happening there?

I can get to sort up to 100,000

Hmm I see
Thanks

For me it takes about 10 seconds for 100000 elements and 40 seconds for 200000. This is nicely in line with the quadratic time complexity: double the number of elements, four times the time. So I predict 500000 would take about 250 seconds (4 minutes and 10 seconds).

Yes the program reads the .txt file
That's what I meant
My bad