Tag Sort (To get both sorted and original)

This is not a new sorting algorithm, but an idea when we need to avoid swapping of large objects or need to access elements of a large array in both original and sorted orders. A common sorting task is to sort elements of an array using a sorting algorithm like Quick Sort, Bubble Sort.. etc, but there may be times when we need to keep the actual array in tact and use a “tagged” array to store the correct positioning of the array when it is sorted. When we want to access elements in sorted way, we can use this “tagged” array.

Why to use Tag Sort?

When we are operating on large array of objects, it might be too costly to swap these large object. After all its about the disk swaps and we want to minimize it!

• Tag Sort allows sorting an integer array after tagging it with original object.
• In turn, we only swap the tag array integers instead of large array of objects.
• 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 elements when they are sorted.

In this example, the original elements in arr[] are not changed, but the original elements in tag[] are manipulated. The tag[] array will now hold the correct subscript ordering of the elements in arr[] so the array can be sorted into descending order when the tag[] array is called upon.  

Another Example, Suppose we have following Person object which inherently takes large chunk of memory( in GB or hundreds of MB).

class Person 
{
    private int id;
    private float salary;
    private Object someBigObject = new Object(); 
    public Person(int id, float salary) 
    { }
    public float getSalary() 
    { }
    public String toString() 
    { }
}

Hence, it might not be practical to move around these objects as disk seeks for swaps can eat up a lot of time. To avoid this, we start by creating a tag array.

• Every Person object is tagged to one element in the tag array and Instead of swapping the person object for sorting based on salary , we swap the tag[] integers.
• While printing the sorted array we take a cue from the tag array to print the sorted Persons array.
• Eventually, we’ll escape swapping large Persons object.

Below is the implementation of above idea. 

Given Person and Tag 
Person{id=0, salary=233.5, someBigObject=java.lang.Object@52cc8049} : Tag: 0
Person{id=1, salary=23.0, someBigObject=java.lang.Object@5b6f7412} : Tag: 1
Person{id=2, salary=13.98, someBigObject=java.lang.Object@27973e9b} : Tag: 2
Person{id=3, salary=143.2, someBigObject=java.lang.Object@312b1dae} : Tag: 3
Person{id=4, salary=3.0, someBigObject=java.lang.Object@7530d0a} : Tag: 4
New Tag Array after getting sorted as per Person[] 
4
2
1
3
0
Person{id=4, salary=3.0, someBigObject=java.lang.Object@7530d0a}
Person{id=2, salary=13.98, someBigObject=java.lang.Object@27973e9b}
Person{id=1, salary=23.0, someBigObject=java.lang.Object@5b6f7412}
Person{id=3, salary=143.2, someBigObject=java.lang.Object@312b1dae}
Person{id=0, salary=233.5, someBigObject=java.lang.Object@52cc8049}

This article is contributed by Rishi Verma . If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.