Array Sorting Algorithms II

**whitey6993** · 12-29-2008 08:16 AM

This tutorial is a sequal to a previous tutorial I wrote on Array Sorting Algorithms. It will teach you a different and more advanced way to sort arrays and vectors.

In my previous tutorial, Array Sorting Algorithms I I showed a simple way to sort arrays and vectors using the bubble sort algorithm. This meathod will work most of the time, but lets say that you have an array of more than 5 numbers. Lets say it's a thousand numbers in your vector or array. The bubble sort only moves elements one at a time, so it will take forever for this algorithm to sort your array. Thats where the selection sort algorithm steps in. Selection sort is designed to take elements and put them in their correct place right away. So lets take a look at the psuedo code for this new algorith (taken from Starting Out with C++, 3rd Edition.

Code:

For Start is set to each subscript in Array from 0 through the next-to-last subscript
   Set Index variable to Start
   Set minIndex variable to Start
   Set minValue variable to array[Start]
   For Index is set to each subscript in Array from Start+1 through the next-to-last subscript
      If array[Index] is less than minValue
         Set minValue to array[Index]
         Set minIndex to Index
      End if
      Increment Index
   End For
   Set array[minIndex] to array[Start]
   Set array[Start] to minValue
End For

This algorithm is a bit more complicated than the bubble sort, but still managabel. So open up a new C++ file and type in the following.

Code:

#include <iostream>
#include <vector>
using namespace std;

vector<int> selectionSort(vector<int>);

int main(void)
{
	return 0;
}

vector<int> selectionSort(vector<int> sortThis);
{

As you can see we will be using vectors in this program instead of arrays. If you want to use arrays for this program, do not include the vector header file and make your function prototype and definition accept an array of integers and an integer for the size, and return nothing.

Code:

void selectionSort(int sortThis[], int size)

As it is, we have included iostream for interactivity, vector for using vectors, and we are using the std namespace so that we can use vector and iostream. We have our selection sort function prototype, and an empty main statment that we will fill later on. We also have our function deffinition which takes a vector of integers as an argument and returns the sorted vector of integers. So now, we can begin programing our sorting algorithm based on the psuedo code.

Code:

	int start, minIndex, minValue;
	for (start = 0; start < sortThis.size() - 1; start++)
	{
		minIndex = start;
		minValue = sortThis.at(start);
		for (int index = start + 1; index < sortThis.size(); index++)
		{
			if (sortThis.at(index) < minValue)
			{
				minValue = sortThis.at(index);
				minIndex = index;
			}
		}
		sortThis.at(minIndex) = sortThis.at(start);
		sortThis.at(start) = minValue;
	}

	return sortThis;
}

We start by creating a value to start each search from, as well as a minIndex to know what our lowest value to swap will be, and a minValue to compare with our current numbers. We enter a for loop from zero to the next-to-last element of our vector, just as the psuedo code says. After this we set our minIndex and minValue variables and then start comparing inside another for loop. If we find something that is lower than minValue, we replace minValue with its value and set our minIndex to the place we found that value. Once we exit the for loop We switch the number that needs to be replaced, and reset our minValue variable. So the algorith works by looking for the lowest value, recording its position, and then putting it at the correct place. After we have finished we return our sorted algorithm and thats it. If you want the algorithm to sort arrays, all you have to do is a little tweaking.

Code:

	int start, minIndex, minValue;
	for (start = 0; start < size - 1; start++)
	{
		minIndex = start;
		minValue = sortThis[start];
		for (int index = start + 1; index < size; index++)
		{
			if (sortThis[index] < minValue)
			{		
				minValue = sortThis[index];
				minIndex = index;
			}
		}
		sortThis[minIndex] = sortThis[start];
		sortThis[start] = minValue;
	}
}

This has the same explination as the one above. Now if you want to test the vector sorting algorithm, go back up to your main statment and type in the following.

Code:

	vector<int> origionalVector;
	vector<int> selectionSorted;
	int buffer;

	for (int i = 0; i < 5; i++)
	{
		cout << "Enter element " << i << " of the vector: ";
		cin >> buffer;
		origionalVector.push_back(buffer);
	}

	selectionSorted = selectionSort(origionalVector);

	cout << "The contents of the sorted Vector:" << endl << endl;

	for (int i = 0; i < 5; i++)
		cout << selectionSorted.at(i) << endl;

	system("pause");

Now you should be able to compile the program, input some unsorted numbers, and get the sorted numbers as output. This code was written and compiled using Dev-C++ compiler, so it may need some tweaking to work in other compiles. The source code for this project is also attatched for convenience. If you would like to contribute to the information presented here, or would like to offer corrections, please post a reply.