Глава 3: Алгоритмы сортировки

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

В этой главе мы рассмотрим несколько классических методов сортировки и важную структуру данных, известную как очередь с приоритетом. Мы начнем с обсуждения нескольких элементарных методов сортировки, включая сортировку выбором, сортировку вставками и сортировку Шелла. Эти методы уместны во многих приложениях, но для больших задач мы обращаемся к сортировке слиянием и быстрой сортировке, двум рекурсивным алгоритмам сортировки, которые можно использовать для сортировки огромного количества элементов. Мы завершим обсуждением очередей с приоритетом и их использованием в сортировке и других приложениях.

Элементарные сортировки

Простейшие алгоритмы сортировки выполняют следующие операции:

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

Эти операции отражают, как люди обычно выполняют задачи сортировки, и эффективны для небольших размеров задач. Однако они не масштабируются хорошо и становятся непрактичными для сортировки больших массивов.

Сортировка выбором

Сортировка выбором - это простой алгоритм сортировки, который работает следующим образом: Сначала найдите наименьший элемент в массиве и поменяйте его местами с первым элементом (если первый элемент уже является наименьшим). Затем найдите следующий наименьший элемент и поменяйте его местами со вторым элементом. Продолжайте таким образом, пока весь массив не будет отсортирован.

Внутренний цикл сортировкиHere is the Russian translation of the provided markdown file, with the code comments translated:

Сортировка выбором используется для поиска минимального элемента в несортированном подмассиве a[i..N-1]. Индекс минимального элемента сохраняется в min. Затем a[i] обменивается с a[min], что помещает минимальный элемент на его окончательную позицию. По мере того, как индекс i перемещается слева направо, элементы слева от него находятся в отсортированном порядке в массиве и больше не будут затронуты.

Вот реализация сортировки выбором на Java:

public static void selectionSort(Comparable[] a) {
    // Длина массива
    int N = a.length;
    // Перебор элементов массива
    for (int i = 0; i < N; i++) {
        // Индекс минимального элемента
        int min = i;
        // Поиск минимального элемента в оставшейся части массива
        for (int j = i+1; j < N; j++) {
            if (less(a[j], a[min])) min = j;
        }
        // Обмен элементов
        exch(a, i, min);
    }
}

Сортировка выбором использует примерно ~N^2/2 сравнений и N обменов для сортировки массива длины N. Время выполнения не зависит от входных данных - оно занимает примерно столько же времени для массива, который уже отсортирован, или для массива с одинаковыми ключами, как и для случайно упорядоченного массива.

Сортировка вставками

Сортировка вставками - это еще один простой алгоритм сортировки, который работает, построив окончательный отсортированный массив по одному элементу за раз. Он гораздо менее эффективен для больших массивов, чем более продвинутые алгоритмы, такие как быстрая сортировка, пирамидальная сортировка или слияние, но у него есть некоторые преимущества:

Он эффективен для небольших наборов данных.
Он более эффективен на практике, чем сортировка выбором.
Он стабилен, т.е. не меняет относительный порядок элементов с равными ключами.
Он на месте, т.е. требует только постоянного дополнительного объема памяти O(1).
Он онлайн, т.е. может сортировать список по мере его получения.

Вот реализация сортировки вставками на Java:

public static void insertionSort(Comparable[] a) {
    // Длина массива
    int N = a.length;
    // Перебор элементов массива, начиная со второго
    for (int i = 1; i < N; i++) {
        // Вставка текущего элемента в отсортированную часть
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
            // Обмен элементов
            exch(a, j, j-1);
        }
    }
}

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

Время работы сортировки вставками зависит от начального порядка элементов во входных данных. Например, если массив большой, и его элементы уже отсортированы (или почти отсортированы), то сортировка вставками будет намного быстрее, чем если элементы расположены в случайном порядке или в обратном порядке.

Сортировка Шелла

Сортировка Шелла - это простое расширение сортировки вставками, которое ускоряет процесс за счет разрешения обмена элементов массива, находящихся на большом расстоянии друг от друга, что позволяет получить частично отсортированные массивы, которые в дальнейшем могут быть эффективно отсортированы с помощью сортировки вставками.

Идея заключается в том, чтобы перераспределить элементы массива таким образом, чтобы каждая h-я запись (начиная с любой) давала отсортированную подпоследовательность. Такой массив называется h-отсортированным. Другими словами, h-отсортированный массив состоит из h независимых отсортированных подпоследовательностей, перемешанных вместе. Выполняя h-сортировку для некоторых больших значений h, мы можем перемещать элементы в массиве на большие расстояния, что упрощает h-сортировку для меньших значений h. Использование такой процедуры для любой последовательности значений h, заканчивающейся на 1, приведет к получению отсортированного массива: это и есть сортировка Шелла.

Вот реализация сортировки Шелла на Java:

public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;
    private int N;
    
    public MaxPQ(int capacity) {
        pq = (Key[]) new Comparable[capacity+1];
    }
   
    public boolean isEmpty() {
        return N == 0;
    }
   
    public void insert(Key key) {
        pq[++N] = key;
        swim(N);
    }
   
    public Key delMax() {
        Key max = pq[1];
        exch(1, N--);
        sink(1);
        pq[N+1] = null;
        return max;
    }
   
    private void swim(int k) {
        while (k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }
   
    private void sink(int k) {
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
   
    private boolea
```Вот перевод на русский язык с сохранением комментариев к коду:
 
```java
n less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }
 
    private void exch(int i, int j) {
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
}

Этот код реализует двоичную кучу с максимальным элементом на вершине, используя массив pq для хранения упорядоченного по куче двоичного дерева. Операции insert() и delMax() поддерживают инвариант кучи, используя вспомогательные методы swim() и sink() для восстановления порядка кучи путем обмена ключей с родителем, который больше, чем ребенок, или ребенком, который больше, чем его родитель, соответственно.

Секундомер

Более полезный абстрактный тип данных - это простая и эффективная абстракция для секундомера, показанная на противоположной странице. Чтобы использовать его, создайте объект Stopwatch, когда вы хотите запустить таймер, затем используйте метод elapsedTime() для получения времени, прошедшего с момента создания объекта в секундах. Реализация использует System.currentTimeMillis() Java для получения текущего времени в миллисекундах с полуночи 1 января 1970 года.

Переменная экземпляра start записывает время, когда был создан секундомер, а elapsedTime() использует start для вычисления прошедшего времени. Показанный клиент типичен: он выполняет некоторые вычисления и использует Stopwatch для измерения времени, которое занимают вычисления. Тип данных Stopwatch является эффективной абстракцией, потому что он разделяет концепцию секундомера (интерфейс) и реализацию (использование System.currentTimeMillis() Java). Это разделение интерфейса и реализации является фундаментальной характеристикой абстрактных типов данных, которую мы будем видеть во всех АТД на протяжении всей книги.

Резюме

Абстрактные типы данных являются важным элементом объектно-ориентированного программирования, широко используемым в современном программировании. В этом разделе мы рассмотрели:

Определение абстрактного типа данных как класса Java с переменными экземпляра для определения значений типа данных и методами экземпляра для реализации операций над этими значениями.
Разработка нескольких реализаций одного и того же API, используя различные представления одного и того же абстрактного типа данных.Тип абстрактных данных.
Различение API, клиентов и реализаций абстрактного типа данных.
Проектирование API для абстрактных типов данных.
Разработка клиентов и тестовых клиентов для использования в тестировании и отладке.
Рассуждение о правильности реализации абстрактного типа данных с использованием утверждений.
Сравнение производительности различных реализаций одного и того же API.

Эти виды деятельности являются неотъемлемой частью разработки любой Java-программы. Каждая Java-программа, которую мы пишем, будет включать в себя использование абстрактных типов данных из библиотек; многие будут включать разработку новых абстрактных типов данных. В следующем разделе мы рассмотрим три основных абстрактных типа данных, которые являются важными компонентами огромного количества программ, а в Разделе 1.4 мы подробно рассмотрим процесс анализа характеристик производительности реализаций.

Chapter 2 Algorithms Fundamentals Chapter 4 Searching Algorithms