Quicksort

Description of quick sort

Quick sort, like merge sort, is based on a paradigm "divide and rule". Below the process of sorting of a subarray of A[p.r] consisting as well as all algorithms using decomposition, from three stages is described.
1. Separation. The array of A[p.r] breaks (by rescheduling of its elements) into two (perhaps, empty) a subarray of A[p.q-1] and A[q+1.r]. Each element of a subarray A[p.q-1] does not exceed the A[q] element, and each element of a subarray A[q+1.r] is not less element A [q]. Index q is calculated during the procedure of splitting.
2. Conquest. Subarrays And [p.q-1] and And are sorted by [q+1.r] by a recursive call of the procedure of quick sort.
3. Combination. As subarrays are sorted on site, for their consolidation no actions are necessary: all array of A[p.r] is sorted.

Algorithm of quick sort

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)

Performance of quick sort

In that case when quick sort creates splitting into two subarrays the n-1 and 0 sizes, the algorithm will work for Θ (n ²) therefore to reduce the probability of such splitting the algorithm of randomized quick sort is more often used.

Algorithm of randomized quick sort

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)


Implementation of quick sort on With

<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>

Literature

• Шаблон:Book
• Шаблон:Book