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

Быстрая сортировка (англ. quicksort) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Даёт в среднем O(n log n) сравнений при сортировке n элементов. В худшем случае, однако, получается O(n2) сравнений. Обычно на практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n log n), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре, и на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.

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

Содержание

Алгоритм

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

  1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом.
  2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него.
  3. Рекурсивно сортируем подсписки, лежащие слева и справа от опорного элемента.

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

Улучшения

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

Примеры реализации

C

Для массива целых чисел:

  int partition (int *a, int p, int r)
  {
    int x = a[r];
    int i = p - 1;
    int j;
    int tmp;
    for (j = p; j < r; j++)
    {
      if (a[j] <= x)
      {
        i++;
        tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
      }
    }
    tmp = a[r];
    a[r] = a[i+1];
    a[i+1] = tmp;
    return i + 1;
  }
  void quicksort (int *a, int p, int r)
  {
    int q;
    if (p < r)
    {
      q = partition (a, p, r);
      quicksort (a, p, q-1);
      quicksort (a, q+1, r);
    }
  }

C++

Быстрая сортировка на основе библиотеки STL.

#include <functional>
#include <algorithm>
#include <iterator>

template< typename BidirectionalIterator, typename Compare >
void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp ) {
  if( first != last ) {
    BidirectionalIterator left  = first;
    BidirectionalIterator right = last;
    BidirectionalIterator pivot = left++;

    while( left != right ) {
      if( cmp( *left, *pivot ) ) {
         ++left;
      } else {
         while( (left != --right) && cmp( *pivot, *right ) )
           ;
         std::iter_swap( left, right );
      }
    }

    --left;
    std::iter_swap( first, left );

    quick_sort( first, left, cmp );
    quick_sort( right, last, cmp );
  }
}

template< typename BidirectionalIterator >
inline void quick_sort( BidirectionalIterator first, BidirectionalIterator last ) {
  quick_sort( first, last,
    std::less_equal< typename std::iterator_traits< BidirectionalIterator >::value_type >()
  );
}

Java

import java.util.Comparator;
import java.util.Random;

public class Quicksort {
    public static final Random RND = new Random();

    private void swap(Object array, int i, int j) {
        Object tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    private int partition(Object array, int begin, int end, Comparator cmp) {
        int index = begin + RND.nextInt(end — begin + 1);
        Object pivot = array[index];
        swap(array, index, end);        
        for (int i = index = begin; i < end; ++ i) {
            if (cmp.compare(array[i], pivot) <= 0) {
                swap(array, index++, i);
            }
        }
        swap(array, index, end);        
        return (index);
    }

    private void qsort(Object array, int begin, int end, Comparator cmp) {
        if (end > begin) {
            int index = partition(array, begin, end, cmp);
            qsort(array, begin, index - 1, cmp);
            qsort(array, index + 1,  end,  cmp);
        }
    }

    public void sort(Object array, Comparator cmp) {
        qsort(array, 0, array.length - 1, cmp);
    }
}

Глагол

 ЗАДАЧА Упоряд-(ряд+:РЯД ИЗ Доступ; всего:ЦЕЛ; сравнить:ЗАДАЧА(с1-,с2-:Вид):ЦЕЛ);
 ПЕР
   Л,П:ЦЕЛ;        (* текущий участок                   *)
   л,п:ЦЕЛ;        (* новый участок                     *)
   граница:Доступ; (* граничное значение для разделение *)
   рядл:Доступ;    (* промежуточное значение для обмена *)
   глубина:ЦЕЛ;    (* текущая глубина стека             *)
   (* стек для новых участков *)
   стек:РЯД 32 ИЗ НАБОР Л,П:ЦЕЛ КОН; 
 УКАЗ
   глубина:=0; 
   стек[глубина].Л:=0; 
   стек[глубина].П:=всего-1;
   ПОВТОРЯТЬ
     (* выбор из стека последнего запроса *)
     Л:=стек[глубина].Л; 
     П:=стек[глубина].П;
     УМЕНЬШИТЬ(глубина);
     ПОВТОРЯТЬ
       (* разделение ряд[Л]...ряд[П] *)
       л:=Л; п:=П;
       граница:=ряд[(Л+П) ДЕЛИТЬ 2];
       ПОВТОРЯТЬ
         ПОКА сравнить(ряд[л]^,граница^) < 0 ВЫП УВЕЛИЧИТЬ(л) КОН;
         ПОКА сравнить(граница^,ряд[п]^) < 0 ВЫП УМЕНЬШИТЬ(п) КОН;
         ЕСЛИ л <= п ТО (* обмен ряд[л] с ряд[п] *)
           рядл:=ряд[л];
           ряд[л]:=ряд[п];
           ряд[п]:=рядл;
           УВЕЛИЧИТЬ(л);
           УМЕНЬШИТЬ(п)
         КОН
       ДО л > п;
       ЕСЛИ п-Л < П-л ТО
         ЕСЛИ л < П ТО (* запись в стек запроса на упорядочивание правой части *)
           УВЕЛИЧИТЬ(глубина);
           стек[глубина].Л:=л;
           стек[глубина].П:=П
         КОН;
         П:=п (* продолжение упорядочивания левой части *)
       ИНАЧЕ
         ЕСЛИ Л < п ТО (* запись в стек запроса на упорядочивание левой части *)
           УВЕЛИЧИТЬ(глубина);
           стек[глубина].Л:=Л;
           стек[глубина].П:=п
         КОН;
         Л:=л (* продолжение упорядочивания правой части *)
       КОН
     ДО Л >= П
   ДО глубина < 0
 КОН Упоряд;

Python

def qsort(L):
   if L == : return 
   return qsort([x for x in L[1:] if x< L[0]]) + L[0:1] + \
          qsort([x for x in L[1:] if x>=L[0]])

Joy

DEFINE sort == [small]
               [uncons [>] split]
               [[swap] dip cons concat] binrec .

PHP

function qsort($s) {
 for($i=0, $x=$y=array(); $i<count($s)-1; $s[++$i]<=$s[0] ? $x=$s[$i] : $y=$s[$i]);
 return count($s)<=1 ? $s : array_merge(qsort($x), array($s[0]), qsort($y));
}

Haskell

 sort :: (Ord a)   => [a] -> [a]
 
 sort            = 
 sort (pivot:rest) = sort [y | y <- rest, y < pivot]
                     ++ [pivot] ++ 
                     sort [y | y <- rest, y >=pivot]

Prolog

split(H, [A|X], [A|Y], Z) :-
  order(A, H), split(H, X, Y, Z).
split(H, [A|X], Y, [A|Z]) :-
  not(order(A, H)), split(H, X, Y, Z).
split(_, , , ).

quicksort(, X, X).

quicksort([H|T], S, X) :-
  split(H, T, A, B),
  quicksort(A, S, [H|Y]),
  quicksort(B, Y, X).

Ruby

def sort(array)
  return  if array.empty?
  left, right = array[1..-1].partition { |y| y <= array.first }
  sort(left) + [ array.first ] + sort(right)
end

SML

This example demonstrates the use of an arbitrary predicate in a functional language.

fun quicksort lt lst =
  let val rec sort =
    fn  => 
     | (x::xs) =>
        let
          val (left,right) = List.partition (fn y => lt (y, x)) xs
        in sort left @ x :: sort right
        end
  in sort lst
end

JavaScript

function QuickSort(A, p, r)
{
        if(p<r)
        {
                var q = Partition(A, p, r);
                QuickSort(A, p, q);
                QuickSort(A, q+1, r);
        }
}
function Partition(A, p, r)
{
        var x = A[r];
        var i=p-1;
        for(var j=p; j<=r ;j++ )
        {
                if(A[j] <= x)
                {
                        i++;
                        var temp = A[i];
                        A[i] = A[j];
                        A[j] = temp;
                }
        }
        return i<r ?i : i-1;
}

TCL

 # Функция выбирает подсписок из списка используя условие condition
 proc lfind {data arg condition} {
   set foo [list]
   foreach item $data {
     set $arg $item
     if {[expr $condition]} {lappend foo $item}
   }
   return $foo
 }
 
 # Сама сотрировка
 proc QSort data {
   set result {}
   if {[llength $data] != 0} {
     set check [lindex $data 0] 
     set result [
       concat \
         [QSort [lfind $data argument "\$argument < $check"]] \
         [list $check] \
         [QSort [lfind $data argument "\$argument > $check"]]]
   }
   return $result
 }
 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home