# Tag Sort

Tag sort is a sorting algorithm that is used to sort elements based on their associated tags or labels. It is particularly useful when the elements to be sorted have multiple tags or labels, and the goal is to group similar elements together based on their common tags.

The tag sort algorithm works by first creating a dictionary of tags and their associated elements. Then, the algorithm iterates over each tag and retrieves the corresponding elements from the dictionary. The retrieved elements are then appended to a new list in the order that they were found.

The algorithm continues this process for each tag, resulting in a sorted list of elements grouped by their tags. The time complexity of tag sort is O(n), where n is the number of elements to be sorted, but the space complexity can be higher than other sorting algorithms due to the need for a dictionary to store tags and their associated elements.

Tag sort can be useful in applications such as content recommendation systems, where items are tagged with multiple labels, and the goal is to recommend items that have similar tags.

The overall space complexity of tag sort is O(n + k), where n is the number of elements to be sorted and k is the number of unique tags.

Here given code implementation process.

``````// C program
// Perform Tag Sort
#include <stdio.h>

//This function are sorting tag element based on given collection element
//This is not modify the element of actual collection
void tag_sort(int collection[], int tag[], int size)
{
//Loop controlling variables
int i = 0;
int j = 0;
//used to swap tag value
int temp = 0;
for (i = 0; i < size; i++)
{
for (j = i + 1; j < size; j++)
{
if (collection[tag[i]] > collection[tag[j]])
{
//When need to swap the value of tag element
temp = tag[i];
tag[i] = tag[j];
tag[j] = temp;
}
}
}
}
//print the collection elements using tag key
void display(int collection[], int tag[], int size)
{
int i = 0;
for (i = 0; i < size; i++)
{
printf("  %d", collection[tag[i]]);
}
}
int main()
{
int collection[] = {
3,
7,
19,
2,
4,
18,
1,
2,
0,
-2,
5
};
//Get the size of collection
int size = sizeof(collection) / sizeof(collection[0]);
//Tag which is storing the location of sorted elements
int tag[size];
int i = 0;
//Set index of tag element
for (i = 0; i < size; ++i)
{
tag[i] = i;
}
printf(" Before Sort");
display(collection, tag, size);
tag_sort(collection, tag, size);
printf("\n Tag Sort");
display(collection, tag, size);
return (0);
}``````

#### Output

`````` Before Sort  3  7  19  2  4  18  1  2  0  -2  5
Tag Sort  -2  0  1  2  2  3  4  5  7  18  19``````
``````// Java program
// Perform Tag Sort
class MySort
{
//This function are sorting tag element based on given collection element
//This is not modify the element of actual collection
public void tag_sort(int[] collection, int[] tag, int size)
{
//Loop controlling variables
int i = 0;
int j = 0;
//used to swap tag value
int temp = 0;
for (i = 0; i < size; i++)
{
for (j = i + 1; j < size; j++)
{
if (collection[tag[i]] > collection[tag[j]])
{
//When need to swap the value of tag element
temp = tag[i];
tag[i] = tag[j];
tag[j] = temp;
}
}
}
}
//print the collection elements using tag key
public void display(int[] collection, int[] tag, int size)
{
int i = 0;
for (i = 0; i < size; i++)
{
System.out.print("  " + collection[tag[i]]);
}
}
public static void main(String[] args)
{
MySort obj = new MySort();
//Define the collection of integer elements
int[] collection = {
3,
7,
19,
2,
4,
18,
1,
2,
0,
-2,
5
};
//Get the size of collection
int size = collection.length;
//Tag which is storing the location of sorted elements
int[] tag = new int[size];
int i = 0;
//Set index of tag element
for (i = 0; i < size; ++i)
{
tag[i] = i;
}
System.out.print(" Before Sort");
obj.display(collection, tag, size);
obj.tag_sort(collection, tag, size);
System.out.print("\n Tag Sort");
obj.display(collection, tag, size);
}
}``````

#### Output

`````` Before Sort  3  7  19  2  4  18  1  2  0  -2  5
Tag Sort  -2  0  1  2  2  3  4  5  7  18  19``````
``````//Include header file
#include <iostream>

using namespace std;
// C++ program
// Perform Tag Sort
class MySort
{
public:
//This function are sorting tag element based on given collection element
//This is not modify the element of actual collection
void tag_sort(int collection[], int tag[], int size)
{
//Loop controlling variables
int i = 0;
int j = 0;
//used to swap tag value
int temp = 0;
for (i = 0; i < size; i++)
{
for (j = i + 1; j < size; j++)
{
if (collection[tag[i]] > collection[tag[j]])
{
//When need to swap the value of tag element
temp = tag[i];
tag[i] = tag[j];
tag[j] = temp;
}
}
}
}
//print the collection elements using tag key
void display(int collection[], int tag[], int size)
{
int i = 0;
for (i = 0; i < size; i++)
{
cout << "  " << collection[tag[i]];
}
}
};
int main()
{
MySort obj = MySort();
int collection[] = {
3 , 7 , 19 , 2 , 4 , 18 , 1 , 2 , 0 , -2 , 5
};
//Get the size of collection
int size = sizeof(collection) / sizeof(collection[0]);
int tag[size];
int i = 0;
//Set index of tag element
for (i = 0; i < size; ++i)
{
tag[i] = i;
}
cout << " Before Sort";
obj.display(collection, tag, size);
obj.tag_sort(collection, tag, size);
cout << "\n Tag Sort";
obj.display(collection, tag, size);
return 0;
}``````

#### Output

`````` Before Sort  3  7  19  2  4  18  1  2  0  -2  5
Tag Sort  -2  0  1  2  2  3  4  5  7  18  19``````
``````//Include namespace system
using System;
// C# program
// Perform Tag Sort
class MySort
{
//This function are sorting tag element based on given collection element
//This is not modify the element of actual collection
public void tag_sort(int[] collection, int[] tag, int size)
{
//Loop controlling variables
int i = 0;
int j = 0;
//used to swap tag value
int temp = 0;
for (i = 0; i < size; i++)
{
for (j = i + 1; j < size; j++)
{
if (collection[tag[i]] > collection[tag[j]])
{
//When need to swap the value of tag element
temp = tag[i];
tag[i] = tag[j];
tag[j] = temp;
}
}
}
}
//print the collection elements using tag key
public void display(int[] collection, int[] tag, int size)
{
int i = 0;
for (i = 0; i < size; i++)
{
Console.Write("  " + collection[tag[i]]);
}
}
public static void Main(String[] args)
{
MySort obj = new MySort();
int[] collection = {
3 , 7 , 19 , 2 , 4 , 18 , 1 , 2 , 0 , -2 , 5
};
//Get the size of collection
int size = collection.Length;
int[] tag = new int[size];
int i = 0;
//Set index of tag element
for (i = 0; i < size; ++i)
{
tag[i] = i;
}
Console.Write(" Before Sort");
obj.display(collection, tag, size);
obj.tag_sort(collection, tag, size);
Console.Write("\n Tag Sort");
obj.display(collection, tag, size);
}
}``````

#### Output

`````` Before Sort  3  7  19  2  4  18  1  2  0  -2  5
Tag Sort  -2  0  1  2  2  3  4  5  7  18  19``````
``````<?php
// Php program
// Perform Tag Sort
class MySort
{
//This function are sorting tag element based on given collection element
//This is not modify the element of actual collection
public	function tag_sort( \$collection, & \$tag, \$size)
{
//Loop controlling variables
\$i = 0;
\$j = 0;
//used to swap tag value
\$temp = 0;
for (\$i = 0; \$i < \$size; \$i++)
{
for (\$j = \$i + 1; \$j < \$size; \$j++)
{
if (\$collection[\$tag[\$i]] > \$collection[\$tag[\$j]])
{
//When need to swap the value of tag element
\$temp = \$tag[\$i];
\$tag[\$i] = \$tag[\$j];
\$tag[\$j] = \$temp;
}
}
}
}
//print the collection elements using tag key
public	function display( \$collection, \$tag, \$size)
{
\$i = 0;
for (\$i = 0; \$i < \$size; \$i++)
{
echo "  ". \$collection[\$tag[\$i]];
}
}
}

function main()
{
\$obj = new MySort();
//Define the collection of integer elements
\$collection = array(3, 7, 19, 2, 4, 18, 1, 2, 0, -2, 5);
//Get the size of collection
\$size = count(\$collection);
//Tag which is storing the location of sorted elements
\$tag = array_fill(0, \$size, 0);
\$i = 0;
//Set index of tag element
for (\$i = 0; \$i < \$size; ++\$i)
{
\$tag[\$i] = \$i;
}
echo " Before Sort";
\$obj->display(\$collection, \$tag, \$size);
\$obj->tag_sort(\$collection, \$tag, \$size);
echo "\n Tag Sort";
\$obj->display(\$collection, \$tag, \$size);
}
main();``````

#### Output

`````` Before Sort  3  7  19  2  4  18  1  2  0  -2  5
Tag Sort  -2  0  1  2  2  3  4  5  7  18  19``````
``````// Node Js program
// Perform Tag Sort
class MySort
{
//This function are sorting tag element based on given collection element
//This is not modify the element of actual collection
tag_sort(collection, tag, size)
{
//Loop controlling variables
var i = 0;
var j = 0;
//used to swap tag value
var temp = 0;
for (i = 0; i < size; i++)
{
for (j = i + 1; j < size; j++)
{
if (collection[tag[i]] > collection[tag[j]])
{
//When need to swap the value of tag element
temp = tag[i];
tag[i] = tag[j];
tag[j] = temp;
}
}
}
}
//print the collection elements using tag key
display(collection, tag, size)
{
var i = 0;
for (i = 0; i < size; i++)
{
process.stdout.write("  " + collection[tag[i]]);
}
}
}

function main()
{
var obj = new MySort();
//Define the collection of integer elements
var collection = [3, 7, 19, 2, 4, 18, 1, 2, 0, -2, 5];
//Get the size of collection
var size = collection.length;
//Tag which is storing the location of sorted elements
var tag = Array(size).fill(0);
var i = 0;
//Set index of tag element
for (i = 0; i < size; ++i)
{
tag[i] = i;
}
process.stdout.write(" Before Sort");
obj.display(collection, tag, size);
obj.tag_sort(collection, tag, size);
process.stdout.write("\n Tag Sort");
obj.display(collection, tag, size);
}
main();``````

#### Output

`````` Before Sort  3  7  19  2  4  18  1  2  0  -2  5
Tag Sort  -2  0  1  2  2  3  4  5  7  18  19``````
``````#  Python 3 program
#  Perform Tag Sort
class MySort :
# This function are sorting tag element based on given collection element
# This is not modify the element of actual collection
def tag_sort(self, collection, tag, size) :
# Loop controlling variables
i = 0
j = 0
# used to swap tag value
temp = 0
while (i < size) :
j = i + 1
while (j < size) :
if (collection[tag[i]] > collection[tag[j]]) :
# When need to swap the value of tag element
temp = tag[i]
tag[i] = tag[j]
tag[j] = temp

j += 1

i += 1

# print the collection elements using tag key
def display(self, collection, tag, size) :
i = 0
while (i < size) :
print("  ", collection[tag[i]], end = "")
i += 1

def main() :
obj = MySort()
# Define the collection of integer elements
collection = [3, 7, 19, 2, 4, 18, 1, 2, 0, -2, 5]
# Get the size of collection
size = len(collection)
# Tag which is storing the location of sorted elements
tag = [0] * size
i = 0
# Set index of tag element
while (i < size) :
tag[i] = i
i += 1

print(" Before Sort", end = "")
obj.display(collection, tag, size)
obj.tag_sort(collection, tag, size)
print("\n Tag Sort", end = "")
obj.display(collection, tag, size)

if __name__ == "__main__": main()``````

#### Output

`````` Before Sort   3   7   19   2   4   18   1   2   0   -2   5
Tag Sort   -2   0   1   2   2   3   4   5   7   18   19``````
``````#  Ruby program
#  Perform Tag Sort
class MySort

# This function are sorting tag element based on given collection element
# This is not modify the element of actual collection
def tag_sort(collection, tag, size)

# Loop controlling variables
i = 0
j = 0
# used to swap tag value
temp = 0
while (i < size)

j = i + 1
while (j < size)

if (collection[tag[i]] > collection[tag[j]])

# When need to swap the value of tag element
temp = tag[i]
tag[i] = tag[j]
tag[j] = temp
end
j += 1
end
i += 1
end
end
# print the collection elements using tag key
def display(collection, tag, size)

i = 0
while (i < size)

print("  ", collection[tag[i]])
i += 1
end
end
end
def main()

obj = MySort.new()
# Define the collection of integer elements
collection = [3, 7, 19, 2, 4, 18, 1, 2, 0, -2, 5]
# Get the size of collection
size = collection.length
# Tag which is storing the location of sorted elements
tag = Array.new(size) {0}
i = 0
# Set index of tag element
while (i < size)

tag[i] = i
i += 1
end
print(" Before Sort")
obj.display(collection, tag, size)
obj.tag_sort(collection, tag, size)
print("\n Tag Sort")
obj.display(collection, tag, size)
end
main()``````

#### Output

`````` Before Sort  3  7  19  2  4  18  1  2  0  -2  5
Tag Sort  -2  0  1  2  2  3  4  5  7  18  19``````
``````// Scala program
// Perform Tag Sort
class MySort
{
//This function are sorting tag element based on given collection element
//This is not modify the element of actual collection
def tag_sort(collection: Array[Int], tag: Array[Int], size: Int): Unit = {
//Loop controlling variables
var i: Int = 0;
var j: Int = 0;
//used to swap tag value
var temp: Int = 0;
while (i < size)
{
j = i + 1;
while (j < size)
{
if (collection(tag(i)) > collection(tag(j)))
{
//When need to swap the value of tag element
temp = tag(i);
tag(i) = tag(j);
tag(j) = temp;
}
j += 1;
}
i += 1;
}
}
//print the collection elements using tag key
def display(collection: Array[Int], tag: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print("  " + collection(tag(i)));
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MySort = new MySort();
//Define the collection of integer elements
var collection: Array[Int] = Array(3, 7, 19, 2, 4, 18, 1, 2, 0, -2, 5);
//Get the size of collection
var size: Int = collection.length;
//Tag which is storing the location of sorted elements
var tag: Array[Int] = Array.fill[Int](size)(0);
var i: Int = 0;
//Set index of tag element
while (i < size)
{
tag(i) = i;
i += 1;
}
print(" Before Sort");
obj.display(collection, tag, size);
obj.tag_sort(collection, tag, size);
print("\n Tag Sort");
obj.display(collection, tag, size);
}
}``````

#### Output

`````` Before Sort  3  7  19  2  4  18  1  2  0  -2  5
Tag Sort  -2  0  1  2  2  3  4  5  7  18  19``````
``````// Swift program
// Perform Tag Sort
class MySort
{
//This function are sorting tag element based on given collection element
//This is not modify the element of actual collection
func tag_sort(_ collection: [Int], _ tag: inout[Int], _ size: Int)
{
//Loop controlling variables
var i: Int = 0;
var j: Int = 0;
//used to swap tag value
var temp: Int = 0;
while (i < size)
{
j = i + 1;
while (j < size)
{
if (collection[tag[i]] > collection[tag[j]])
{
//When need to swap the value of tag element
temp = tag[i];
tag[i] = tag[j];
tag[j] = temp;
}
j += 1;
}
i += 1;
}
}
//print the collection elements using tag key
func display(_ collection: [Int], _ tag: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print("  ", collection[tag[i]], terminator: "");
i += 1;
}
}
}
func main()
{
let obj: MySort = MySort();
//Define the collection of integer elements
let collection: [Int] = [3, 7, 19, 2, 4, 18, 1, 2, 0, -2, 5];
//Get the size of collection
let size: Int = collection.count;
//Tag which is storing the location of sorted elements
var tag: [Int] = Array(repeating: 0, count: size);
var i: Int = 0;
//Set index of tag element
while (i < size)
{
tag[i] = i;
i += 1;
}
print(" Before Sort", terminator: "");
obj.display(collection, tag, size);
obj.tag_sort(collection, &tag, size);
print("\n Tag Sort", terminator: "");
obj.display(collection, tag, size);
}
main();``````

#### Output

`````` Before Sort   3   7   19   2   4   18   1   2   0   -2   5
Tag Sort   -2   0   1   2   2   3   4   5   7   18   19``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.