Array Sorting Algorithms I

[whitey6993]

This tutorial will show you two algoritms commonly used for sorting arrays or vectors. A knowledge of at least arrays, and possibly vectors is extremley helpful for this tutorial.

In an earlier tutorial I wrote, I explained hot to sort strings using the bubble sort algorithm. I felt that it would be helpful to write a tutorial explaining more about sorting arrays and vectors. So without further ado, lets begin!

I will be using vectors instead of arrays for this tutorial. If you need a tutorial on vectors, please look here We will start with the easiest method of sorting vectors, the bubble sort. For background knowledge, here is the psuedo code of the bubble sort algorithm (taken from Starting Out with C++ 3rd Edition

 
Do
   Set count variable to 0
   For count is set to each subscript in Array from 0 to the next-to-last subscript
      If array[count] is greater than array[count+1]
   swap them
   set swap flag to true
   end if
End for
While any elements have been swapped.

Now that we have the psuedo code for the bubble sort algorithm, the actual function is easy. Open up a new C++ file and type in the following:

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

vector<int> bubbleSort(vector<int>);

int main(void)
{
	return 0;
}

vector<int> bubbleSort(vector<int> sortThis)
{

We are using vectors, so we have to include the vector header file and "using namespace std". We also include iostream for interaction. We will define our prototype to accept a vector of integers as its only argument, and return an ordered vector of integers. After this we define an empty main statment and then begin to define our function. If you want to create a function to order arrays, all you have to do is modify the function to accept the array and the size of the array. It also returns void:

void bubbleSort(int[], int)

Now that we have our function definition started, we can code the bulk of our function. So, following the pseudo code, we type this into the bubbleSort function.

	int count, swap, temp;
	
	do
	{
		swap = 0;
		for (count = 0; count < sortThis.size() - 1; count++)
		{
			if (sortThis.at(count) > sortThis.at(count + 1)
			{
				temp = sortThis.at(count);
				sortThis.at(count) = sortThis.at(count + 1);
				sortThis.at(count + 1) = temp;
				swap = 1;
			}
		}
	}while (swap != 0);
	
	return sortThis;
}

Now I will explain the code. We declare three integers to hold the count, our swap flag, and a temporary storage place for when we swap numbers. Count can be declared inside the for loop, it just depends on your preferance. The swap flag is basically to tell us when to stop swapping, so everything ends up in its right place. We start our do while loop, because we want to at least check to see if anything needs to be swapped and set our swap flag to zero to check if anything has been swaped later. After this we start our for loop and then start iterating through our vector to see if we need to swap anything. The if statment is currently set to order things in ascending order, but by using the less-than operator, we can set it to order numbers in descending order. If the algorithm finds something that needs to be swaped we swap it, and then say that we swaped something by setting our swap flag to 1. At the end of the do-while loop, we check to see if we are done swapping, and then return our sorted vector.

For the sake of completness, here is the code for sorting arrays using the bubble sort algorithm. It has the same explanation and is also based off of the bubble sort psuedo code.

void bubbleSort(int sortThis[], int size)
{
	int count, swap, temp;

	do
	{
		swap = 0;
		for (count = 0; count < size - 1; count++)
		{
			if (sortThis[count] > sortThis[count + 1]
			{
				temp = sortThis[count];
				sortThis[count] = sortThis[count + 1];
				sortThis[count + 1] = temp;
				swap = 1;
			}
		}
	}while (swap != 0);
	
	return;
}

Now all we have to do is test out the new function to make sure it works. Go back up to your main function and enter in this code.

vector<int> oldVector;
vector<int> sortedVector;
int buffer;

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

sortedVector = bubbleSort(oldVector);

cout << "Sorted Vector Contents: " << endl << endl;

for (int i = 0; i < sortedVector.size(); i++)
     cout << sortedVector.at(i) << endl;

system("pause");

This code simply takes integers through a buffer and inserts them into the vector. It then calls the function and stores the sorted vector into a new vector. The contents are output to the screen and the program exits.

The source code used in this project is attatched to the post for convenience. The bubble sort is the simplest method of sorting arrays. For larger arrays and vectors, the selection sort is a better option. This will be the focus of my next tutorial, Array Sorting Algorithms II.

I hope that you have enjoyed the first part of Array Sorting Algorithms. If you wish to contribute to the information presented here or would like to offer corrections, please post a reply.

[Jordan]

Nice tutorial! +rep

[whitey6993]

The second part of this tutorial is now finished. You can find it here

[Wheeli3e]

Hi whitey,

I try to integrate your coding to fix in my project, but it would't work for me. My project is simple, i have this array[myList] 4,3,5,6,2 and i'm suppose to arrange it in order and show the output.

But i'm quite new to java and i couldn't understand some jargon in your code, my template is :

public class Lab2Ex1_JianLe
{

public static void main (String [] args)

{
int [] myList = {5, 4, 2, 3, 8, 7};
System.out.println ("My List before sorting is: ");
for (int i=0; i<myList.length; i++)
System.out.println (myList[i]);

// sort Algorithms

System.out.println ("My List after sorting is: ");
for (int i=0; i<myList.length; i++)
System.out.println (myList[i]);
}
}

Would it be cool if you guide me along, i wouldn't expect you to provide me the answer as i wish to learn too.. Thank you.

[WingedPanther]

1) this is an old thread
2) this is a C++ tutorial, not a Java tutorial