Selection Sort Algortithm

[lost110]

Hello! Is the below code fine! I mean the idea of selection sort is that for each value of n, the inner for loop will execute n times, then n-2 times, then n-3 .....so on! Isn't it so?

  #include<iostream>
using namespace std;
int main()
{
	int n,i,j;
	cin >> n;
	for ( i=0; i<=n-1; i++) 
	{
		for (j = i + 1; j <=n; j++) 
		{
			cout << "executed" << endl;
		}
		cout << "break" << endl;
	}
	system("pause");
}

[doug4]

First of all, nothing is being sorted.

Second of all, this code is similar to a bubble sort, not a selection sort.

so, not, the code is not fine.

[lost110]

Hye @dough4 I am just doing the loop analysis here. I am not implementing selection sort here! I am just seeing how the nested loops are behaving. That how much time the inner loop executes.
Isn't this concept only for selection sort? i.e the inner for loop will execute n times, then n-2 times, then n-3 .....so on!
e.g:
user enters 5 .
the inner loop runs 5 times
then ....................4 times
...........................3 times...so on!

[Handy Andy]

Hello lost110,

If you want to test something try this:

#include<iostream>

using namespace std;

int main()
{
    constexpr int MAXSIZE{ 5 };
    int numArr[MAXSIZE]{ 99, 25, 42, 80, 10 };
    int arrUsed{};

    std::cout << "\n Enter 5.: ";
    cin >> arrUsed;

    std::cout << '\n';

    for (int i = 0; i <= arrUsed - 1; i++)
    {
        for (int j = i + 1; j <= arrUsed; j++)
        {
            cout << " executed when i = " << i << " array element is " << numArr[i] << " when j = " << j << " array elemnnt is " << numArr[j] << '\n';
        }

        cout << "break" << endl;
    }

	// The next line may not be needed. If you have to press enter to see the prompt it is not needed.
	std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');  // <--- Requires header file <limits>.
	std::cout << "\n\n Press Enter to continue: ";
	std::cin.get();

	return 0;  // <--- Not required, but makes a good break point.
}

The output is:

// numArr[MAXSIZE]{ 99, 25, 42, 80, 10 }

 Enter 5.: 5

 executed when i = 0 array element is 99 when j = 1 array elemnnt is 25
 executed when i = 0 array element is 99 when j = 2 array elemnnt is 42
 executed when i = 0 array element is 99 when j = 3 array elemnnt is 80
 executed when i = 0 array element is 99 when j = 4 array elemnnt is 10
 executed when i = 0 array element is 99 when j = 5 array elemnnt is 0
break
 executed when i = 1 array element is 25 when j = 2 array elemnnt is 42
 executed when i = 1 array element is 25 when j = 3 array elemnnt is 80
 executed when i = 1 array element is 25 when j = 4 array elemnnt is 10
 executed when i = 1 array element is 25 when j = 5 array elemnnt is 0
break
 executed when i = 2 array element is 42 when j = 3 array elemnnt is 80
 executed when i = 2 array element is 42 when j = 4 array elemnnt is 10
 executed when i = 2 array element is 42 when j = 5 array elemnnt is 0
break
 executed when i = 3 array element is 80 when j = 4 array elemnnt is 10
 executed when i = 3 array element is 80 when j = 5 array elemnnt is 0
break
 executed when i = 4 array element is 10 when j = 5 array elemnnt is 0
break

On my computer I get this

 executed when i = 0 array element is 99 when j = 5 array elemnnt is -858993460

Either example means that you are going past the end of the array. The "<=" is causing this. In a for loop using the "<=" should be rare. Most often you just need "<".

When you change the "<=" to just "<" the outout is:

// numArr[MAXSIZE]{ 99, 25, 42, 80, 10 }

 Enter 5.: 5

 executed when i = 0 array element is 99 when j = 1 array elemnnt is 25
 executed when i = 0 array element is 99 when j = 2 array elemnnt is 42
 executed when i = 0 array element is 99 when j = 3 array elemnnt is 80
 executed when i = 0 array element is 99 when j = 4 array elemnnt is 10
break
 executed when i = 1 array element is 25 when j = 2 array elemnnt is 42
 executed when i = 1 array element is 25 when j = 3 array elemnnt is 80
 executed when i = 1 array element is 25 when j = 4 array elemnnt is 10
break
 executed when i = 2 array element is 42 when j = 3 array elemnnt is 80
 executed when i = 2 array element is 42 when j = 4 array elemnnt is 10
break
 executed when i = 3 array element is 80 when j = 4 array elemnnt is 10
break


 Press Enter to continue:

Which is what you want.

As doug4 said this is a good start for a bubble sort. What you need to start with is code for a selection sort. Then play with that until you understand it.

Andy

[lost110]

I have seen bubble sort recently. The for loop functionality is same there just as in selection sort.

[ne555]

> Hye @dough4 I am just doing the loop analysis here. I am not implementing selection sort here!
then consider a better title and description.
if you just want to see the order, yes, two nested loop O(n^2)
if you want to actually count the iterations, you are off by 1 in your conditions as shown by Handy Andy (perhaps you should bother to actually write the algorithm to make sure it is correct)


> this code is similar to a bubble sort, not a selection sort.
both may work, it hard to identify it without the body


> Isn't this concept only for selection sort? i.e the inner for loop will
> execute n times, then n-2 times, then n-3 .....so on!
I would call that a side effect, not a concept, also it starts at `n-1' not at `n'

the concept of selection sort is «extract the minimum of the remaining items and put it at the end of the sorted array»
the concept of insertion sort is «extract one item and place it in its proper position on the current sorted array»
the concept of bubble sort is «my neighbour is an idiot that thinks is more important than me, I'll teach a lesson»


> I have seen bubble sort recently. The for loop functionality is same there
> just as in selection sort.
I have no idea what are you trying to say with «loop functionality»
bubble sort may not do `n-1' iterations as it has an `is_sorted()' function incorporated

[jonnin]

most of the slow sorts look similar. They are, in reality, minor tweaks or variation on bubble sort. For example (from memory) selection skips extra work (that bubble does) if its in reversed order, insertion skips extra if its already in the right order, (and this applies to being nearly in best/worst order too), and so on. Whether these 'improvements' matter or not depends on your needs. Often data is changed a little and sorted again, having been already sorted, and taking advantage of that can be a big deal (shell sort, the best of the non-recursive multi-loop types, also has this advantage).

[ne555]

> They are, in reality, minor tweaks or variation on bubble sort
I don't understand how you reach such conclusion
it's like voodoo programming, change a sign here and there, ¡behold, a new sorting algorithm!
sure, the code does look similar, but the underlying ideas, the mechanisms of why they work, are totally unrelated

> For example (from memory) selection skips extra work (that bubble does) if
> its in reversed order
consider this pseudocode (the subarray is not copied, len() is O(1))

def selection_sort(array):
	for K in range(len(array)-1):
		min_index = min_element(array[K:])
		if K not_eq min_index:
			swap(array[K], array[min_index])

def min_element(array):
	min_index = 0
	for K in range(1, len(array)):
		if array[K] < array[min_index]:
			min_index = K
	return min_index

regardless of the start order of the array, the algorithm always does the same number of comparisons
however, at worst it will do n-1 swaps, which is good if the objects are big
so it's an indirect sort that only requires O(1) extra memory

another good thing is within the min_element() function
there are better implementations to extract the minimum element from a set, like a binary search tree (treesort) or a priority queue (heapsort) which gives you O(n lg n)


kind of hate the fascination with teaching bubble-sort, the algorithm is bad, is not quite clear how it works (¿how many iterations? ¿does it stop?), it has an embed (not visible) is_sorted() function and the bubbles are rocks.

[jonnin]

I don't understand how you reach such conclusion
sure, the code does look similar, but the underlying ideas, the mechanisms of why they work, are totally unrelated...

they all find a victim and move it to its final location. I think if you handed a new coder the code for bubble sort and told them to improve on it, I would have ended up with one of the others after a bit of poking at it. Its different, but not that far off.

I also dislike bubble sort. I guess its OK for intro to run-time analysis study. It was more profound when bubble sorting 1000 items took an hour... that made one pay attention. Now its like 10 nanoseconds vs 1 nanosecond and the students probably miss the implications. I can't imagine a modern school having the class tie up the computers for 2 days running sorts overnight...

[dhayden]

I have seen bubble sort recently. The for loop functionality is same there just as in selection sort.

Yes. The difference is that selection sort swaps items once (at most) each time the inner loop runs while bubble sort might swap items for each iteration of the inner loop. So bubble sort does more work on average than selection. However, since the amount of work in the inner loop is constant for each algorithm, the big-O time is the same (O(n²)

You loops are correct. People got confused because you didn't actually implement the algorithm within the loops.

[ne555]

> You loops are correct.
no, they are off by 1
should use < instead of <=

[anup30]

>

Hye @dough4 I am just doing the loop analysis here. I am not implementing selection sort here! I am just seeing how the nested loops are behaving. That how much time the inner loop executes.
Isn't this concept only for selection sort? i.e the inner for loop will execute n times, then n-2 times, then n-3 .....so on!
e.g:
user enters 5 .
the inner loop runs 5 times
then ....................4 times
...........................3 times...so on!

I have seen bubble sort recently. The for loop functionality is same there just as in selection sort.

if n is the size of array to be sorted, then inner loop of selection sort 'compares' (not 'execute') n-1 times (not n), then n-2, n-3, .... 1 times.

but the inner loop of bubble sort 'compares' n times in all run for outer for loop.