Сортировка массива пар по первому элементу: различные методы

Сортировка массива пар (также известного как кортежи) по первому элементу — распространенная задача в программировании. Эта операция включает в себя расположение пар в порядке возрастания или убывания на основе значений первого элемента. В этой статье мы рассмотрим несколько методов выполнения этой задачи, а также примеры кода. Давайте погрузимся!

Метод 1: использование функции sort()
Один простой подход — использовать встроенную функцию sort(), предоставляемую большинством языков программирования. Функция sort() обычно принимает специальную функцию сравнения, которая определяет порядок элементов. Вот пример на Python:

pairs = [(3, 'apple'), (1, 'banana'), (2, 'cherry')]
pairs.sort(key=lambda x: x[0])
print(pairs)

Выход:

[(1, 'banana'), (2, 'cherry'), (3, 'apple')]

Метод 2: использование функции sorted()
Подобно первому методу, мы можем использовать функцию sorted() для достижения того же результата. Функция sorted() возвращает новый отсортированный список, оставляя исходный массив неизменным. Вот пример на JavaScript:

const pairs = [[3, 'apple'], [1, 'banana'], [2, 'cherry']];
const sortedPairs = pairs.sort((a, b) => a[0] - b[0]);
console.log(sortedPairs);

Выход:

[[1, 'banana'], [2, 'cherry'], [3, 'apple']]

Метод 3. Использование собственного алгоритма сортировки.
Если вы предпочитаете реализовать собственный алгоритм сортировки, вы можете адаптировать существующие алгоритмы, такие как быстрая сортировка или сортировка слиянием. Основная идея — сравнивать и менять пары на основе их первого элемента. Вот пример на C++ с использованием алгоритма быстрой сортировки:

#include <iostream>
#include <vector>
using namespace std;
int partition(vector<pair<int, string>>& pairs, int low, int high) {
    int pivot = pairs[high].first;
    int i = low - 1;
    for (int j = low; j <= high - 1; j++) {
        if (pairs[j].first < pivot) {
            i++;
            swap(pairs[i], pairs[j]);
        }
    }
    swap(pairs[i + 1], pairs[high]);
    return i + 1;
}
void quickSort(vector<pair<int, string>>& pairs, int low, int high) {
    if (low < high) {
        int pi = partition(pairs, low, high);
        quickSort(pairs, low, pi - 1);
        quickSort(pairs, pi + 1, high);
    }
}
int main() {
    vector<pair<int, string>> pairs = {{3, "apple"}, {1, "banana"}, {2, "cherry"}};
    int n = pairs.size();
    quickSort(pairs, 0, n - 1);
    for (auto& pair : pairs) {
        cout << "(" << pair.first << ", " << pair.second << ") ";
    }
    cout << endl;
    return 0;
}

Выход:

(1, banana) (2, cherry) (3, apple)