Sort by choice

[BananaCode]

Hello

So to strengthen my learning in c++, I'm trying my hands on a few algorithms I found in a book to sort arrays. However, that's in pascal and I don't quite understand it, as they don't show the entire code.

This is what I've come up with, it works with some number, but not with all. Can somebody help me and say what is the problem with it?

Note: I don't want to use any other sorting algorithm, I would like to implement this specific type.

The principle of sort by choice is that, you select the smallest element in an array, put it in position 0, go on to the next smallest element, put it in position 1, etc.

#include <iostream>

using namespace std;

void print (int a[], int size);

int main()
{	
	int size, temp, min=0, x;
	int *arr;
	bool change=false;
	cin >> size;
	arr = new int [size];
	for (int i=0;i<size;i++)
	{
		cin >> arr[i];
	}
	for (int y=0;y<size;y++)
	{
		change=false;
		x = y;
		for (;x<size;x++)
		{
			if (arr[x] < arr[min])
			{
				min = x;
				change = true;
			}
		}
		
		if (change)
		{
			temp = arr[y];
			arr[y] = arr[min];
			arr[min] = temp;
		}
	}
	print(arr, size);
	

	return 0;
}

void print (int a[], int size)
{
	for (int l=0;l<size;l++)
	{
		cout << a[l] << " ";
	}
	cout << endl;
	system("pause");

}

[kbw]

It sort of looks like a bubble sort that's lost its way. You shouldn't really care about what the minimum value is.
http://en.wikipedia.org/wiki/Bubble_sort

[BananaCode]

I was interested in coding that specific sorting algorithm, which requires me to select the minimum value.

But thank you for the link

[kbw]

I see. Is the algorithm described somewhere? If I can see a description I can probably help verify your code.

BTW, you'll need to change line 39 to:

delete [] arr;

[BananaCode]

I'll try to translate:

You select position j1, which is the position of the smallest value a[1],...,a[n], an swap a[j1] with a[1]. Then we select the next smallest value j2 from a[2],...,a[n], and swap a[j2] with a[2] and so forth until all elements are in the correct position.

If you can read german, here is the book I found on the internet. The chapter is called "Sortieren durch Auswahl":

http://ethz.codechaos.ch/FS10/Datenstrukturen%20und%20Algorithmen/book/2-sortieren.pdf

[D80DSL3A]

I think the algorithm you're looking for is called the selection sort.
http://en.wikipedia.org/wiki/Selection_sort

[ne555]

The problem is that you don't reset min.
Suppose that you found the min value in the place that should belong (so you don't need to swap).

Edit: As a suggestion, create a function min_element that returns the index of the min value in a range.

[BananaCode]

Thank you fun2code, I'll check that link

ne555, I don't quite understand what you mean. Where am I resetting min?

[BananaCode]

with help of wikipedia:

#include <iostream>

using namespace std;

void print (int a[], int size);

int main()
{	
	int size, temp, iPos, iMin, i;
	int *arr;
	cin >> size;
	arr = new int [size];
	for (int i=0;i<size;i++)
	{
		cin >> arr[i];
	}
	for (iPos=0; iPos<size;iPos++)
	{
		iMin=iPos;
		for (i =iPos+1; i<size;i++)
		{
			if (arr[i] < arr[iMin])
			{
				iMin = i;
			}
		}

		if ( iMin != iPos )
		{
			temp = arr[iPos];
			arr[iPos] = arr[iMin];
			arr[iMin] = temp;
		}
	}
	print(arr, size);
	

	return 0;
}

void print (int a[], int size)
{
	for (int l=0;l<size;l++)
	{
		cout << a[l] << " ";
	}
	cout << endl;
	system("pause");

}

At least I had a similar idea...

[ne555]

You are not resetting it, that is the problem.
Suppose that this is the input array: [ 7 2 5 4 3 1 5 ]
First iteration:
min = 5
array = [1 2 5 4 3 7 5]
Second iteration:
min = 1
array = [1 2 5 4 3 7 5]
Third:
min = 1 // <-----
array = [1 2 5 4 3 7 5]

[BananaCode]

Ah yes, yes. Now I understand. I had implemented a resetting min variable, but it went out funny, so I took it out.

But with your description ne555, I can actually understand it better. Thank you.

Problem is solved.

[D80DSL3A]

Glad you solved the problem. You have a memory leak though! This is important so I want to point it out even though you have closed the thread.
You need to delete the dynamically allocated memory. kbw pointed this out but I guess you didn't catch it.
Add after line 35:
delete [] arr;

[BananaCode]

Ah yes, I oversaw his post.

Memory leak means that this memory goes somehow lost during program execution once the array is not used anymore?