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

В этом блоге мы исследуем мир алгоритмов сортировки. Мы начнем с введения в то, что такое алгоритмы сортировки и почему они необходимы. Затем мы углубимся в различные типы алгоритмов сортировки, включая пузырьковую сортировку, сортировку выбором, сортировку вставками, сортировку слиянием, быструю сортировку и другие. Мы объясним принципы работы каждого алгоритма и их временную и пространственную сложность.

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

Независимо от того, являетесь ли вы новичком или опытным программистом, этот блог предоставит вам всестороннее представление об алгоритмах сортировки, их реализации и применении. Итак, приступим.

Пузырьковая сортировка 🫧

Этот алгоритм проходит данные слева направо, и вот шаги:

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

Таким образом, самый большой элемент сначала перемещается в крайний правый конец. Давайте посмотрим на его реализацию на Java:

class Solution {
    public int[] bubbleSort (int[] heights) {
        for(int i=0;i<heights.length;i++){
            for(int j=0;j<heights.length-1;j++){
                if(heights[j]>heights[j+1]){
                    int tempHeight = heights[j];
                    heights[j] = heights[j+1];
                    heights[j+1] = tempHeight;
                }
            }
        }
        return heights;
    }
}

Нам нужно проверить каждый элемент в «j» с соседним элементом «j + 1» n раз (итерируя с i), пока самый большой элемент не будет пузыриться до конца массива.

Сложность времени:

O(n²) —Поскольку алгоритм использует вложенный цикл (для замены только соседних элементов).

Космическая сложность:

O(1) — Алгоритм работает, сравнивая соседние элементы во входном массиве и меняя их местами, если они находятся в неправильном порядке. Эта операция может выполняться на месте, что означает, что сам входной массив может быть изменен для сортировки данных без дополнительной памяти.

Преимущества и недостатки пузырьковой сортировки:

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

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

Этот алгоритм находит минимальное значение в списке и заменяет его значением в первой позиции, а затем повторяет этот процесс для оставшейся части списка.

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

Давайте посмотрим, как этот алгоритм реализован в Java:

class Solution {
    public int[] selectionSort(int[] heights) {
        for (int i = 0; i < heights.length-1; i++){
            int min_idx = i;
            for (int j = i+1; j < heights.length; j++)
                if (heights[j] < heights[min_idx])
                    min_idx = j;

            int tempHeight = heights[min_idx];
            heights[min_idx] = heights[i];
            heights[i] = tempHeight;
        }
        return heights;
    }
}

На каждой итерации мы ищем минимальный элемент, который еще не «выбран», а затем сравниваем и меняем местами аналогично алгоритму пузырьковой сортировки.

Сложность времени:

O(n²) —Поскольку алгоритм использует вложенный цикл (для поиска минимального индекса и замены).

Космическая сложность:

O(1) — поскольку дополнительная память используется только для временных переменных при замене двух значений в массиве. Сортировка выбором никогда не делает более O(n) свопов и может быть полезна, когда запись в память требует больших затрат.

Преимущества VS Недостатки сортировки выбором:

  • Преимущества: простая реализация, эффективность для небольших наборов данных, сортировка на месте.
  • Недостатки: квадратичная временная сложность.

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

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

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

Давайте посмотрим, как это реализовано в Java:

class Solution {
    public int[] insertionSort(int[] heights) {
        for (int i = 1; i < heights.length; i++){
            int key = heights[i];
            int j = i-1;
            while(j>=0 && heights[j]>key){
                heights[j+1] = heights[j];
                j = j-1;
            }
            heights[j+1] = key;
        }
        return heights;
    }
}

Мы движемся слева направо, устанавливая ключ для каждого индекса, начиная с 1. Затем мы перебираем все предыдущие элементы до ключа, если элемент больше ключа, то меняем местами.

Сложность времени:

O(n²) —Поскольку алгоритм использует вложенный цикл (для поиска ключа и обмена).

Космическая сложность:

O(1) — Как и в предыдущих алгоритмах, мы меняем местами, используя тот же входной массив.

Преимущества VS Недостатки сортировки вставками:

  • Преимущества: Эффективен для небольших наборов данных, адаптивен (эффективен для почти отсортированных данных), стабильная сортировка, сортировка на месте.
  • Недостатки: квадратичная временная сложность.

Сортировка слиянием 🔀

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

  • Разделите массив на две половины.
  • Рекурсивно вызывайте функцию для каждой половины массива, пока в каждом подмассиве не останется только один элемент (массив с одним элементом всегда отсортирован).
  • Объедините отсортированные подмассивы в один отсортированный массив с помощью функции слияния.

Посмотрим на реализацию на Java:

class Solution {
    public int[] mergeSort(int[] heights) {
        int len = heights.length;
        if(len<2){
            return names;
        }
        int mid = len/2;
        int[] leftHeight = new int[mid];
        int[] rightHeight = new int[len-mid];      

        for(int i=0;i<mid;i++){
            leftHeight[i] = heights[i];
        }
        for(int i=mid;i<len;i++){
            rightHeight[i-mid] = heights[i];
        }

        mergeSort(leftHeight);
        mergeSort(rightHeight);

        int i=0,j=0,k=0;
        while(i<leftHeight.length && j<rightHeight.length){
            if(leftHeight[i]<=rightHeight[j]){
                heights[k] = leftHeight[i];
                i++;
            } else {
                heights[k] = rightHeight[j];
                j++;
            }
            k++;
        }
        while(i<leftHeight.length){
            heights[k] = leftHeight[i];
            i++;
            k++;
        }        
        while(j<rightHeight.length){
            heights[k] = rightHeight[j];
            j++;
            k++;
        }

        return heights;
    }
}

Мы продолжаем рекурсивно делить массив, пока он не достигнет длины 1, а затем начинаем процесс слияния. Мы проверяем два массива, которые у нас есть, и если один меньше другого, добавляем его в массив.

Сложность времени:

O(n logn) —Поскольку алгоритм использует вложенный цикл (для поиска ключа и обмена).

Космическая сложность:

O(n) — поскольку мы ввели два новых массива (левый и правый), но их общая длина равна n.

Преимущества VS Недостатки сортировки слиянием:

  • Преимущества: Быстрое время выполнения — O(n log n), стабильная сортировка.
  • Недостатки: требуется дополнительное место в памяти для временных массивов.

Быстрая сортировка 🏃

Подобно сортировке слиянием, использует принцип «разделяй и властвуй», но выбирает опорный элемент и делит список на два подсписка — меньше и больше, чем опорный. Рекурсивно сортирует подсписки.

  • Ключевой процесс в quickSort — это partition().
  • Целью разделов является размещение опорной точки (любой элемент может быть выбран в качестве опорной точки) в правильном положении в отсортированном массиве.
  • Поместите все меньшие элементы слева от оси
  • Поместите все большие элементы справа от оси
  • Разделение выполняется рекурсивно с каждой стороны опорной точки после того, как опорная точка помещена в правильное положение.

Вот реализация Java:

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }
    public void quickSort(int[]arr, int lowIndex, int highIndex){
        if(lowIndex>=highIndex) return;
        int pivotIndex = new Random().nextInt(highIndex - lowIndex) + lowIndex;
        int pivot = arr[pivotIndex];
        swap(arr,pivotIndex,highIndex);
        int left = partition(arr,lowIndex,highIndex,pivot);
        quickSort(arr,lowIndex,left-1);
        quickSort(arr,left+1,highIndex);
         
    }
    public int partition(int[]arr,int lowIndex,int highIndex,int pivot){
        int left = lowIndex;
        int right = highIndex;
        while(left<right){
            while(arr[left]<=pivot && left<right){
                left++;
            }            
            while(arr[right]>=pivot && right>left){
                right--;
            }
            swap(arr,left,right);
        }
        swap(arr,left,highIndex);
        return left;
    }
    public void swap(int[]array,int index1,int index2){
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }
}

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

Функция partition() работает, перебирая массив и сравнивая каждый элемент с опорным элементом. Если элемент меньше опорного элемента, то он заменяется элементом с текущим индексом. Этот процесс продолжается до тех пор, пока опорный элемент не окажется в правильном положении в отсортированном массиве.

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

Сложность времени:

O(n log n) —Поскольку алгоритм делит задачу на все более мелкие подзадачи, каждая подзадача решается за время O(n).

Космическая сложность:

O(log n) — поскольку алгоритм использует стек для хранения рекурсивных вызовов, стек может увеличиваться до глубины O(log n).

Преимущества и недостатки быстрой сортировки:

  • Преимущества: в среднем быстрее других алгоритмов, эффективен для больших наборов данных, сортировка на месте.
  • Недостатки: в худшем случае время O(n²), нестабильная сортировка.

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

  • Пузырьковая сортировка — это простой алгоритм, который легко понять и реализовать. Однако он также неэффективен, поскольку его временная сложность в худшем случае составляет O(n²). Пузырьковая сортировка не подходит для больших массивов данных.
  • Сортировка выбором — еще один простой алгоритм, который легко понять и реализовать. Это более эффективно, чем пузырьковая сортировка, с наихудшей временной сложностью O (n²). Однако сортировка выбором не так эффективна, как некоторые другие алгоритмы, такие как сортировка слиянием или быстрая сортировка.
  • Сортировка вставками — это стабильный алгоритм сортировки, то есть он сохраняет исходный порядок одинаковых элементов в массиве. Сортировка вставками эффективна для небольших массивов данных, но становится неэффективной для больших массивов данных.
  • Сортировка слиянием — это очень эффективный алгоритм сортировки по принципу «разделяй и властвуй». Он имеет временную сложность в наихудшем случае O (n log n). Сортировка слиянием — хороший выбор для больших массивов данных.
  • Quicksort — еще один очень эффективный алгоритм сортировки по принципу «разделяй и властвуй». Он имеет временную сложность в наихудшем случае O (n log n). Однако быстрая сортировка может быть нестабильной, что означает, что она может не сохранить исходный порядок одинаковых элементов в массиве.

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

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