[SOLVED] learning c++, confusing array sort

comp_brad1136 · 03-08-2011, 08:55 AM

The website I'm studying calls this a "Selection Sort."
I'm wanting to understand why this works, so I can continue to other chapters. Can Someone please explain how/why this particular loop works?

Code:

#include <iostream>
#include <algorithm>

int main(){
	using namespace std;
	const int nArraySize = 5;
	int nAnArray[nArraySize] = {15, 32, 8, 64, 82};
	// Start selection sort
	for (int nStartIndex = 0; nStartIndex < nArraySize; nStartIndex++){
		int nSmallestIndex = nStartIndex;
		for (int nCurrentIndex = nStartIndex +1; nCurrentIndex < nArraySize; nCurrentIndex ++){
			if (nAnArray[nCurrentIndex] < nAnArray[nSmallestIndex])
				nSmallestIndex = nCurrentIndex;
		}
		swap(nAnArray[nStartIndex], nAnArray[nSmallestIndex]);
	}
	// Display results
	for (int nArrayIndex = 0; nArrayIndex < nArraySize; nArrayIndex++){
		cout << nAnArray[nArrayIndex] << endl;
	}
	return 0;
}

johnsfine · 03-08-2011, 09:16 AM

The outer loop goes through all the positions in that array.

For each step of the outer loop, the inner loop finds the value that belongs in the position selected by the outer loop. Then the swap function is used to swap the value that was in that position with the value that belongs in that position.

When looking for the value that belongs in a position, you obviously do not want to consider the smaller values that have already been placed in their final location earlier in the array. Since you don't consider those, the value that should be placed in the current position is always the smallest value that has not yet been moved to its final position.

In your example it would
Find the smallest of 15, 32, 8, 64, 82 and swap that with the 15 to get 8, 32, 15, 64, 82
Find the smallest of 32, 15, 64, 82 and swap that with the 32 to get 8, 15, 32, 64, 82
Find the smallest of 32, 64, 82 and swap that with the 32, which changes nothing.
Find the smallest of 64, 82 and swap that with the 64, which changes nothing.
Done.