Am I dense, or is this normal...?

Selection sort is kicking my ass

Page 1 of 1

13 Replies - 651 Views - Last Post: 04 April 2010 - 11:12 AM Rate Topic: -----

#1 jhicks32917  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 02-April 10

Am I dense, or is this normal...?

Posted 03 April 2010 - 07:28 AM

Hi everyone,

So, I'm new to programming and I'm working my way down through a book. I've gotten to a Selection Sort exercise; I know this is a pretty common C++ exercise.
It is kicking my ass. Should I be able to understand this easier? Is this a sign I might be a bit too dense to learn to program effectively?

I cannot for the life of me figure out how to compare every number in the array to each other in order to find out the smallest number, or even if that is the right approach, and even if I
did, I don't think I could swap array[i] with array[p].

If it's normal to have a bit of a headache with this, please let me know, or if you just have something constructive, or a pointer in the right direction.

PS. If I come back and someone has posted the completed code for selection sort, I will find you.

Is This A Good Question/Topic? 0
  • +

Replies To: Am I dense, or is this normal...?

#2 Tapas Bose  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 23
  • View blog
  • Posts: 472
  • Joined: 09-December 09

Re: Am I dense, or is this normal...?

Posted 03 April 2010 - 07:31 AM

We will not do homework for you.
[rules]
[/rules]
Was This Post Helpful? 0
  • +
  • -

#3 jhicks32917  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 02-April 10

Re: Am I dense, or is this normal...?

Posted 03 April 2010 - 07:58 AM

View PostTapas Bose, on 03 April 2010 - 06:31 AM, said:

We will not do homework for you.
[rules]
[/rules]



...Please point me to where I asked someone to do my homework for me.
One, this isn't homework, this is what I want to do with my free time.
Two, I stated in my post that I did NOT want someone posting the finished code. I don't want it to be given to me.

Your welcome,


#include <iostream>
#include <string>
#include <stdlib.h>

using namespace std;

int main()
{
	int n[100];
	int p = 0;
	int min_index = 0;

	cout << "Enter ten unsorted intergers...\n";
	
	for (int i = 0; i < 11; ++i)
	{
		cout << "[" << i << "] = ";
		cin >> n[i];
	}

	cout << "Unsorted list: ";

	for (int i = 0; i < 11; ++i)
	{
		cout << n[i] << ", ";
	}
	cout << "Sorting...\n" << "Sorted list: ";

	for (int i = 0; i < 9; i++)
	{
		p = n[i];
		min_index = i;
		
		for (int j = (i+1); j < 10; j++)
		{
			if (n[j] < p)
			{
				p = n[j];
				min_index = j;
			}
		}
		n[i] = p;
		
	}
	for (int i = 0; i < 11; ++i)
	{
		cout << "[" << i << "] = " << n[i];
	}
	
	cout << endl;
	system("PAUSE");
}

This post has been edited by jhicks32917: 03 April 2010 - 07:59 AM

Was This Post Helpful? 0
  • +
  • -

#4 Tapas Bose  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 23
  • View blog
  • Posts: 472
  • Joined: 09-December 09

Re: Am I dense, or is this normal...?

Posted 03 April 2010 - 08:07 AM

jhicks32917 said:

PS. If I come back and someone has posted the completed code for selection sort, I will find you.

What does it mean? If you are willing to show your effort then burst it in the beginning.
Was This Post Helpful? 0
  • +
  • -

#5 tauit_dnmd  Icon User is offline

  • D.I.C Head

Reputation: 8
  • View blog
  • Posts: 129
  • Joined: 25-March 10

Re: Am I dense, or is this normal...?

Posted 03 April 2010 - 08:12 AM

1/ you want to enter 10 unsort number ,but you use a wrong loop:
for (int i = 0; i < 11; ++i)
        {
                cout << "[" << i << "] = ";
                cin >> n[i];
        }

and here is wrong:
for (int i = 0; i < 11; ++i)
        {
                cout << n[i] << ", ";
        }

--->you entering 11 number in here.only loop when i <10 :
for (int i = 0; i < 10; ++i)
        {
                cout << "[" << i << "] = ";
                cin >> n[i];
        }

--and sort function should be like this:
cout << "Sorting...\n" << "Sorted list: ";

        for (int i = 0; i < 9; i++)
        {
                min_index = i;
                
                for (int j = (i+1); j < 10; j++)
                {
                        if (n[j] < n[min_index])
                        {
                                min_index = j;
                        }
                }
                int temp=n[i];
                n[i]=n[min_index];
                n[min_index]=temp;
        }

Was This Post Helpful? 1
  • +
  • -

#6 jhicks32917  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 02-April 10

Re: Am I dense, or is this normal...?

Posted 03 April 2010 - 08:14 AM

View PostTapas Bose, on 03 April 2010 - 07:07 AM, said:

jhicks32917 said:

PS. If I come back and someone has posted the completed code for selection sort, I will find you.

What does it mean? If you are willing to show your effort then burst it in the beginning.


It's a joke, like a threat. Me saying if you post the completed code I will find you IRL and inflict pain :P
Again, just a joke, but it was me letting everyone know that I don't want it to be given to me.
I suppose I should have been more clear.
Was This Post Helpful? 0
  • +
  • -

#7 jhicks32917  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 02-April 10

Re: Am I dense, or is this normal...?

Posted 03 April 2010 - 08:28 AM

Thanks tauit, I've got it figured out now. I'm going to read through some more tutorials so I'm sure I've gotten everything understood.
Was This Post Helpful? 0
  • +
  • -

#8 jhicks32917  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 02-April 10

Re: Am I dense, or is this normal...?

Posted 03 April 2010 - 09:58 AM

So, I've been over the code a few times and rewritten it, and I can't seem to understand why in this code

for(int i = 0; i < 9; i++)
	{
		min_index = i;
		for(int j = (i+1); j < 10; j++)
		{
			if(n[j] < n[min_index])
			{
				min_index = j;
			}
		temp = n[i];
		n[i] = n[min_index];
		n[min_index] = temp;
		}
	}


i < 9 in the first loop and i < 10 in the nested loop.
It seems like it should be reversed, at least in my mind, but I know it doesn't quite work out that way, haha.
Was This Post Helpful? 0
  • +
  • -

#9 tauit_dnmd  Icon User is offline

  • D.I.C Head

Reputation: 8
  • View blog
  • Posts: 129
  • Joined: 25-March 10

Re: Am I dense, or is this normal...?

Posted 03 April 2010 - 10:31 AM

                 temp = n[i];
                n[i] = n[min_index];
                n[min_index] = temp;



-->i fotgot : it look like this:
                int temp = n[i]; ///here is where i forgot int 
                n[i] = n[min_index];
                n[min_index] = temp;



---So,this is full code base on your code:
#include <iostream>
#include <string>
#include <stdlib.h>

using namespace std;

int main()
{
        int n[100];
        int p = 0;
        int min_index = 0;

        cout << "Enter ten unsorted intergers...\n";
        
        for (int i = 0; i < 10; ++i)
        {
                cout << "[" << i << "] = ";
                cin >> n[i];
        }

        cout << "Unsorted list: ";

        for (int i = 0; i < 10; ++i)
        {
                cout << n[i] << ", ";
        }
        cout << "Sorting...\n" << "Sorted list: ";

        for(int i = 0; i < 9; i++)
        {
                min_index = i;
                for(int j = (i+1); j < 10; j++)
                {
                        if(n[j] < n[min_index])
                        {
                                min_index = j;
                        }
                }
                int temp = n[i];
                n[i] = n[min_index];
                n[min_index] = temp;
        }
        for (int i = 0; i < 10; ++i)
        {
                cout << n[i]<<" ";
        }
        
        cout << endl;
        system("PAUSE");
}



This post has been edited by tauit_dnmd: 03 April 2010 - 10:58 AM

Was This Post Helpful? 0
  • +
  • -

#10 jhicks32917  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 02-April 10

Re: Am I dense, or is this normal...?

Posted 03 April 2010 - 10:43 AM

What is wrong with declaring temp at the beginning of the code? That's what I did, as such...

int main()
{
	int n[100];
	int min_index = 0;
	int temp = 0;



and it works fine, but again, I just don't understand why the first 'for loop' has i<9 and not i<10 as its qualifier (I don't know if that's the correct terminology)
Was This Post Helpful? 0
  • +
  • -

#11 tauit_dnmd  Icon User is offline

  • D.I.C Head

Reputation: 8
  • View blog
  • Posts: 129
  • Joined: 25-March 10

Re: Am I dense, or is this normal...?

Posted 03 April 2010 - 11:11 AM

What is wrong with declaring temp at the beginning of the code?--->it's OK
Was This Post Helpful? 0
  • +
  • -

#12 jhicks32917  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 02-April 10

Re: Am I dense, or is this normal...?

Posted 03 April 2010 - 11:17 PM

Okay, I understand that the code works, I just don't get how. I've sat down and worked through it on paper and I keep getting this...

Say the following are entered into the array:

[0] = 12
[1] = 16
[2] = 13
[3] = 4


I understand that 12 and 13 won't be swapped, and I've worked it out on paper, it makes sense.
Then 16 and 13 are swapped, cool, I get that too. Written on paper still makes sense.
Then 16 and 4 are swapped giving...

[0] = 12
[1] = 13
[2] = 4
[3] = 16

When is 4 compared to what is in [0] and [1]? I don't see where in the code it goes back to check if [2] is less than what is in [1] or [0]

Please, if someone could dumb this down for me... I just can't seem to get it. Again, I know the code works, I just don't know why...

#include <iostream>
#include <stdlib.h>

using namespace std;

int main()
{
	int n[100];
	int min_index = 0;
	int temp = 0;

	cout << "Enter ten unsorted values: ";

	for (int i = 0; i < 10; i++)
	{
		cout << "[" << i << "] = ";
		cin >> n[i];
	}

	cout << "Unsorted values: ";

	for (int i = 0; i < 10; i++)
	{
		cout << "[" << i << "] = " << n[i];
	}

	cout << "\nSorting..." << "\nSorted list: ";
	for (int i = 0; i < 9; i++)
	{
		min_index = i;
		for (int j = (i+1); j < 10; j++)
		{
			
			if (n[j] < n[min_index])
			{
				min_index = j;
			}
		
		}
		temp = n[i];
		n[i] = n[min_index];
		n[min_index] = temp;
	}

	for (int i = 0; i < 10; i++)
	{
		cout << "[" << i << "]" << n[i] << endl;
	}
	cout << endl;
	system("PAUSE");
}


I can't seem to come to this conclusion by myself. The closest I've come is a program that will organize numbers as long as the numbers that need to be swapped are only one space away from where they need to be. For example...

[0] = 12
[1] = 11
[2] = 27
[3] = 9
[4] = 8

Would then organize into:

[0] = 11
[1] = 12
[2] = 9
[3] = 27
[4] = 8

But that is the closest I can get. I can't seem to get each position later in the array to compare to previously sorted data.
I'm sorry if I'm over complicating this, but I just really want to grasp what is happening before I move on.

This post has been edited by jhicks32917: 03 April 2010 - 11:22 PM

Was This Post Helpful? 0
  • +
  • -

#13 tauit_dnmd  Icon User is offline

  • D.I.C Head

Reputation: 8
  • View blog
  • Posts: 129
  • Joined: 25-March 10

Re: Am I dense, or is this normal...?

Posted 03 April 2010 - 11:51 PM

for (int i = 0; i < 9; i++)
	{
		min_index = i;
		for (int j = (i+1); j < 10; j++)
		{
			
			if (n[j] < n[min_index])
			{
				min_index = j;
			}
		
		}
		temp = n[i];
		n[i] = n[min_index];
		n[min_index] = temp;
	}


Example:I have a array a: 0 2 4 5 1 7 2 8 1 5 .that’s contain 10 element of integer.
+Loop with i=0: min_index=i=0;
+loop from j=i+1= 1 to j< 10 to find smallest number in n[i+1] n[9];
+swap n[i] and n[min_index] to put smallest number into array:
because n[0]=0 is smallest.
Result of loop: 0 2 4 5 1 7 2 8 1 5 .
+Loop with i=1: min_index=i=1;
+loop from j=i+1= 2 to j< 10 to find smallest number in n[i+1] n[9];
+swap n[i] and n[min_index] to put smallest number into array.
because n[8]=1 is smallest in n[i+1] n[9];
Result of loop: 0 1 4 5 1 7 2 8 2 5 .
+Loop with i=2: min_index=i=2;
+loop from j=i+1= 3 to j< 10 to find smallest number in n[i+1] n[9];
+swap n[i] and n[min_index] to put smallest number into array.
because n[4]=1 is smallest in n[i+1] n[9];
Result of loop: 0 1 1 5 4 7 2 8 2 5
End program you get: 0 1 1 2 2 4 5 7 8

You can download a program in below to see the way that selection sort work.That's a program made by me:

Attached File(s)


This post has been edited by tauit_dnmd: 03 April 2010 - 11:52 PM

Was This Post Helpful? 0
  • +
  • -

#14 jhicks32917  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 02-April 10

Re: Am I dense, or is this normal...?

Posted 04 April 2010 - 11:12 AM

Oh my gosh, yes, I finally understand. For some reason, in my mind the for loop where 'int j = (i+1)' was being declared only ran once. Only checking the number j to min_index, when it in fact advances through all points in the array.

God, I was making that more complicated than it needed to be.
Thank you for the help!

On a side note, the course I'm taking is from Game Institute, www.gameinstitute.com Anyone have feedback on them? I've only gotten to chapter three of module 1 in c++, but so far it seems solid. I like how they give examples of how each exercise could be applied to the gaming world/ business world.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1