LinuxQuestions.org
Welcome to the most active Linux Forum on the web.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 03-08-2011, 09:55 AM   #1
comp_brad1136
Member
 
Registered: Nov 2004
Location: SW Missouri, USA
Distribution: Debian 6 "Squeeze"
Posts: 55

Rep: Reputation: 7
learning c++, confusing array sort


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;
}
 
Old 03-08-2011, 10:16 AM   #2
johnsfine
Guru
 
Registered: Dec 2007
Distribution: Centos
Posts: 5,125

Rep: Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119Reputation: 1119
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.

Last edited by johnsfine; 03-08-2011 at 10:22 AM.
 
  


Reply

Tags
loops, programing


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
sort 2-d array in perl monkeyorhunter Programming 1 03-07-2011 09:52 PM
Sort an array rahulruns Programming 3 11-17-2009 06:50 AM
Sort an array in python J_Szucs Programming 3 06-15-2008 05:33 PM
selection sort compiles but does not sort the array as desired ganesha Programming 2 04-20-2008 08:44 AM
confusing array of structs kpachopoulos Programming 1 11-23-2005 03:13 PM


All times are GMT -5. The time now is 10:19 PM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration