Quicksort

Описание быстрой сортировки

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

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

Partition(A,p, r)
1. x<-A[r]
2. i<-p-1
3. for j<-p to r-1
4. do if A[j]<=x
5. then i<-i+1
6. swap A[i]<->A[j]
7. swap A[i+1]<->A[r]
8. return i+1
Quicksort(A,p, r)
1. if p<r
2. then q<-Partition(A,p,r)
3. Quicksort(A,p, q-1)
4. Quicksort(A,q+1,r)

Производительность быстрой сортировки

В том случае, когда быстрая сортировка создает разбиение на два подмассива размерами n-1 и 0, алгоритм будет работать за Θ(n²), поэтому, для того, чтобы свести вероятность такого разбиения чаще используется алгоритм рандомизированной быстрой сортировки.

Алгоритм рандомизированной быстрой сортировки

Randomized_Partition(A,p,r)
1. i<-Random(p,r)
2. swap A[r]<->A[i]
3. return Partition(A,p,r)
Randomized_Quicksort(A,p,r)
1. if p<r
2. then q<-Randomized_Partition(A,p,r)
3. Randomized_Quicksort(A,p,q-1)
4. Randomized_Quicksort(A,q+1,r)


Реализация быстрой сортировки на С

<source lang="cpp">

1. include <stdio.h>
2. include <stdlib.h>
3. include <time.h>

int x[1000];

int randint(int a, int b) { srand(time(NULL)); return a+rand()%(b-a); }

void swap(int a, int b) { int tmp=x[a]; x[a]=x[b]; x[b]=x[a]; }

void qsort(int l, int u) { int i,m; if(l>=u) return; swap(l, randint(l,u)); m=l; for(i=l+1; i<=u; i++) if(x[i]<x[l]) swap(++m, i); swap(l,m); qsort(l,m-1); qsort(m+1,u); } </source>

Литература

• Томас Х. Кормен и др. Глава 7. Быстрая сортировка // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
• Энди Орам и Грег Уилсон Глава 3. Самый красивый код, который я никогда не писал // Идеальный код = Beautiful Code. — 1-е изд. — C.: «O'Reilly», 2007. — С. 624. — ISBN 978-5-91180-603-3