Specializing in programming tutorials that make sense!

You are in Section 7 of 9, Article 7.4 of 7.5

7 .. Sorting Array Data
       7.4 .. Tag Sort

Tag Sort

A selection sort and bubble sort will directly manipulate and change elements in an array. There may also be times when it is necessary to keep actual array data in tact but output the array in a sorted state. To accomplish this, a "tagged" array can be used to store the correct positioning of an array when it is sorted.

When the programmer needs to refer to the sorted array, this "tagged" array can be used.

With a tag sort, the actual array elements to be sorted 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 };

Using the arrays defined above, the following associations can be made:

• position 0 in tag to the value of 3 in arr using arr[tag[0]]
• position 1 in tag to the value of 7 in arr using arr[tag[1]]
• position 2 in tag to the value of 1 in arr using arr[tag[2]]
• position 3 in tag to the value of 12 in arr using arr[tag[3]]
• position 4 in tag to the value of 39 in arr using arr[tag[4]]
• position 5 in tag to the value of 4 in arr using arr[tag[5]]

After the tag sort algorithm (for ascending order) is executed, the above arrays would contain the following elements:

arr[6] = { 3, 7, 1, 12, 39, 4 }; tag[6] = { 2, 0, 5, 1, 3, 4 };

After the tag sort, the following associations can be made:

• position 0 in tag to the value of 1 in arr using arr[tag[0]]
• position 1 in tag to the value of 3 in arr using arr[tag[1]]
• position 2 in tag to the value of 4 in arr using arr[tag[2]]
• position 3 in tag to the value of 7 in arr using arr[tag[3]]
• position 4 in tag to the value of 12 in arr using arr[tag[4]]
• position 5 in tag to the value of 39 in arr using arr[tag[5]]

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

A tag sort essentially makes follows the selection sort algorithm except that values in the tagged array are swapped instead of elements in the original array.

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]); } }

When needing to use the above tagSort function in a program, first call the tagSort function, and then use the tagArr[] for array indexing when displaying the contents of the actual sorted array.

For example, if needing 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 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 the above tag sort used to sort an integer array into ascending order.

arrtagsort.cpp

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

arrtagsortd.cpp

In the next article, we'll cover the quicksort algorithm. The quicksort algorithm is the most efficient array sorting algorithm described in this tutorial.

Read on for more about the quicksort algorithm...

Next: Structures

You are in Section 7 of 9, Article 7.4 of 7.5

[Back to Top]

.: Report Bug : Error Log : About Webmaster :.