Author: Mike Ware
Website: [warebiz] :: "The Programmer's Domain" - http://warebiz.tripod.com
Email: warebiz@yahoo.com
Copyright © 2003 Michael Shawn Ware, All Rights Reserved.
You are here --> [Section 7 :: Sorting Array Data]
"Jump To Articles"
--> Selection Sort
--> Bubble Sort
--> Merge Sort
--> Tag Sort
Selection Sort
In this tutorial, I will cover three techniques for sorting an individual array and one technique for merging previously sorted arrays. The first technique, which is called a selection sort, is a sort used for sorting an individual array. The sort itself, depending on if the array is to be sorted into ascending or descending order, will evaluate each element in the array and will lock a position in place during each loop sequence. For example, if an array is to be sorted into ascending order, during the first pass through the array, the selection sort will hunt for the element that is the smallest and will lock that element in the first location of the array ( array[0] ). During the next cycle, the sort will start hunting from the next unlocked position, find the next smallest value, and lock it into the second location. Because array values will be moved from an initial position to a new position, a "swap" function will be implemented and used to handle this sorting operation. The following is an example of a selection sort. Study the code very carefully and mimic the mind of a compiler during execution of the program.
// selection sort used to sort an array of integers into ascending order
void selectionSort ( int arr[], int size )
{
int indexOfMin, pass, j;
for ( pass = 0; pass < size - 1; pass++ )
{
indexOfMin = pass;
for ( j = pass + 1; j < size; j++ )
if ( arr[j] < arr[pass] )
indexOfMin = j;
swap ( &arr[pass], &arr[indexOfMin] );
}
}
// swap function for integers
void swap ( int* x, int* y )
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
The following is a complete program demonstrating the use of a selection sort function used to sort an integer array into ascending order.
/////////////////////////////////// Compiled Using Dev C/C++ V.4 Compiler /////////////////////////////
#include <iostream.h>
#include <stdlib.h>
const int MAXSIZE = 10;
void selectionSort ( int arr[], int size );
void swap ( int* x, int* y );
int main()
{
int numbers[MAXSIZE] = { 13, 5, 1, 7, 9, 11, 3, 17, 19, 15 };
int index;
cout << "BEFORE SORT: ";
for (index = 0; index < MAXSIZE; index++)
cout << numbers[index] << " ";
selectionSort(numbers, MAXSIZE);
cout << endl << endl << "AFTER SORT: ";
for (index = 0; index < MAXSIZE; index++)
cout << numbers[index] << " ";
cout << endl << endl;
system("PAUSE");
return EXIT_SUCCESS;
}
void selectionSort ( int arr[], int size )
{
int indexOfMin, pass, j, index;
for ( pass = 0; pass < size - 1; pass++ )
{
indexOfMin = pass;
for ( j = pass + 1; j < size; j++ )
if ( arr[j] < arr[indexOfMin] )
indexOfMin = j;
swap ( &arr[pass], &arr[indexOfMin] );
}
}
void swap ( int* x, int* y )
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
/////////////////////////////////// Compiled Using Dev C/C++ V.4 Compiler /////////////////////////////
The above selection sort is a standard technique for sorting arrays. The next technique I will cover, the bubble sort, is another standard sort, and it actually provides a more efficient method of performing the same sorting technique as a selection sort. Read on for more about bubble sorts...
Bubble Sort
The bubble sort is another standard technique for sorting data in an array. Instead of making one "swap" after a pass through the array like the selection sort, the bubble sort makes several swaps of values depending on whether we want to sort the data into ascending or descending order. Let's describe what happens if we want to use the bubble sort for sorting an array of integers into ascending order. The sort begins by evaluating the first two elements in the array. If the first element is greater than the second element, then a "swap" will be made. If not, no "swap" is made. The second element and the third element are evaluated next. If the second element is greater than the third, then a "swap" is made. If not, no "swap" is made. As you can see, if the first element is the largest integer in the array, it will continue to be "swapped" through the array until it reaches the last position in the array. Whereas the selection sort locks values into the beginning of the array, the bubble sort locks values into positions toward the end of the array. Again, we must use a "swap" function along with our bubble sort function when sorting the array. The following is a bubble sort function used to sort an array of integers into ascending order.
// bubble sort function defined for ascending order assortment
void bubbleSort ( int arr [ ], int size )
{
int last = size - 2;
int isChanged = 1, k;
while ( last >= 0 && isChanged )
{
isChanged = 0;
for ( k = 0; k <= last; k++ )
if ( arr[k] > arr[k+1] )
{
swap ( &arr[k], &arr[k+1] );
isChanged = 1;
}
last--;
}
}
// swap function defined for integers
void swap ( int* x, int* y )
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
The following is a complete program demonstrating the use of a bubble sort function used to sort an integer array into descending order.
/////////////////////////////////// Compiled Using Dev C/C++ V.4 Compiler //////////////////////////////
#include <iostream.h>
#include <stdlib.h>
const int MAXSIZE = 10;
void bubbleSort ( int arr [ ], int size );
void swap ( int* x, int* y );
int main()
{
int numbers[MAXSIZE] = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };
int index;
cout << "BEFORE SORT: ";
for (index = 0; index < MAXSIZE; index++)
cout << numbers[index] << " ";
bubbleSort(numbers, MAXSIZE);
cout << endl << endl << "AFTER SORT: ";
for (index = 0; index < MAXSIZE; index++)
cout << numbers[index] << " ";
cout << endl << endl;
system("PAUSE");
return EXIT_SUCCESS;
}
void bubbleSort ( int arr [ ], int size )
{
int last = size - 2;
int isChanged = 1, k;
while ( last >= 0 && isChanged )
{
isChanged = 0;
for ( k = 0; k <= last; k++ )
if ( arr[k] < arr[k+1] )
{
swap ( &arr[k], &arr[k+1] );
isChanged = 1;
}
last--;
}
}
void swap ( int* x, int* y )
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
/////////////////////////////////// Compiled Using Dev C/C++ V.4 Compiler /////////////////////////////
We have now covered two standard techniques for sorting data in an individual array: a selection and bubble sort. Suppose we need to merge two arrays that have been previously sorted into ascending order. We want to keep the third array sorted into ascending order as we join the two arrays into a third Do you have something in mind? Read on to find out more about the merge sort and if your idea is similar to it...
Merge Sort
A programmer can use a merge sort to combine two previously sorted arrays into a third array. The third array will need to be sorted also, but he can take care of this while he merges the two arrays into one. A merge sort requires two arrays that have been previously sorted into ascending or descending order. When the sort first begins (for ascending order), the first elements of each of the arrays are evaluated to see which array contains the smaller value. Once the smaller value is found, it will be placed as the first element in the third array. The sort continues to evaluate the elements of both arrays until the end of one of the arrays is reached. Depending on which array has ended, the remaining values in the other array will be attached to the end of the third array. The following is a complete program demonstrating how to merge two arrays previously sorted into ascending order:
/////////////////////////////////// Compiled Using Dev C/C++ V.4 Compiler /////////////////////////////
#include <iostream.h>
#include <stdlib.h>
const int FIRSTPOS = 0;
const int ARRSIZE1 = 6;
const int ARRSIZE2 = 8;
void mergeSort(int arr1[], int arr2[], int arr3[], int size1, int size2, int* size3);
int main()
{
int ARRSIZE3 = ARRSIZE1 + ARRSIZE2 + 1;
int nums1[ARRSIZE1] = { 3, 7, 9, 15, 19, 23 };
int nums2[ARRSIZE2] = { 1, 5, 11, 17, 21, 25, 29, 31 };
int nums3[ARRSIZE3];
int k;
cout << "ARRAY 1: ";
for (k = FIRSTPOS; k < ARRSIZE1; k++)
cout << nums1[k] << " ";
cout << endl << endl << "ARRAY 2: ";
for (k = FIRSTPOS; k < ARRSIZE2; k++)
cout << nums2[k] << " ";
mergeSort(nums1, nums2, nums3, ARRSIZE1, ARRSIZE2, &ARRSIZE3);
cout << endl << endl << "MERGED ARRAY 3: ";
for (k = FIRSTPOS; k < ARRSIZE3; k++)
cout << nums3[k] << " ";
cout << endl << endl;
system("PAUSE");
return EXIT_SUCCESS;
}
void mergeSort(int arr1[], int arr2[], int arr3[], int size1, int size2, int* size3)
{
int pos1 = FIRSTPOS, pos2 = FIRSTPOS, pos3 = FIRSTPOS;
while (pos1 < size1 && pos2 < size2)
if (arr1[pos1] < arr2[pos2])
arr3[pos3++] = arr1[pos1++];
else
arr3[pos3++] = arr2[pos2++];
if (pos1 < size1)
while (pos1 < size1)
arr3[pos3++] = arr1[pos1++];
else
while (pos2 < size2)
arr3[pos3++] = arr2[pos2++];
*size3 = size1 + size2;
}// end mergeSort()
/////////////////////////////////// Compiled Using Dev C/C++ V.4 Compiler /////////////////////////////
You now know how to sort individual arrays, and you know how to merge two previously sorted arrays into a third sorted array. There may be times when you need to sort an array without having to directly manipulate the elements in the array. Is this possible? Try to devise a solution to this problem before reading on to see the standard technique for solving this type of problem. Read on for more...
Tag Sort
I have previously mentioned two standard methods for sorting individual arrays (a selection and bubble sort), but those two methods directly manipulated and changed the elements in the array. Sometimes, a programmer will want to directly sort the elements in an array, but there may be times when he needs to keep the actual array in tact and use a "tag" array to store the correct positioning of the array when it is sorted. When the programmer needs to refer to the sorted array, he can call upon this "tagged" array that holds the correct ordering of when the array is sorted. In other words, the actual elements are not being changed during the sort process. The positions in the tag array are being changed so they will hold the correct ordering of the sorted elements of the array. For example, consider the following integer array and integer tag array:
arr[6] = { 3, 7, 1, 12, 39, 4 };
tag[6] = { 0, 1, 2, 3, 4, 5 };
This associates the position of 0 in tag[] to the value of 3 in arr[], the position of 1 in tag[] to the value of 7 in arr[], the position of 2 in tag[] to the value of 1 in arr[], the position of 3 in tag[] to the value of 12 in arr[], the position of 4 in tag[] to the value of 39 in arr[], and the position of 5 in tag[] to the value of 4 in arr[]. After the tag sort (for ascending order) is executed, the arrays would contain the following elements:
arr[6] = { 3, 7, 1, 12, 39, 4 };
tag[6] = { 2, 0, 5, 1, 3, 4 };
As shown, the original elements in arr[] were not changed, but the original elements in tag[] were manipulated. The tag[] array now holds the correct ordering of the positions in arr[] so the array can be sorted into ascending order when the tag[] array is called upon.
The following is a tag sort function used to sort an array of integers into ascending order. Note that the function will also use a "swap" function so values can be manipulated during the sort process:
// tag sort based on selection sort
void tagSort(int dataArr[], int tagArr[], int size)
{
int k, indexOfMin, pass;
for (k = 0; k < size; k++)
tagArr[k] = k;
for (pass = 0; pass < size - 1; pass++)
{
indexOfMin = pass;
for (k = pass + 1; k < size; k++)
if (dataArr[ tagArr[k] ] < dataArr[ tagArr[indexOfMin] ])
indexOfMin = k;
if (indexOfMin != pass)
swap ( &tagArr[pass], &tagArr[indexOfMin] );
}
}// end tagSort( )
// swap function defined for integers
void swap ( int* x, int* y )
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
When you need to use this tag sort in a program, you obviously need to first call the tagSort() function, and then use the tagArr[] for array subscripting when you are displaying the contents of the actual sorted array. For example, if we wanted to display an integer array called arrNums, which has 10 elements, sorted into ascending order, we could call our tagSort() function and then use the following code when we want to display the sorted array:
int k;
for (k = 0; k < 10; k++)
cout << arrNums[ tagArr[k] ] << " ";
The following is a complete program demonstrating the use of a tag sort used to sort an integer array into ascending order.
/////////////////////////////////// Compiled Using Dev C/C++ V.4 Compiler /////////////////////////////
#include <iostream.h>
#include <stdlib.h>
const int MAXSIZE = 5;
const int FIRSTPOS = 0;
void tagSort(int dataArr[], int tagArr[], int size);
void swap ( int* x, int* y );
int main()
{
int intArr[MAXSIZE] = { 32, 16, 8, 24, 40 };
int tagArr[MAXSIZE];
int k, j, i;
tagSort(intArr, tagArr, MAXSIZE);
cout << "ORIGINAL: ";
for (k = FIRSTPOS; k < MAXSIZE; k++)
cout << intArr[k] << " ";
cout << endl << endl << "TAGGED: ";
for(j = FIRSTPOS; j < MAXSIZE; j++)
cout << tagArr[j] << " ";
cout << endl << endl << "SORTED: ";
for (i = FIRSTPOS; i < MAXSIZE; i++)
cout << intArr[tagArr[i]] << " ";
cout << endl << endl;
system("PAUSE");
return EXIT_SUCCESS;
}
void tagSort(int dataArr[], int tagArr[], int size)
{
int k, indexOfMin, pass;
for (k = FIRSTPOS; k < size; k++)
tagArr[k] = k;
for (pass = FIRSTPOS; pass < size - 1; pass++)
{
indexOfMin = pass;
for (k = pass + 1; k < size; k++)
if (dataArr[ tagArr[k] ] < dataArr[ tagArr[indexOfMin] ])
indexOfMin = k;
if (indexOfMin != pass)
swap ( &tagArr[pass], &tagArr[indexOfMin] );
}
}// end tagSort( )
void swap ( int* x, int* y )
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
/////////////////////////////////// Compiled Using Dev C/C++ V.4 Compiler /////////////////////////////
I have now covered four methods for sorting arrays: a selection sort, bubble sort, merge sort, and tag sort. We can now move on to another topic: structures. Structures in C++ are very similar to what other programming languages call records. Read on for more about structures...
Move on to next set of topics: [Section 8] - User-Defined Types, Header Files, and Graphics Intro
Back to Top