Programming in C++

Sorting Array Data

Selection Sorts

I will cover two technqiues for sorting an individual array and one technique for merging prevously sorted arrays. The first technique, which is called a selection sort, is a sort used for sorting one 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 positions in place while evaluating the array's values. 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 [0]. During the next pass through, the sort will start hunting from the next unlocked position, find the next smallest value, and lock it into the second location. This process continues during each pass through the array until the whole array is sorted. A selection sort makes use of the swap function we defined earlier. The following is an example of a selection sort. Study the code very carefully and try to think like the 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;
   int pass;
   int 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 using a selection sort to sort an integer array into ascending order.

////////////////////////////////////////////////// Compiler Using Dev-C++ 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[] = { 13, 5, 1, 7, 9, 11, 3, 17, 19, 15 };
     int k;

     cout << "BEFORE SORT: ";
     for (k = 0; k < MAXSIZE; k++)
           cout << numbers[k] << " ";

     selectionSort(numbers, MAXSIZE);

     cout << endl << endl;
     cout << "AFTER SORT: ";
     for (k = 0; k < MAXSIZE; k++)
           cout << numbers[k] << " ";

     cout << endl << endl << endl;

     system("PAUSE");
     return 0;
}// end main()

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[indexOfMin])
                       indexOfMin = j;

           swap(arr[pass], arr[indexOfMin]);
     }
}// end selectionSort()

void swap(int& x, int& y)
{
     int temp;
     temp = x;
     x = y;
     y = temp;
}// end swap()

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\


The above selection sort is a standard technique for sorting arrays. The next technique I will cover, the bubble sort, is another standard sort, but it provides a more efficient way of performing the same sort as a selection sort. Read on for more about bubble sorts...

Bubble Sorts

The bubble sort is another standard technique for sorting data in an array. Instead of making only 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 is 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. As the selection sort locks values into the beginning of the array, the bubble sort locks the positions at the end of the array. Again, we must use a swap function along with our bubble sort function when sorting an array. The following is a bubble sort used to sort an array of integers into ascending order.

void bubbleSort ( int arr [ ], int size )
{
   int last = size - 2;
   int isChanged = 1;

   while ( last >= 0 && isChanged )
   {
           isChanged = 0;
           for ( int 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;
}



The following is a complete program demonstrating using a bubble sort to sort an integer array into descending order.

////////////////////////////////////////////////// Compiler Using Dev-C++ 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 nums[] = { 1, 7, 5, 3, 15, 11, 13, 17, 21, 19 };
     int k;

     cout << "BEFORE SORT: ";
     for (k = 0; k < MAXSIZE; k++)
           cout << nums[k] << " ";

     bubbleSort(nums, MAXSIZE);

     cout << endl << endl;
     cout << "AFTER SORT: ";
     for (k = 0; k < MAXSIZE; k++)
           cout << nums[k] << " ";

     cout << endl << endl << endl;

     system("PAUSE");
     return 0;
}// end main()

void bubbleSort(int arr[], int size)
{
     int last = size - 2;
     int isChanged = 1;

     while (last >= 0 && isChanged)
     {
           isChanged = 0;

           for (int k = 0; k <= last; k++)
                 if (arr[k] < arr[k+1])
                 {
                       swap(arr[k], arr[k+1]);
                       isChanged = 1;
                 }
           last--;
     }
}// end bubbleSort()

void swap(int& x, int& y)
{
     int temp;
     temp = x;
     x = y;
     y = temp;
}// end swap()

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\


We have now covered two techniques for sorting data in an individual array: selection and bubble sorts. Suppose we need to merge two arrays that are sorted in ascending order into a third array. We want to keep the third array sorted into ascending order as we join the two arrays. Do you have something in mind? Read on to find out more about the merge sort and if your idea is similar to it...

The Merge Sort

You can use a merge sort to combine two sorted arrays into a third array. The third array will need to be sorted also, but we can take care of that while we merge 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 found. Depending on which array has ended, the remaining values in the other array will be placed on the end of the third array. The following is a complete program demonstrating how to merge two arrays that are in ascending order:



\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ Compiled Using Dev-C++ Compiler \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

#include <iostream.h>
#include <stdlib.h>

void mergeSort(int arr1[], int arr2[], int arr3[], int size1, int size2, int& size3);
void swap(int& x, int& y);

int main()
{
     int nums1[] = { 3, 7, 9, 15, 19, 23 };
     int nums2[] = { 1, 5, 11, 17, 21, 25, 29, 31 };
     int nums3[15];
     int size1 = 6;
     int size2 = 8;
     int size3;
     int k;

     cout << "ARRAY 1: ";
     for (k = 0; k < size1; k++)
           cout << nums1[k] << " ";

     cout << endl << endl;
     cout << "ARRAY 2: ";
     for (k = 0; k < size2; k++)
           cout << nums2[k] << " ";

     mergeSort(nums1, nums2, nums3, size1, size2, size3);

     cout << endl << endl;
     cout << "MERGED ARRAY 3: ";
     for (k = 0; k < size3; k++)
           cout << nums3[k] << " ";

     cout << endl << endl << endl;

     system("PAUSE");
     return 0;
}// end main()

void mergeSort(int arr1[], int arr2[], int arr3[], int size1, int size2, int& size3)
{
     int pos1 = 0, pos2 = 0, pos3 = 0;

     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()

void swap(int& x, int& y)
{
     int temp;
     temp = x;
     x = y;
     y = temp;
}// end swap()

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\


You now know how to sort individual arrays, and you know how to merge two sorted arrays. However, there may be times when you would like to sort an array without having to directly change the elements in the array. Is it possible? Try to devise a solution to this problem before reading on to see how I came up with a solution. Read on for more...

Tag Sort

I have previously mentioned two standard methods for sorting arrays (selection and bubble sorts), but those two methods directly manipulated and changed the elements in the array. Sometimes, you will want to directly sort the elements in an array, but there may be times when you need 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 you need to refer to the sorted array, you 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, rather 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[] --> 3  7  1  12  39  4
   tag[] --> 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 and completed, the arrays would contain the following elements:

   arr[] --> 3  7  1  12  39  4
   tag[] --> 2  0  5  1  3  4

As you can tell, the original elements in arr[] were not changed at all, but the original elements in tag[] have been changed. 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 that can be used to sort an array of integers into ascending order. Note that the function will also use a "swap" function so the values can be manipulated during the sort process:

// TAG SORT IS 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( )

void swap(int& x, int& y)
{
   int temp;
   temp = x;
   x = y;
   y = temp;
}// end swap( )


When you want to use this tag sort in your program, you obviously need to first call the tagSort() function, and then use the tagArr[] 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 would call our tagSort() function and then use the following code when we want to display the sorted array:

   for (int k = 0; k < 10; k++)
       cout << arrNums[ tagArr[k] ] << endl;



The following is a complete program demonstrating the use of a tag sort to sort an integer array into ascending order.

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ Compiled Using Dev-C++ Compiler \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

#include
#include
#include

void TagSort(int tagArr[], int dataArr[], int size);
void swap(int& x, int& y);

int main()
{
     const int MAXSIZE = 5;
     int intArr[MAXSIZE] = { 32, 16, 8, 24, 40 };
     int tagArr[MAXSIZE];

     TagSort(tagArr, intArr, MAXSIZE);

     cout << "ORIGINAL: ";
     for (int k = 0; k < MAXSIZE; k++)
           cout << intArr[k] << " ";

     cout << endl << endl;
     cout << "TAGGED: ";
     for(int j = 0; j < MAXSIZE; j++)
           cout << tagArr[j] << " ";

     cout << endl << endl;
     cout << "SORTED: ";
     for (int i = 0; i < MAXSIZE; i++)
           cout << intArr[tagArr[i]] << " ";

     cout << endl << endl << endl;

     system("PAUSE");
     return 0;
}// end main()

void TagSort(int tagArr[], int dataArr[], 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()

void swap(int& x, int& y)
{
     int temp;
     temp = x;
     x = y;
     y = temp;
}// end swap()

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


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 a better topic: structures. Structures in C++ are very similar to what other programming languages may call records. Read on for more about structures...

You might also like...

Comments

Contribute

Why not write for us? Or you could submit an event or a user group in your area. Alternatively just tell us what you think!

Our tools

We've got automatic conversion tools to convert C# to VB.NET, VB.NET to C#. Also you can compress javascript and compress css and generate sql connection strings.

“Before software should be reusable, it should be usable.” - Ralph Johnson