10 Replies - 543 Views - Last Post: 28 February 2012 - 12:24 PM Rate Topic: -----

#1 bardown91  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 20-February 12

Selection sort Algorithm

Posted 20 February 2012 - 07:55 PM

Hello I am running into a few problems in generating a Selection sort. Here is what I have so far.

#include <iostream>

using namespace std;

int main() {
	const int SIZE = 27;
	int end = 26;
	int values[SIZE] = {12,94,56,23,41,34,27,31,24,86,54,67,34,59,11,9,77,22,91,64,21,85,71,60,30,44,18};
	cout << "Initial Values:\n";
	for(int i = 0; i < SIZE; i++) {
		cout << values[i] << " ";
	}
	cout << endl;

	while(end > 0) {




after this step I know I need to find the largest value between 0 and end.. and am trying to find the location of the largest value because i plan on swapping values.

This is entirely independent study via youtube/internet. and am looking for a resourceful c++ response to creating a selection sort.

:code: Just one tag at the beginning, and the other one at the end.

This post has been edited by r.stiltskin: 20 February 2012 - 08:06 PM
Reason for edit:: Fixed the code tags.


Is This A Good Question/Topic? 0
  • +

Replies To: Selection sort Algorithm

#2 bardown91  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 20-February 12

Re: Selection sort Algorithm

Posted 20 February 2012 - 08:18 PM

I need to find the values for n and the n list items but am having troubles formatting that selection process
Was This Post Helpful? 0
  • +
  • -

#3 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Selection sort Algorithm

Posted 20 February 2012 - 09:38 PM

I can't improve on Wikipedia's description of the algorithm, which is:

1. Find the minimum value in the list
2. Swap it with the value in the first position

Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)

You should try to implement each of those steps in actual code and if you can't work it out then post your code and explain what your difficulty is.
Was This Post Helpful? 0
  • +
  • -

#4 bardown91  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 20-February 12

Re: Selection sort Algorithm

Posted 20 February 2012 - 09:58 PM

right, I get the basic concept of sort selection. Moving the unsorted subsection left and sorted subsection right until numbers are numerically arranged. But what I don't understand is how to set the marker for the unsorted section at the end of the list, and how to move the marker as numbers are sorted. I realize the "end" is inside the array as opposed to SIZE but Im trying to swap the end with the largest value but i have no idea how to call a temporary variable or the best way to find the largest number on my list.
Was This Post Helpful? 0
  • +
  • -

#5 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Selection sort Algorithm

Posted 20 February 2012 - 10:14 PM

You seem to be under the impression that you have to move entire sections of the array at one time. Actually you only move a single element at a time. After the first "find minimum and swap" the smallest element is the first element and that single element is the sorted portion of the array. From that point on you ignore that element; you start at the second element and "find minimum and swap". After that iteration, the first two elements in the array are the sorted portion; from then on you ignore them and start at the third element, and so on.

And "setting a marker" is simply incrementing an index variable in the loop control expression -- exactly the same as you did when you printed the contents of the array.
Was This Post Helpful? 0
  • +
  • -

#6 bardown91  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 20-February 12

Re: Selection sort Algorithm

Posted 20 February 2012 - 10:58 PM

thank you for the timely responses, I may be just confusing basics here...



I believe my for statement should look something like this, But I am Having troubles with my While statement. any help>

  for(int i = 0 ; i < 20; i++) {
for (int j = i ; j < 20 ; j++) { 
}
swap lowest into arr[i] 
}


Was This Post Helpful? 0
  • +
  • -

#7 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Selection sort Algorithm

Posted 20 February 2012 - 11:20 PM

I think you need to master the basics of working with loops before you can deal effectively with sorting. Here's a pretty good tutorial on control structures (which includes for and while loops).
Was This Post Helpful? 0
  • +
  • -

#8 bardown91  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 20-February 12

Re: Selection sort Algorithm

Posted 20 February 2012 - 11:37 PM

Ok so as I understand I must find my largest number so far before I start sorting.

while(i < SIZE) {
		if(largestSoFar < values[i]) {
			largestSoFar = values[i];
			location = i;
		}
		i = i + 1;
	}
	cout << "The largest element was " << largestSoFar << " and was in location " << location << ".\n";



but then how do i exchange the largest value found with the value at the end and repeat the process without having to code a separate line for each sort? and then from there do I assign letters as my temporary variables??
Was This Post Helpful? 0
  • +
  • -

#9 bardown91  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 20-February 12

Re: Selection sort Algorithm

Posted 21 February 2012 - 12:25 AM

  for(int i = 0; b > 56 ; i++) {
for(int b=i ; b> 56; i++){
}swap lowest into arr[i] }



any better? not sure if b is the right variable to call, or if i even assign letters to numbers.
Was This Post Helpful? 0
  • +
  • -

#10 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Selection sort Algorithm

Posted 21 February 2012 - 07:19 AM

View Postbardown91, on 21 February 2012 - 02:25 AM, said:

  for(int i = 0; b > 56 ; i++) {
for(int b=i ; b> 56; i++){
}swap lowest into arr[i] }



any better? not sure if b is the right variable to call, or if i even assign letters to numbers.

I don't know where 56 came from. Looking back at Post #1, the size of the array was 27.

Anyway, you shouldn't use "magic numbers" (numbers whose meaning isn't apparent when you look at them). You started off on the right track when you defined the constant SIZE. Use it. Also, why start off with such a big array for testing? I'd start with something much smaller, like 6. That way it'll be easy to quickly make up different configurations for testing: all unique, some repeating, all the same, already sorted, already sorted in reverse, etc. You need to test your program under as many conditions as you can think of.

On line 1 (the outer loop control statement) b doesn't exist yet. i is the control variable there. And for the limiting value, you should use your constant SIZE instead of the magic number. And finally, the control variable in this loop should always remain LESS than, not GREATER than the limiting value, so
for(int i = 0; i < SIZE; i++) {
    // ...

Was This Post Helpful? 1
  • +
  • -

#11 bardown91  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 20-February 12

Re: Selection sort Algorithm

Posted 28 February 2012 - 12:24 PM

Thank you for your responses r.stiltskin. !
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1