Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Array Sorting Algorithms II

form array

  • Please log in to reply
4 replies to this topic

#1 whitey6993

whitey6993

    CC Addict

  • Just Joined
  • PipPipPipPipPip
  • 156 posts

Posted 29 December 2008 - 06: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.

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.

#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.

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.

	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.

	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.

	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.

Attached Files

  • Attached File  main.cpp   1.29KB   330 downloads

  • 2

#2 Guest_Jordan_*

Guest_Jordan_*
  • Guest

Posted 29 December 2008 - 07:59 AM

Another excellent tutorial! +rep
  • 0

#3 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 29 December 2008 - 08:34 AM

Very nice.
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#4 whitey6993

whitey6993

    CC Addict

  • Just Joined
  • PipPipPipPipPip
  • 156 posts

Posted 30 December 2008 - 08:58 AM

Thank you :)
  • 1

#5 Egz0N

Egz0N

    CC Leader

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1155 posts

Posted 30 December 2008 - 10:26 AM

nice tutorial .. +rep :)
  • 0





Also tagged with one or more of these keywords: form, array

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download