Сортировка тегов (для сортировки и оригинала)

Опубликовано: 20 Января, 2022

Это не новый алгоритм сортировки, а идея, когда нам нужно избежать перестановки больших объектов или получить доступ к элементам большого массива как в исходном, так и в отсортированном порядке.
Распространенной задачей сортировки является сортировка элементов массива с использованием алгоритма сортировки, такого как быстрая сортировка, пузырьковая сортировка и т. Д., Но могут быть моменты, когда нам нужно сохранить фактический массив в тактильном состоянии и использовать «помеченный» массив для хранения правильное позиционирование массива при его сортировке. Когда мы хотим получить доступ к элементам отсортированным способом, мы можем использовать этот «помеченный» массив.

Зачем использовать сортировку по тегам?

Когда мы работаем с большим массивом объектов, замена этих больших объектов может оказаться слишком затратной. В конце концов, все дело в обмене дисками, и мы хотим свести его к минимуму!

  • Сортировка тегов позволяет сортировать целочисленный массив после тегирования его исходным объектом.
  • В свою очередь, мы меняем местами только целые числа массива тегов, а не большой массив объектов.
  • Фактические элементы не изменяются в процессе сортировки. Позиции в массиве тегов изменяются, поэтому они будут содержать правильный порядок элементов при сортировке.

В этом примере исходные элементы в arr [] не изменяются, но изменяются исходные элементы в tag []. Теперь массив tag [] будет содержать правильный порядок индексов элементов в arr [], поэтому массив может быть отсортирован в порядке убывания при вызове массива tag [].

Другой пример. Предположим, у нас есть следующий объект Person, который по своей сути занимает большой кусок памяти (в ГБ или сотни МБ).

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

Следовательно, может быть непрактично перемещать эти объекты, поскольку поиск диска для подкачки может отнимать много времени. Чтобы этого избежать, мы начнем с создания массива тегов.

  • Каждый объект Person привязан к одному элементу в массиве тегов, и вместо замены объекта person для сортировки по заработной плате мы меняем местами целые числа tag [].
  • При печати отсортированного массива мы берем реплику из массива тегов, чтобы напечатать отсортированный массив Persons.
  • В конце концов, мы избежим замены большого объекта Persons.

Below is the implementation of above idea.

// Java Program to illustrate Tag Sort. This code
// uses Bubble Sort to modify tag array according
// to salaries. We can use other optimized sorting
// techniques also.
class Person
{
    private int id;
    private float salary;
    private Object someBigObject = new Object();
  
    public Person(int id, float salary)
    {
        this.id = id;
        this.salary = salary;
    }
  
    public float getSalary()
    {
        return salary;
    }
  
    @Override
    public String toString()
    {
        return "Person{" +
               "id=" + id +
               ", salary=" + salary +
               ", someBigObject=" + someBigObject +
               "}";
    }
}
  
public class Main
{
    public static void main(String[] args)
    {
        // Creating objects and their original
        // order (in tag array)
        int n = 5;
        Person persons[] = new Person[n];
        persons[0] = new Person(0, 233.5f);
        persons[1] = new Person(1, 23f);
        persons[2] = new Person(2, 13.98f);
        persons[3] = new Person(3, 143.2f);
        persons[4] = new Person(4, 3f);
        int tag[] = new int[n];
        for (int i = 0; i < n; i++)
            tag[i] = i;
  
        // Every Person object is tagged to
        // an element in the tag array.
        System.out.println("Given Person and Tag ");
        for (int i = 0; i < n; i++)
            System.out.println(persons[i] +
                               " : Tag: " + tag[i]);
  
        // Modifying tag array so that we can access
        // persons in sorted order.
        tagSort(persons, tag);
  
        System.out.println("New Tag Array after "+
                           "getting sorted as per Person[] ");
        for (int i=0; i<n; i++)
            System.out.println(tag[i]);
  
        // Accessing persons in sorted (by salary)
        // way using modified tag array.
        for (int i = 0; i < n; i++)
            System.out.println(persons[tag[i]]);
    }
  
    // Modifying tag array so that we can access
    // persons in sorted order of salary.
    public static void tagSort(Person persons[],
                               int tag[])
    {
        int n = persons.length;
        for (int i=0; i<n; i++)
        {
            for (int j=i+1; j<n; j++)
            {
                if (persons[tag[i]].getSalary() >
                        persons[tag[j]].getSalary())
                {
                    // Note we are not sorting the
                    // actual Persons array, but only
                    // the tag array
                    int temp = tag[i];
                    tag[i] = tag[j];
                    tag[j] = temp;
                }
            }
        }
    }
}

Выход:

Данное лицо и тег 
Человек {id = 0, salary = 233,5, someBigObject=java.lang.Object@15db9742}: Тег: 0
Человек {id = 1, salary = 23.0, someBigObject=java.lang.Object@6d06d69c}: Тег: 1
Человек {id = 2, salary = 13.98, someBigObject=java.lang.Object@7852e922}: Тег: 2
Человек {id = 3, salary = 143.2, someBigObject=java.lang.Object@4e25154f}: Тег: 3
Человек {id = 4, salary = 3.0, someBigObject=java.lang.Object@70dea4e}: Тег: 4
Новый массив тегов после сортировки по Person [] 
4
2
1
3
0
Человек {id = 4, salary = 3.0, someBigObject=java.lang.Object@70dea4e}
Человек {id = 2, salary = 13.98, someBigObject=java.lang.Object@7852e922}
Человек {id = 1, salary = 23.0, someBigObject=java.lang.Object@6d06d69c}
Человек {id = 3, salary = 143,2, someBigObject=java.lang.Object@4e25154f}
Человек {id = 0, salary = 233,5, someBigObject=java.lang.Object@15db9742}

Эта статья предоставлена Риши Верма . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

РЕКОМЕНДУЕМЫЕ СТАТЬИ