Сортировка массива пар с использованием заданной функции сортировки

Question

Допустим, у меня есть доступ к стабильному алгоритму сортировки, который может сортировать массив целых чисел A. Поэтому sort(A) вернет элементы A в порядке возрастания.

У меня есть массив пар целых чисел, которые я хотел бы отсортировать по второму элементу, где возможны дубликаты. Если дубликаты существуют во втором элементе, массив сохранит порядок элементов (он должен быть стабильным).

Так что, если array имеет записи:

(1,2),(1,1),(0,2),(3,2),(4,1)

Тогда результат будет:

(1,1),(4,1),(1,2),(0,2),(3,2)

Возможно ли это, используя только предоставленную мне функцию сортировки, или мне нужно написать собственную функцию сортировки?

Answer 1

Подумав некоторое время, я думаю, что это может сработать, но, возможно, кто-то может проверить, имеет ли это смысл:
Я думал о создании карты такой, чтобы (если (x, y) и (z, y) были единственными парами в массиве, чей второй компонент - y, тогда map (y) = [x, z]. Другими словами, с учетом целого числа x эта карта находит набор всех целых чисел y, таких что (y, x) является парой в массиве. Я должен быть в состоянии построить эту карту в линейное время (в размере массива пар), проходя через массив, а затем после сортировки по y, использовать карту, чтобы восстановить исходный массив (снова в линейном времени в размере из массива пар.).

Answer 2

array.sorted (по: {$ 0.1 <$ 1.1}) </p>