Skip to main content

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
Last updated on by Kalkicode




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.

New Comment