Алгоритмы сортировки

Сортировки сравнением (Comparison sorts)

Сортировки сравнением имеют минимальную сложность O(n*lg n).

Сортировка вставками (Insert sort)

Сложность: O(n²)

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

Преимущества: практически не требует выделения памяти (всего O(1)); алгоритм эффективен при малом размере входного массива.

Недостатки: неэффективен на большом размере входного массива (более 100).

Алгоритм:

Вход: массив A, состоящий из элементов A[1], A[2], ..., A[n]

for i = 2, 3, ..., n:  
    key = A[i]
    j = i - 1
    while j > 0 and A[j] > key:
        A[j + 1] = A[j]
        j = j - 1
    A[j + 1] = key

Реализация на Java:

//insertion sort
public static void insertionSort(int[] arr) {
    int i, j, tmp;
    //двигаемся вперед по массиву
    for (i = 1; i < arr.length; i++) {
        j = i;
        //двигаем элемент назад, пока он больше предыдущих
        while (j > 0 && arr[j - 1] > arr[j]) {
            tmp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = tmp;
            j--;
        }
    }
}

Сортировка слиянием (Merge sort)

Сложность: O(n*lg n)

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

Преимущества: алгоритм эффективен при большом размере входного массива (более 1000).

Недостатки: требует выделения O(n) памяти

Алгоритм:

function mergesort(m)
    var list left, right, result
    if length(m) ≤ 1
        return m
    else
        middle = length(m) / 2
        for each x in m up to middle
            add x to left
        for each x in m after middle
            add x to right
        left = mergesort(left)
        right = mergesort(right)
        result = merge(left, right)
        return result
    end if

function merge(left,right)
    var list result
    while length(left) > 0 and length(right) > 0
        if first(left) ≤ first(right)
            append first(left) to result
            left = rest(left)
        else
            append first(right) to result
            right = rest(right)
        end if
    if length(left) > 0 
        append left to result
    if length(right) > 0 
        append right to result
    return result

Реализация на Java:

//merge sort
public static int[] mergeSort(int[] arr) {
    if (arr.length <= 1)  return arr;

    int mid = arr.length / 2;
    int[] left = new int[mid];
    int[] right = new int[mid + arr.length%2];

    int j = 0;
    for (int i = 0; i < arr.length; i++) {
        if (i < arr.length / 2) {
            left[i] = arr[i];
        } else {
            right[j++] = arr[i];
        }
    }
    return Merge(mergeSort(left), mergeSort(right));
}

public static int[] Merge(int[] left, int[] right) {
    int a = 0, b = 0;
    int[] merged = new int[left.length + right.length];
    //забиваем отсортированный массив из левой и правой частей
    for (int i = 0; i < left.length + right.length; i++) {
        //поочередно берем меньший член из крайних левого и правого
        if (b < right.length && a < left.length)
            if (left[a] > right[b] && b < right.length)
                merged[i] = right[b++];
            else
                merged[i] = left[a++];
        else
            if (b < right.length)
                merged[i] = right[b++];
            else
                merged[i] = left[a++];
    }
    return merged;
}

Пирамидальная сортировка (Heap sort)

Сложность: O(n*lg n)

Сортировка пирамидой использует сортирующее дерево. Алгоритм заключается в выстраивании элементов массива в сортирующее дерево. Итерационно удаляем элементы из корня под одному за раз и перестраиваем дерево. То есть на первом шаге обмениваем Array[1] и Array[n], преобразовываем Array[1], Array[2], … , Array[n-1] в сортирующее дерево. Затем переставляем Array[1] и Array[n-1], преобразовываем Array[1], Array[2], … , Array[n-2] в сортирующее дерево. Процесс продолжается до тех пор, пока в сортирующем дереве не останется один элемент. Тогда Array[1], Array[2], … , Array[n] — упорядоченная последовательность.

Преимущества: практически не требует выделения памяти (всего O(1))

Недостатки: Из-за сложности алгоритма выигрыш получается только на больших n (более 1000)

Алгоритм:

function build_max_heap(A)
  for i = length(A) downto 2
    do Обменять A[1] на A[i]
      heap_size[A] = heap_size[A] - 1
      max_heapify(A,1)

function max_heapify(A,i)
  l = left(i)
  r = right(i)
  if l <= heap_size(A) and A[l] > A[i]
    then largest = l
    else largest = i
  if r <= heap_size(A) and A[r] > A[largest]
    then largest = r
  if largest != i
    then Обменять A[i] на A[largest]
      max_heapify(A, largest)

Реализация на Java:

public static void heapSort(int[] arr) {
    for(int i = arr.length; i > 1; i--){
        buildMaxHeap(arr, i - 1);
    }
}

public static void buildMaxHeap(int[] arr, int max_index){
    int i, o;
    int leftChild, rightChild, maxChild, root, temp;
    root = (max_index -1)/2;

    //обходим дерево в поисках максимального члена (ранее отсортированные максимальные игнорируем)
    for(i = root; i >= 0; i--){
        leftChild = (2*i) + 1;
        rightChild = (2*i) + 2;

        if((leftChild <= max_index) && (rightChild <= max_index)){
            if(arr[rightChild] >= arr[leftChild])
                maxChild = rightChild;
            else
                maxChild = leftChild;
        } else{
            if(rightChild > max_index)
                maxChild = leftChild;
            else
                maxChild = rightChild;
        }

        //передвигаем  максимальный член вверх по пирамиде (начало массива)
        if(arr[i] < arr[maxChild]){
            temp = arr[i];
            arr[i] = arr[maxChild];
            arr[maxChild] = temp;
        }
    }

    //убираем максимальный член в конец массива
    temp = arr[0];
    arr[0] = arr[max_index];
    arr[max_index] = temp;
}

Быстрая сортировка (Quick sort)

Сложность: средняя O(n*lg n), максимальная O(n²)

Еще одна сортировка, основанная на парадигме "Разделяй и властвуй". Массив A[p..r] разбивается (путем переупорядочивания его элементов) на два подмассива A[p..q-1] и A[q+1..r]. Каждый элемент первого подмассива не превышает каждый елемент второго. Индекс q вычисляется в ходе процедуры разбиения и называется опорным элементом. Подмассивы сортируются путем рекурсивного вызова процедуры быстрой сортировки. После этого весь массив оказывается отсортированным.

Преимущества: при качественной реализации один из самых быстродействующих алгоритмов на практике; требует лишь O(lg n) дополнительной памяти

Недостатки: при неудачном выборе опорного элемента время вычисления деградирует к O(n²).

Алгоритм:

для сортировки всего списка вызов выглядит quick_sort(A,1,length[A])

function quick_sort(A,p,r)
  if p < r 
    then q = partition(A,p,r)
      quick_sort(A,p,q-1)
      quick_sort(A,q+1,r)

function partition(A,p,r)
  x = A[r]
  i = p - 1
  for i = p to r - 1
    do if A[j] <= x
      then i = i + 1
        Обменять A[i] на A[j]
  Обменять A[i + 1] на A[r]
  return i + 1 

Реализация на Java:

//quick sort
public static void quickSort(int[] arr, int low, int high) {
    int i = low;
    int j = high;
    //выбираем середину в качестве опорного элемента
    int mid = arr[(low + high)/2];
    //сдвигаем меньшие члены влево от опорного, а большие вправо
    do {
        while (arr[i] < mid)
            ++i;
        while (mid < arr[j])
            --j;
        if ( i <= j ) {
            if( i < j ) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
            ++i;
            --j;
        }
    } while (i <= j);

    //теперь также сортируем левую и правую часть
    if (low < j)
        quickSort(arr, low, j);
    if (i < high)
        quickSort(arr, i, high);
}

Сортировки за линейное время

Как видно из названия, сложность следующих сортировок O(n)

Сортировка подсчетом (Counting sort)

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

Достоинства: достаточно быстр

Недостатки: элементы входного массива должны быть в интервале от 0 до k, где k - натуральное число; требует выделения памяти

Алгоритм:

function counting_sort
    for i = 0 to k - 1
        C[i] = 0
    for i = 0 to n - 1
        C[A[i]] = C[A[i]] + 1
    b = 0
    for j = 0 to k - 1
        for i = 0 to C[j] - 1
            A[b] = j
            b = b + 1

Реализация на Java:

//counting sort
public static void countingSort(int[] arr, int max) {
int i, j, b = 0;
int[] c = new int[max];

//забьем вспомогательный массив нулями (его индексы соответствуют исходным значениям)
for (i = 0; i < max; i++)  c[i] = 0;

    //забьем вспомогательный массив значениями, равными количеству элементов, меньших данного значения индекса
    for (i = 0; i < arr.length; i++) {
       c[arr[i]] = c[arr[i]] + 1;
       b = 0;
    }

    //забьем на основе данных из вспомогательного массива выходной массив
    for (j = 0; j < max; j++) {
       for (i = 0; i < c[j]; i++) {
           arr[b] = j;
           b = b + 1;
       }
    }
}

Поразрядная сортировка (Radix sort)

Вариант сортировки с младших разрядов least significant digit (LSD). Сначала производится сортировка по младшему разряду, потом по следующему, и так далее, пока дело не дойдет до старшего разряда. Но существует и второй вариант - сортировка по старшему разряду (most significant digit (MSD)).

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

Алгоритм:

function radix_sort
  for i = 1 to d 
    do Устойчивая сортировка массива A по i-ой цифре

Реализация на Java:

//radix sort
public static void radixSort(int[] arr) {
int cnt[][] = new int[4][];
int b[];
int i, j;
int a_len = arr.length;

if (a_len < 2) {
        // массив длиной 1 элемент не нужно сортировать :)
        return;
    }

    // инициализируем счетчик [cnt]
    for (j = 0; j < 4; j++) {
        cnt[j] = new int[257];
        for (i = 0; i < 257; i++) cnt[j][i] = 0;
    }

    // выделяем память под копию сортируемого массива
    b = new int[a_len];

    // подсчитываем количество элементов для каждого значения j-го разряда
    for (i = 0; i < a_len; i++) {
        for (j = 0; j < 4; j++) {
            cnt[j][1 + ((arr[i] >>> (8 * j)) & 0xff)]++;
}
}

for (j = 0; j < 4; j++) {
        /*
            вычисляем позиции cnt[i], начиная с которых будут располаться элементы
            с соответствующим значением j-го разряда
        */
        for (i = 1; i < 256; i++) cnt[j][i] += cnt[j][i - 1];
        // расставляем элементы из массива a в массив b в указанном порядке
        for (i = 0; i < a_len; i++) {
            b[cnt[j][(arr[i] >>> (8 * j)) & 0xff]++] = arr[i];
}
// копируем массив b на место массива a
for (i = 0; i < a_len; i++) arr[i] = b[i];
    }
}

Блочная (карманная) сортировка (Bucket sort)

Идея, лежащая в основе алгоритма заключается в том, чтобы разбить интервал [0,1) на n одинаковых интервалов, а затем распределить по этим интервалам n входных величин. Поскольку входные элементы равномерно распределены, можно предположить, что в каждый интервал попадет не много элементов. Для получения выходной последовательности, надо провести сортировку в каждом интервале, а затем последовательно перечислить элементы в каждом из них.

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

Алгоритм:

function bucket-sort(A, n) is
  buckets ← новый массив из n пустых элементов
  for i = 0 to (length(A)-1) do
    вставить A[i] в конец массива buckets[nA[i]]
  for i = 0 to n - 1 do
    next-sort(buckets[i])
  return Конкатенация массивов buckets[0], ..., buckets[n-1]

Реализация на Java:

//bucket sort
public static void bucketSort(int[] arr) {

    //поиск максимального элемента массива
    int maxValue = arr[0];
 
    for (int k = 1; k < arr.length; k++) {
       if (arr[k] > maxValue)
           maxValue = arr[k];
    }

    int i, j;
    //создадим вспомогательный массив
    int[] bucket = new int[maxValue + 1];
    //распределим числа по карманам
    for(i = 0; i < arr.length; i++ ) {
        bucket[arr[i]]++;
    }

    //отсортируем числа в карманах используя сортировку подсчетом
    for(i = 0, j = 0; i < bucket.length; i++) {
        for(; bucket[i]>0; (bucket[i])--) {
            arr[j++] = i;
        }
    }
}

ну и напоследок выложу код для запуска всех вышеперечисленных сортировок, может кому-то он пригодится:

public class Sorting {

    public static void main(String[] args) {
        String[] types = {"insertion","merge","heap","quick", "counting", "radix", "bucket"};
        sort(types);
    }

    private static void sort(String[] types) {
        for (String type: types) {
            int[] arr = {8,4,7,2,7,0,32,17,45,43,32,4,38,4,89,3,6,7,86,3,545,6,7,2,54};
            int[] arr2 = {8,24,7,2,7,0,22,17,15,13,12,4,18,4,19,3,6,7,16,3,15,6,7,2,14};
            if (type.equals("insertion")) {
                insertionSort(arr);
            } else if (type.equals("merge")) {
                arr = mergeSort(arr);
            } else if (type.equals("heap")) {
                heapSort(arr);
            } else if (type.equals("quick")) {
                quickSort(arr, 0, arr.length -1);
            } else if (type.equals("counting")) {
                countingSort(arr, 1000);
            } else if (type.equals("radix")) {
                radixSort(arr);
            } else if (type.equals("bucket")) {
                bucketSort(arr2);
            }
    
            System.out.println("\n"+ type + "Sorted: ");
            if (!type.equals("bucket")) {
                for (int i: arr)  System.out.print(i + ",");
            } else {
                for (int i: arr2)  System.out.print(i + ",");
            }
        }
    }


   ... //here is the code of sorts
}