Сортировка тегов (для сортировки и оригинала)
Это не новый алгоритм сортировки, а идея, когда нам нужно избежать перестановки больших объектов или получить доступ к элементам большого массива как в исходном, так и в отсортированном порядке.
Распространенной задачей сортировки является сортировка элементов массива с использованием алгоритма сортировки, такого как быстрая сортировка, пузырьковая сортировка и т. Д., Но могут быть моменты, когда нам нужно сохранить фактический массив в тактильном состоянии и использовать «помеченный» массив для хранения правильное позиционирование массива при его сортировке. Когда мы хотим получить доступ к элементам отсортированным способом, мы можем использовать этот «помеченный» массив.
Зачем использовать сортировку по тегам?
Когда мы работаем с большим массивом объектов, замена этих больших объектов может оказаться слишком затратной. В конце концов, все дело в обмене дисками, и мы хотим свести его к минимуму!
- Сортировка тегов позволяет сортировать целочисленный массив после тегирования его исходным объектом.
- В свою очередь, мы меняем местами только целые числа массива тегов, а не большой массив объектов.
- Фактические элементы не изменяются в процессе сортировки. Позиции в массиве тегов изменяются, поэтому они будут содержать правильный порядок элементов при сортировке.
В этом примере исходные элементы в 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.