Перейти к содержанию

Реализации алгоритмов/Сортировка/Быстрая

Материал из Викиучебника — открытых книг для открытого мира

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

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

Работает для произвольного массива из n целых чисел.

Sub QSort(ByRef arr As Variant, ByVal iLbound As Integer, iUbound As Integer)
    Dim iL As Integer, iU As Integer
    Dim iVal As Integer, iSwap As Integer
    iL = iLbound:    iU = iUbound
    iVal = arr((iLbound + iUbound) \ 2)
    Do While iL <= iU
       Do While arr(iL) < iVal And iL < iUbound
          iL = iL + 1
       Loop
       Do While iVal < arr(iU) And iU > iLbound
          iU = iU - 1
       Loop
       If iL <= iU Then
          iSwap = arr(iL)
          arr(iL) = arr(iU)
          arr(iU) = iSwap
          iL = iL + 1
          iU = iU - 1
       End If
    Loop
     
    If iLbound < iU Then
        Call QSort(arr, iLbound, iU)
    End If
    If iL < iUbound Then
        Call QSort(arr, iL, iUbound)
    End If
End Sub
   int Partition(int[] array, int start, int end) 
   {
       int marker = start; // divides left and right subarrays
       for (int i = start; i < end; i++) 
       {
           if (array[i] < array[end]) // array[end] is pivot
           {
               (array[marker], array[i]) = (array[i], array[marker]);
               marker += 1;
           }
       }
       // put pivot(array[end]) between left and right subarrays
       (array[marker], array[end]) = (array[end], array[marker]);
       return marker;
   }

   void Quicksort(int[] array, int start, int end)
   {
       if (start >= end) 
           return;

       int pivot = Partition (array, start, end);
       Quicksort(array, start, pivot - 1);
       Quicksort(array, pivot + 1, end);
   }

Работает для произвольного массива из n целых чисел.

int n, a[n]; //n - количество элементов
void qs(int *s_arr, int first, int last)
{
    if (first < last)
    {
        int left = first, right = last, middle = s_arr[(left + right) / 2];
        do
        {
            while (s_arr[left] < middle) left++;
            while (s_arr[right] > middle) right--;
            if (left <= right)
            {
                int tmp = s_arr[left];
                s_arr[left] = s_arr[right];
                s_arr[right] = tmp;
                left++;
                right--;
            }
        } while (left <= right);
        qs(s_arr, first, right);
        qs(s_arr, left, last);
    }
}

Исходный вызов функции qs для массива из n элементов будет иметь следующий вид.

qs(a, 0, n-1);
   int partition (int[] array, int start, int end) 
   {
       int temp;//swap helper
       int marker = start;//divides left and right subarrays
       for ( int i = start; i < end; i++ ) 
       {
           if ( array[i] < array[end] ) //array[end] is pivot
           {
               temp = array[marker]; // swap
               array[marker] = array[i];
               array[i] = temp;
               marker += 1;
           }
       }
       //put pivot(array[end]) between left and right subarrays
       temp = array[marker];
       array[marker] = array[end];
       array[end] = temp; 
       return marker;
   }

   void quicksort (int[] array, int start, int end)
   {
       if ( start >= end ) 
       {
           return;
       }
       int pivot = partition (array, start, end);
       quicksort (array, start, pivot-1);
       quicksort (array, pivot+1, end);
   }

C# с обобщёнными типами

[править]

Тип Т должен реализовывать интерфейс IComparable<T>.

static int partition<T>( T[] m, int a, int b)
where T : IComparable<T>
{
    int i = a;
    for (int j = a; j < b; j++)         // просматриваем с a по b
    {
        if (m[j].CompareTo( m[b]) <= 0)  // если элемент m[j] не превосходит m[b],
        {
            T t = m[i];                  // меняем местами m[j] и m[a], m[a+1], m[a+2] и так далее...
            m[i] = m[j];                 // то есть переносим элементы меньшие m[b] в начало,
            m[j] = t;                    // а затем и сам m[b] «сверху»
            i++;                         // таким образом последний обмен: m[b] и m[i], после чего i++
        }
    }
    return i - 1;                        // в индексе i хранится <новая позиция элемента m[b]> + 1
}

static void quicksort<T>( T[] m, int a, int b) where T : IComparable<T>// a - начало подмножества, b - конец
{                                        // для первого вызова: a = 0, b = <элементов в массиве> - 1
    if (a >= b) return;
    int c = partition( m, a, b);
    quicksort( m, a, c - 1);
    quicksort( m, c + 1, b);
}

//Пример вызова
//double[] arr = {9,1.5,34.4,234,1,56.5};
//quicksort<double>(arr,0,arr.Length-1);
//

C# с использованием лямбда-выражений

[править]
using System;
using System.Collections.Generic;
using System.Linq;

static public class Qsort
    {
        public static IEnumerable<T> QuickSort<T>(this IEnumerable<T> list) where T : IComparable<T>
        {
            if (!list.Any())
            {
                return Enumerable.Empty<T>();
            }
            var pivot = list.First();
            var smaller = list.Skip(1).Where(item => item.CompareTo(pivot) <= 0).QuickSort();
            var larger = list.Skip(1).Where(item => item.CompareTo(pivot) > 0).QuickSort();

            return smaller.Concat(new[] { pivot }).Concat(larger);
        }

//(тоже самое, но записанное в одну строку, без объявления переменных)

        public static IEnumerable<T> shortQuickSort<T>(this IEnumerable<T> list) where T : IComparable<T>
        {
            return !list.Any() ? Enumerable.Empty<T>() : list.Skip(1).Where(
                item => item.CompareTo(list.First()) <= 0).shortQuickSort().Concat(new[] { list.First() })
                    .Concat(list.Skip(1).Where(item => item.CompareTo(list.First()) > 0).shortQuickSort());
        }
    }

Быстрая сортировка на основе библиотеки 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 >()
   );
}

Для вещественных чисел

[править]
int partition (double *a, int p, int r)
{
    double x = *(a+r);
    int i = p - 1;
    int j;
    double 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 (double *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);
    }
 }
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);
    }

Java с инициализацией и перемешиванием массива

[править]

и с измерением времени сортировки массива нанотаймером (работает только если нет совпадающих элементов массива).

import java.util.Random;

public class QuickSort
{
    public static void main(String[] args)
    {
       int N = 10;
       int[] A = new int[N + 1];

       // заполнение массива
       for (int i = 0; i <= N; i++)
       {
          A[i] = N - i;
          System.out.print(A[i] + " ");
       }
       System.out.println("\nBefore qSort\n");

       // перемешивание массива
       Random r = new Random (); //инициализация от таймера
       int yd, xs;
       for (int i = 0; i <= N; i++)
       {
          yd=A[i];
          xs=r.nextInt(N + 1);
          A[i]=A[xs];
          A[xs]=yd;
       }

       for (int i = 0; i <= N; i++) System.out.print(A[i]+" ");
       System.out.println("\nAfter randomization\n");

       long start, end;
       int low = 0;
       int high = N;

       start=System.nanoTime();   // получить начальное время
       qSort(A, low, high);
       end=System.nanoTime();    // получить конечное время

       for (int i = 0; i <= N; i++) System.out.print(A[i] + " ");
       System.out.println("\nAfter qSort");
       System.out.println("\nTime of running: " + (end - start) + "nanosec");
    }
   //описание функции qSort
   public static void qSort(int[] A, int low, int high)
   {
      int i = low;
      int j = high;
      int x = A[low + (high - low) / 2];
      do
      {
         while(A[i] < x) i++;
         while(A[j] > x) j--;
         if(i <= j)
         {
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
            i++; j--;
         }
      }
      while(i <= j);

      //рекурсивные вызовы функции qSort
      if (low <  j) qSort(A, low,  j);
      if (i < high) qSort(A, i, high);
  }
}

Java без рекурсии, с использованием стека

[править]

пошаговый алгоритм с возможностью вывода на экран текущего действия

import java.awt.Color;
import java.awt.Graphics;
import java.util.Arrays;
import java.util.Stack;

class ArrRange
{
  // структура для хранения индексов границ массива
	public int low, high;
	public ArrRange(int from, int to)
	{
		this.low  = from;
		this.high = to;
	}
}

public class QuickSorter
{
	// Задаем размер массива
	final static int size = 10;
	
	// Объявляем массив
	int[] a;
	
	// Стек для хранения индексов начала и конца массива
	Stack<ArrRange> stack;

	QuickSorter ()
	{
		a = new int[size];
		for (int i = 0; i < size; i++) a[i] = (int) (Math.random() * 100);
		stack = new Stack<ArrRange>();
		stack.push(new ArrRange(0, a.length - 1));
	}

	int step = -1;              // текущий шаг
	int drawStep = -1;          // текущий шаг для вывода сообщения
	int temp1 = -1, temp2 = -1; // текущие переставляемые элементы
	int middle = -1;            // середина массива
	int opora;                  // опорный элемент
	int i, j;
	ArrRange range;
	

	public void NextStep()
	{
		switch (step)
		{
			case -1: range = stack.pop(); step = 0; break;
			// находим опорный элемент
			case 0:
				middle = (range.low + range.high) >> 1; opora = a[middle];
				i = range.low; j = range.high;
				step = 1;
				break;
			// ишем слева элемент больше опорного
			case 1:
				while (a[i] < opora) i++;
				temp1 = a[i];
				step = 2;	
				break;		
			// ишем справа элемент меньше опорного
			case 2:
				while (a[j] > opora) j--;
				temp2 = a[j];
				step = 3;
				break;
			// меняем местами
			case 3:
				if (i <= j)
				{
	        int temp = a[i]; a[i] = a[j]; a[j] = temp;
	        i++;
	        j--;
	      }
				step = i <= j ? 1 : 4;
				break;
			// разделить массив на 2 части
			case 4:
				if(i < middle)
				{
				  /*
				    правая часть больше:
				    если в ней больше 1 элемента - нужно сортировать, отправляем в стек
				    следующая итерация разделения будет работать с левой частью
				  */
					if (i < range.high) stack.push (new ArrRange(i, range.high));
					range.high = j;
				}
				else
				{
				  /*
				    левая часть больше:
				    следующая итерация разделения будет работать с правой частью
				  */
					if (j > range.low) stack.push(new ArrRange(range.low, j));
					range.low = i;
				}
				step = (range.low < range.high) ? 0 : (stack.size() > 0) ? -1 : 5;
				break;
		}
	}
	
	public void draw (Graphics g)
	{
		int h = 30, w = 30, l = 50;
		for (int i = 0; i < size; i++)
		{
			g.setColor(new Color(0, 0, 0));
			g.clearRect(l + i * h, 100, w, h);
			g.drawRect (l + i * h, 100, w, h);
			g.drawString(a[i] + "", l + i * h + 7, 105 + h / 2);
		}

		g.setColor(new Color(0, 0, 0));
		g.drawString("temp1: " + temp1, l, 160);
		g.drawString("temp2: " + temp2, l, 180);
		g.drawString("opora: " + opora, l, 200);
		String s = "";
		switch (drawStep)
		{
		  case -1: s = "начинаем сортировку";                 break;
		  case  0: s = "находим опорный элемент";             break;
		  case  1: s = "ишем слева элемент больше опорного";  break;
		  case  2: s = "ишем справа элемент меньше опорного"; break;
		  case  3: s = "меняем местами";                      break;
		  case  4: s = "разделяем массив на 2 части";         break;
		  case  5: s = "закончили сортировку";                break;
		}
		g.drawString("Действие: " + s, l, 50);
		drawStep = step;
	}
}
/*
 * Алгоритм быстрой сортировки
 *
 * @param data Array
 * @param compare function(a, b) - возвращает 0 если a=b, -1 если a<b и 1 если a>b (необязательная)
 * @param change function(a, i, j) - меняет местами i-й и j-й элементы массива а (необязательная)
 *
 */
const qsort = (data, compare, change) => {
    let a = data,
        f_compare = compare,
        f_change  = change;

    if (!(a instanceof Array)) { // Данные не являются массивом
        return undefined;
    };
    if (f_compare === undefined) { // Будем использовать простую функцию (для чисел)
        f_compare = (a, b) => {
           if (a === b) {
               return 0;
           } else if (a > b) {
               return 1;
           } else {
               return -1;
           }
       }
    };
    if (f_change === undefined) { // Будем использовать простую смену (для чисел)
        f_change = (a, i, j) => {
        const temp = a[i];
        a[i] = a[j];
        a[j] = temp;
        }
    };

    const qs = (l, r) => {
        let i = l,
            j = r,
            x = a[l+r>>1];
            //x = a[Math.floor(Math.random()*(r-l+1))+l];
            // x = a[l]; // Если нет желания использовать объект Math

        while (i <= j) {
            while (f_compare(a[i], x) === -1) {
                i++;
            }
            while (f_compare(a[j], x) === 1) {
                j--;
            }
            if (i <= j) {
                f_change(a, i++, j--);
            }
        }
        if (l < j) {
            qs(l, j);
        }
        if (i < r) {
            qs(i, r);
        }
    }
    qs(0, a.length - 1);
}
 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;
 }

Через list comprehension:

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

Математическая версия:

 def qsort(L):
    if L: return qsort(filter(lambda x: x < L[0], L[1:])) + L[0:1] + qsort(filter(lambda x: x >= L[0], L[1:]))
    return []
DEFINE sort == [small][]
               [uncons [>] split]
               [[swap] dip cons concat] binrec .
/*
* Функция, непосредственно производящая сортировку.
* Так как массив передается по ссылке, ничего не возвращает.
*/

function custom_sort(&$array, $left, $right) {

  //Создаем копии пришедших переменных, с которыми будем манипулировать в дальнейшем.
  $l = $left;
  $r = $right;
  
  //Вычисляем 'центр', на который будем опираться. Берем значение ~центральной ячейки массива.
  $center = $array[(int)($left + $right) / 2];
  
  //Цикл, начинающий саму сортировку
  do {
  
    //Ищем значения больше 'центра'
    while ($array[$r] > $center) { 
      $r--;
    }
    
    //Ищем значения меньше 'центра'
    while ($array[$l] < $center) { 
      $l++;
    }
  
    //После прохода циклов проверяем счетчики циклов
    if ($l <= $r) {
    
      //И если условие true, то меняем ячейки друг с другом.
       if ($array[$l] > $array[$r])   list($array[$r], $array[$l]) = array($array[$l], $array[$r]);
      
      //И переводим счетчики на следующий элементы
      $l++;
      $r--;
    }
  
  //Повторяем цикл, если true
  } while ($l <= $r);
  
  if ($r > $left) {
    //Если условие true, совершаем рекурсию
    //Передаем массив, исходное начало и текущий конец
    custom_sort($array, $left, $r); 
  }
  
  if ($l < $right) {
    //Если условие true, совершаем рекурсию
    //Передаем массив, текущие начало и конец
    custom_sort($array, $l, $right);
  }

//Сортировка завершена

}
function quicksort ($array, $l=0, $r=0) {
    if($r === 0) $r = count($array)-1;
    $i = $l;
    $j = $r;
    $x = $array[($l + $r) / 2];
    do {
        while ($array[$i] < $x) $i++;
        while ($array[$j] > $x) $j--;
        if ($i <= $j) {
            if ($array[$i] > $array[$j])
                list($array[$i], $array[$j]) = array($array[$j], $array[$i]);
            $i++;
            $j--;
        }
    } while ($i <= $j);
    if ($i < $r) quicksort ($array, $i, $r);
    if ($j > $l) quicksort ($array, $l, $j);
}
  qsort []     = []
  qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Математическая версия — с использованием генераторов:

  qsort [] = []
  qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]

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

В отличие от других вариантов реализации на функциональных языках, представленных здесь, приводимая реализация алгоритма на Лиспе является "честной" - она не порождает новый отсортированный массив, а сортирует тот, который поступил ей на вход, "на том же месте". При первом вызове функции в параметры l и r необходимо передать нижний и верхний индексы массива (или той его части, которую требуется отсортировать). Код использует "императивные" макросы Common Lisp'а.

(defun quickSort (array l r)
    (let ((i l)
          (j r)
          (p (svref array (round (+ l r) 2))))
        (while (<= i j)
            (while (< (svref array i) p) (incf i))
            (while (> (svref array j) p) (decf j))
            (when (<= i j)
                (rotatef (svref array i) (svref array j))
                (incf i)
                (decf j)))
        (if (>= (- j l) 1) (quickSort array l j))
        (if (>= (- r i) 1) (quickSort array i r)))
    array)

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

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

const max=20; { можно и больше... }
type
  list = array[1..max] of integer;

procedure quicksort(var a: list; );

  procedure sort(l,r: integer);
  var
    i,j,x,y: integer;
  begin
    i:=l; j:=r; x:=a[l+random(r-l+1)]; { x := a[(l + r) div 2]; - для выбора среднего элемента }
    repeat
      while a[i]<x do i:=i+1; { a[i] > x  - сортировка по убыванию}
      while x<a[j] do j:=j-1; { x > a[j]  - сортировка по убыванию}
      if i<=j then
      begin
        if a[i] > a[j] then {это условие можно убрать} {a[i] < a[j] при сортировке по убыванию}
        begin
          y:=a[i]; a[i]:=a[j]; a[j]:=y;
        end;
        i:=i+1; j:=j-1;
      end;
    until i>=j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
  end; {sort}

begin {quicksort};
  randomize; {нужно только если используется выборка случайного опорного элемента}
  sort(Lo,Hi)
end; {quicksort}

Устойчивый вариант (требует дополнительно O(n)памяти)

const max=20; { можно и больше… }
type
  list = array[1..max] of integer;

procedure quicksort(var a: list; );

var 
  num: array[1..max] of integer; { дополнительный массив для хранения индексов }

  procedure sort(l,r: integer);
  var
    i,j,x,xval,xvaln,y: integer;
  begin
    i:=l; j:=r; x:=random(r-l+1)+l; xval:=a[x]; xvaln:=num[x];{ x := l+(r-l)div 2; - для выбора среднего элемента }
    repeat
      while (a[i]<xval)or((a[i]=xval)and(num[i]<xvaln)) do i:=i+1; {> - сортировка по убыванию}
      while (xval<a[j])or((a[j]=xval)and(xvaln<num[j])) do j:=j-1; {> - сортировка по убыванию}
      if i<=j then
      begin
        y:=a[i]; a[i]:=a[j]; a[j]:=y;
        y:=num[i]; num[i]:=num[j]; num[j]:=y;
        i:=i+1; j:=j-1
      end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r)
  end; {sort}

begin {quicksort}
  randomize; {нужно только если используется выборка случайного опорного элемента}
  for i:=1 to n do
    num[i]:=i;
  sort(Lo,Hi)
end; {quicksort}

Быстрая сортировка, нерекурсивный вариант

[править]

Нерекурсивная реализация быстрой сортировки через управляемый вручную стек. Функции compare и change реализуются в зависимости от типа данных.

procedure quickSort(var X: itemArray; n: integer);
type
  p_node = ^node;
  node = record
           node: integer;
           next: p_node
         end;
var
  l,r,i,j: integer;
  stack: p_node;
  temp: item;

  procedure push(i: integer);
  var
    temp: p_node;
  begin
    new(temp);
    temp^.node:=i;
    temp^.next:=stack;
    stack:=temp
  end;

  function pop: integer;
  var
    temp: p_node;
  begin
    if stack=nil then
      pop:=0
    else
    begin
      temp:=stack;
      pop:=stack^.node;
      stack:=stack^.next;
      dispose(temp)
    end
  end;

begin
  stack:=nil;
  push(n-1);
  push(0);
  repeat
    l:=pop;
    r:=pop;
    if r-l=1 then
    begin
      if compare(X[l],X[r]) then
        change(X[l],X[r])
    end
    else
    begin
      temp:=x[l + (r-l) div 2]; {random(r-l+1)+l}
      i:=l;
      j:=r;
      repeat
        while compare(temp,X[i]) do i:=i+1;
        while compare(X[j],temp) do j:=j-1;
        if i<=j then
        begin
          change(X[i],X[j]);
          i:=i+1;
          j:=j-1
        end;
      until i>j;
      if l<j then
      begin
        push(j);
        push(l)
      end;
      if i<r then
      begin
        push(r);
        push(i)
      end
    end;
  until stack=nil
end;

Частично рекурсивная реализация

[править]

Реализация на языке pascal с одной рекурсивной ветвью. После разделения массива меньшая часть сортируется рекурсивным вызовом, а бо’льшая — в цикле. Это гарантирует глубину рекурсии не более lg(N).

procedure qSort(var ar: array of real;);
  procedure sort(var ar: array of real; low, high: integer);
  var i, j: integer;
      m, wsp: real;
  begin
    repeat
      i:=low; j:=high; m:=ar[(i+j) div 2]; // Взятие среднего опорного элемента
      repeat
        while ar[i]<m do Inc(i); 
        while ar[j]>m do Dec(j); 
        if i<=j then begin
          wsp:=ar[i]; ar[i]:=ar[j]; ar[j]:=wsp;
          Inc(i); Dec(j);
         end;
      until i>j;
      if (j - low) < (high - i) then begin // Сравнение размеров выделенных подмассивов
        if low < j then qSort(ar, low, j); // Если первый подмассив меньше - он сортируется рекурсивно,
        low := i;                          // а для следующего прохода цикла выбирается второй подмассив.
        end 
      else begin // в противном случае всё наоборот
        if i < high then qSort(ar, i, high); // Рекурсивно сортируется второй подмассив,
        high := j;                           // а в следующем проходе цикла - первый.
      end; 
    until low = high;
  end;
begin
  sort(ar, 0, High(ar));
end;

Пример реализации алгоритма в объектно-ориентированном стиле с обобщением по типу данных (Generics)

[править]

В представленной реализации алгоритма быстрой сортировки элементов массива порядок сортировки определяется пользовательской функцией обратного вызова:

function Comparer(const Left, Right: T): Integer,

которая должна удовлетворять условиям контракта вызова и возвращаемого значения:

  • < 0, если Left < Right;
  • = 0, если Left = Right;
  • > 0, если Left > Right.

Библиотечный модуль

[править]
unit VectorT;

interface

type
  TVector<T> = record
  public type
    TComparer = function (const Left, Right: T): Integer;
  private
    procedure Sort(Comparer: TComparer; Left, Right: Integer); overload;
    procedure Swap(One, Two: Integer);
  public
    Items: TArray<T>;
    procedure Sort(Comparer: TComparer); overload;
  end;

implementation

procedure TVector<T>.Sort(Comparer: TComparer);
var
  Count: Integer;
begin
  Count := Length(Items);
  if Count > 1 then
    Sort(Comparer, 0, Count - 1)
end;

procedure TVector<T>.Sort(Comparer: TComparer; Left, Right: Integer);
var
  Delta: Integer;
  Minor: Integer;
  Major: Integer;
  Basis: T;
begin
  Delta := (Right - Left) div 2;
  if Delta = 0 then
    begin
      if Comparer(Items[Right], Items[Left]) < 0 then
        Swap(Left, Right);
      Exit
    end;
  Minor := Left;
  Major := Right;
  Basis := Items[Left + Delta];
  repeat
    while Comparer(Items[Minor], Basis) < 0 do
      Inc(Minor);
    while Comparer(Basis, Items[Major]) < 0 do
      Dec(Major);
    if Minor >= Major then
      Break;
    if Comparer(Items[Major], Items[Minor]) < 0 then
      Swap(Minor, Major);
    Inc(Minor);
    Dec(Major)
  until Minor >= Major;
  if Left < Major then
    Sort(Comparer, Left, Major);
  if Minor < Right then
    Sort(Comparer, Minor, Right)
end;

procedure TVector<T>.Swap(One, Two: Integer);
var
  Item: T;
begin
  Item := Items[One];
  Items[One] := Items[Two];
  Items[Two] := Item
end;

end.

Пример использования

[править]
program QuickSort_Demo;

{$APPTYPE CONSOLE}
{$R *.res}

uses
  VectorT in 'VectorT.pas';

procedure ShowArray(const Caption: string; const Items: TArray<Integer>);
var
  Index: Integer;
begin
  WriteLn(Caption);
  for Index := Low(Items) to High(Items) do
    WriteLn('Items[', Index, '] = ', Items[Index])
end;

type
  TSortOrder = record
  public
    class function Ascending(const Left, Right: Integer): Integer; static;
    class function Descending(const Left, Right: Integer): Integer; static;
  end;

class function TSortOrder.Ascending(const Left, Right: Integer): Integer;
begin
  // Order: Left < Right
  Result := Left - Right
end;

class function TSortOrder.Descending(const Left, Right: Integer): Integer;
begin
  // Order: Right < Left
  Result := Right - Left
end;

var
  Vector: TVector<Integer> = (Items: [5, 3, 7, 11, 9]);

begin
  ShowArray('Initial array:', Vector.Items);
  Vector.Sort(TSortOrder.Ascending);
  ShowArray('Sorted ascending:', Vector.Items);
  Vector.Sort(TSortOrder.Descending);
  ShowArray('Sorted descending:', Vector.Items);
  Write('Press [Enter] key to exit ...');
  ReadLn
end.
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).
def sort(array)
  return [] if array.empty?
  left, right = array[1..-1].partition { |y| y <= array.first }
  sort(left) + [ array.first ] + sort(right)
end

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
 # Функция выбирает подсписок из списка используя условие 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
 }
@out=(5,2,7,9,2,5,67,1,5,7,-8,5,0);
sub sortQ{
    my($s, $e) = @_;
    my $m = $s - 1;
    for($s..$e - 1){
	if($out[$_] lt $out[$e]){
	    ++$m;
	    ($out[$m], $out[$_]) = ($out[$_], $out[$m]);
	}
    }
    ++$m;
    ($out[$m], $out[$e]) = ($out[$e], $out[$m]);
    sortQ($s, $m-1) if $s < $m-1;
    sortQ($m+1, $e) if $m+1 < $e;
}
sortQ(0, $#out);
let rec quicksort = function
    [] -> []
    | h::t -> quicksort ([ for x in List.filter(fun z -> z<=h)  t -> x])
              @ [h] @ quicksort ([ for x in List.filter(fun z -> z>h)  t -> x])

let list1 = [2; 34; 56; 12; 1; 5; 100; 450; 788 ]

let res = quicksort list1
 let rec qsort l=match l with
                    []->[]
                   |a::b-> (qsort (List.filter ((>=) a) b) lt) @  [a]  @  (qsort (List.filter ((<) a) b ));;
qsort([]) -> [];
qsort([H|T]) -> qsort([X || X <- T, X < H]) ++ [H] ++ qsort([X || X <- T, X >= H]).
array qsort(array)(array _a)
{
    alias typeof(array.init[0]) _type;

    array filter(bool delegate(_type) dg, array a){
        array buffer = null;
            foreach(value; a) {

                if(dg(value)){
                    buffer ~= value;
                }
            }
        return buffer;
    }

    if(_a.length <= 1) {
        return _a;
    }
    else {
        return qsort( filter((_type e){ return _a[0] >= e; }, _a[1 .. $] ) ) ~ _a[0] ~
               qsort( filter((_type e){ return _a[0] <  e; }, _a[1 .. $] ) );
    }

}

Более короткий вариант с использованием стандартной библиотеки Phobos:

import std.algorithm;

T _qsort3(T)(T a) {
    if( a.length <= 1 )
        return a;
    else
        return _qsort3( a[1..$].filter!( e => a[0] >= e ).array ) ~ a[0] ~
               _qsort3( a[1..$].filter!( e => a[0] <  e ).array );
}


#[allow(non_camel_case_types)]
type tupe=i64;
fn quicksort(a:&mut Vec<tupe>)
{
	if a.len()<=1
	{return ();}
	let mut amin=Vec::new();
	let mut amax=Vec::new();
	for _i in &a[1..]
	{
		if *_i>a[0]
		{
			amax.push(*_i);
		}
		else
		{
			amin.push(*_i);
		}
	}
	quicksort(&mut amin);
	quicksort(&mut amax);
	amin.push(a[0]);
	amin.extend(amax);
	for (_num, _i) in amin.iter().enumerate()
	{
		a[_num]=*_i;
	}
}

fn quicksort1(s_arr:&mut [tupe])
{
	let last = s_arr.len()-1;
	if 0 < last
	{
		let mut left = 0;
		let mut right = last;
		let middle = s_arr[ last / 2];
		loop
		{
			while s_arr[left] < middle {left+=1};
			while s_arr[right] > middle {right-=1};
			if left < right
			{
				let tmp = s_arr[left];
				s_arr[left] = s_arr[right];
				s_arr[right] = tmp;
				left+=1;
				right-=1;
			}
			else {break;}
		}
		right-=1;
		left+=1;
		
		quicksort1(&mut s_arr[0..=right]);
		quicksort1(&mut s_arr[left..=last]);
	}
}

fn main()
{
	let listfir = vec![10,29,14,4,35,6];
	let mut list = listfir.clone();
	println!("{:?}", list);
	quicksort(&mut list);
	println!("{:?}", list);
	
	let mut list = listfir.clone();
	println!("{:?}", list);
	quicksort1(&mut list[..]);
	println!("{:?}", list);

}
def qsort(xs: List[Int]): List[Int] = xs match {
  case head :: tail =>
  	val left = tail.filter(_ < head)
  	val right = tail.filter(_ >= head)
  	qsort(left) ++ List(head) ++ qsort(right)
  case Nil => Nil
}

Реализация с применением дженериков для типов данных, реализующих трейт Ordering:

def qSort[T](list: List[T])(implicit ord: Ordering[T]): List[T] = {
    import ord._
    if(list.isEmpty) Nil
    else {
      val head :: tail = list
      val (left, right) = tail.partition(_ <= head)
      qSort(left) ::: head :: qSort(right)
    }
  }

Ленивая реализация:

  (defn qsort [[x & xs]]
    (letfn [(f [g] (qsort (filter #(g % x) xs)))]
      (when x (lazy-cat (f <) [x] (f >=)))))

Shen/Qi II

[править]
(define filter
  {(A --> boolean) --> (list A) --> (list A)}
  _   []      -> []
  T?  [A | B]  -> (append [A] (filter T? B)) where (T? A)
  T?  [_|B]    -> (filter T? B)
)

(define q-sort
  {(list number) --> (list number)}
  [] -> []
  [A | B] -> (append (q-sort (filter (> A) [A|B]))
                     [A]
                     (q-sort (filter (< A) [A|B]))))

Судя по тестам, сортировка пузырьком 5000 занимает в 8 с половиной раз больше времени, чем qSort'ом

    Sub Swap(ByRef Val1, ByRef Val2)
        Dim Proc
        Proc = Val1
        Val1 = Val2
        Val2 = Proc
    End Sub

    Function partition(ByRef a() As Integer, ByVal left As Integer, ByVal right As Integer, ByRef pivot As Integer)
        Dim i
        Dim piv
        Dim store
        piv = a(pivot)
        Swap(a(right - 1), a(pivot))
        store = left
        For i = left To right - 2
            If a(i) <= piv Then
                Swap(a(store), a(i))
                store = store + 1
            End If
        Next
        Swap(a(right - 1), a(store))

        Return store
    End Function

    Function getpivot(ByRef a() As Integer, ByVal left As Integer, ByVal right As Integer)
        Return New System.Random().Next(left, right - 1)
    End Function

    Sub quicksort(ByRef a() As Integer, ByVal left As Integer, ByVal right As Integer)
        Dim pivot As Integer
        If right - left > 1 Then
            pivot = getpivot(a, left, right)
            pivot = partition(a, left, right, pivot)
            quicksort(a, left, pivot)
            quicksort(a, pivot + 1, right)
        End If
    End Sub

    Sub qSort(ByVal a() As Integer)
        Dim i
        Dim ii
        For i = 0 To a.Length() - 1
            ii = New System.Random().Next(0, a.Length() - 1)
            If i <> ii Then
                Swap(a(i), a(ii))
            End If
        Next

        quicksort(a, 0, a.Length())
    End Sub

Вызов функции:

qSort(имя сортируемого массива)

Встроенный язык 1С 8.*

[править]

Здесь приведен алгоритм сортировки на примере объекта типа «СписокЗначений», но его можно модифицировать для работы с любым объектом, для этого нужно изменить соответствующим образом код функций «СравнитьЗначения», «ПолучитьЗначение», «УстановитьЗначение».

Функция СравнитьЗначения(Знач1, Знач2)
    Если Знач1>Знач2 Тогда
        Возврат 1;
    КонецЕсли;
    Если Знач1<Знач2 Тогда
        Возврат -1;
    КонецЕсли;
    Возврат 0;
КонецФункции
 
Функция ПолучитьЗначение(Список, Номер)
    Возврат Список.Получить(Номер-1).Значение;
КонецФункции
 
Процедура УстановитьЗначение(Список, Номер, Значение)
    Список[Номер-1].Значение =  Значение;
КонецПроцедуры
 
Процедура qs_0(s_arr, first, last)
 
    i = first;
    j = last;
    x = ПолучитьЗначение(s_arr, Окр((first + last) / 2, 0));
    	 
    Пока i <= j Цикл
        Пока СравнитьЗначения(ПолучитьЗначение(s_arr, i), x)=-1 Цикл
            i=i+1;
        КонецЦикла;
        Пока СравнитьЗначения(ПолучитьЗначение(s_arr, j), x)=1 Цикл
            j=j-1;
        КонецЦикла;
        Если i <= j Тогда
            Если i < j Тогда
                к=ПолучитьЗначение(s_arr, i);
                УстановитьЗначение(s_arr, i, ПолучитьЗначение(s_arr, j));
                УстановитьЗначение(s_arr, j, к);
            КонецЕсли;
            i=i+1;
            j=j-1;
        КонецЕсли;
    КонецЦикла;
 
    Если i < last Тогда
        qs_0(s_arr, i, last);
    КонецЕсли;
    Если first < j Тогда
        qs_0(s_arr, first,j);
    КонецЕсли;
КонецПроцедуры
 
Процедура Сортировать(Список, Размер="", Первый="", Последний="")
    Если Не ЗначениеЗаполнено(Первый) Тогда
        Первый=1;
    КонецЕсли;
    Если НЕ ЗначениеЗаполнено(Последний) Тогда
        Последний=Размер;
    КонецЕсли;
    qs_0(Список, Первый, Последний);
КонецПроцедуры
DEF FN QSORT(LOW,HIGH)
LOCAL I,J,X,TEMP

   J=HIGH
   X=Y[(LOW+HIGH)/2]
   DO
      WHILE Y[I]<X:I=I+1:WEND
      WHILE Y[J]>X:J=J-1:WEND
      IF I<=J THEN
         TEMP=Y[I]
         Y[I]=Y[J]
         Y[J]=TEMP
         I=I+1
         J=J-1
      END IF
   LOOP WHILE I<=J
   IF LOW<J THEN F=FN QSORT(LOW,J)
   IF I<HIGH THEN F=FN QSORT(I,HIGH)
   FN QSORT=TRUE
END DEF

Пример вызова функции FN QSORT(LOW,HIGH), входные и выходные данные в массиве DIM Y[N1:N2]

LOW=N1
HIGH=N2
F=FN QSORT(LOW,HIGH)
----------------------------------------------------------------------------------
type sort_lst is table of integer;
-----------------------------------------------------------------------------------
function sort(in_array IN out sort_lst, in_low in integer, in_high in integer) return sort_lst
  is
      i integer default 1; j integer default 1;
      m real; wsp real;
      l_array sort_lst:=sort_lst();
  begin  
      l_array :=in_array;
 
      i:=in_low; j:=in_high; m:=l_array((i+j)/2); -- Взятие среднего опорного элемента
      
      loop
        while (l_array(i)<m) loop
              i:=i+1; -- изменить порядок сортировки можно
           end loop; 
           
        while (l_array(j)>m) loop
             j:=j-1;  -- поменяв >< в этих двух строках
        end loop; 

        if i<=j then 
            begin
               wsp:=l_array(i); l_array(i):=l_array(j); l_array(j):=wsp;
               I:=I+1; j:=j-1;
            end;
        end if;

        exit when i>j; -- пост условие
      end loop;

      if in_low<j then 
         l_array:=sort(l_array, in_low, j);     
      end if;
      
      if i<in_high then
          l_array:=sort(l_array, i, in_high);  
      end if;
      
      return l_array;
          
end sort;
----------------------Быстрая сортировка---------------------------------------------------------------------------------------------------------
Function Quick_sort(in_unsorted_list IN sort_lst) return sort_lst
  IS   
    l_unsorted_list sort_lst:=sort_lst();
    l_res sort_lst:=sort_lst();
begin
  l_unsorted_list:=in_unsorted_list;  
  l_res:=sort(l_unsorted_list, l_unsorted_list.first, l_unsorted_list.last);
  return l_res;  
end Quick_sort;
--------------------------------------------------------------------------------------------------------------------------------------------------