Sorting algorithms and
order statistic algorithms
Data Structures and Algorithms
1
DSaA 2012/2013
Sorting - definition
" Sorting: process by which a collection
of items is placed into order
 Operation of arranging data
" Swaps
" Assignments
 Order typically based on a data field called
a key
Formal Definition:
The sort operation may be defined in terms of an initial array, S,
of N items and a final array, S2 , as follows.
1) S2 i d" S2 i+1, 0 < i < N (the items are in order) and
2) S2 is a permutation of S.
2
DSaA 2012/2013
Sorting
Sorting:
" comparable
 insertsort
 selectsort
 bubblesort
 mergesort
 quicksort
 heapsort
" noncomparable
 bucketsort
 radixsort
3
DSaA 2012/2013
Sorting property
(key, data)
(5,3),(6,4),(5,1),(2,4),(5,3),(2,5)
" method
 comparable
 non-comparable
(2,4),(2,5),(5,3),(5,1),(5,3),(6,4)
" stability
 stable
 unstable
" extra memory needed
 in-place extra memory: O(1)
 extra memory greater than O(1)
" distance between exchanged elements
 long distance
 short distance
" sorting whole or adding new element
 off-line
 on-line
4
DSaA 2012/2013
Insertsort - example
76 71 57 12 50 20 93 43 85 62 5 3
71 76 57 12 50 20 93 43 85 62 5 3
57 71 76 12 50 20 93 43 85 62 5 3
12 57 71 76 50 20 93 43 85 62 5 3
12 50 57 71 76 20 93 43 85 62 5 3
12 20 50 57 71 76 93 43 85 62 5 3
12 20 50 57 71 76 93 43 85 62 5 3
12 20 43 50 57 71 76 93 85 62 5 3
12 20 43 50 57 71 76 85 93 62 5 3
5
DSaA 2012/2013
Insertsort - code
void insertSort(int arr[],int n)
{
int i,j,k,elem;
for(i=1;i {
j=0;
elem=arr[i]; // i-th element will be added
while(j j++;
for(k=i;k>j;k--) // shift elements
arr[k]=arr[k-1];
arr[j]=elem;
//showArr(arr,n);
}
}
6
DSaA 2012/2013
insertsort - analysis
" complexity
 worse-case, average complexity: O(n2)
" property
 suitable for linked list
 stable
 work quickly for small list  threshold sorting algorithm
 work quickly on large list that are close to being
sorted in the sense that no element has many larger
elements occurring before it.
 an online sorting algorithm
 in-place algorithm
7
DSaA 2012/2013
Selectionsort - example
1 2 3 4 11 12
76 71 57 12 50 20 93 43 85 62 5 3
2 3 4 11
3 71 57 12 50 20 93 43 85 62 5 76
3 4
3 5 57 12 50 20 93 43 85 62 71 76
4 5 6
3 5 12 57 50 20 93 43 85 62 71 76
5 8
3 5 12 20 50 57 93 43 85 62 71 76
6 8
3 5 12 20 43 57 93 50 85 62 71 76
7 8
3 5 12 20 43 50 93 57 85 62 71 76
8
DSaA 2012/2013
Selectsort - code
void selectSort(int arr[],int n)
{
int i,j,minIdx,minElem;
for(i=0;i {
minIdx=i; // minimum search
minElem=arr[i];
for(j=i;j if(arr[j] {
minElem=arr[j];
minIdx=j;
}
arr[minIdx]=arr[i];
arr[i]=minElem;
// showArr(arr,n);
}
}
9
DSaA 2012/2013
Selectsort - property
" complexity
 worse-case, average complexity: O(n2)
" property
 unstable (can be changed to be stable!)
 in-place algorithm
 easy to implement
10
DSaA 2012/2013
Bubblesort  example  1 step
76 71 57 12 50 20 93 43 85
71 76 57 12 50 20 93 43 85
71 57 76 12 50 20 93 43 85
71 57 12 76 50 20 93 43 85
swap
no swap
71 57 12 50 76 20 93 43 85
71 57 12 50 20 76 93 43 85
71 57 12 50 20 76 93 43 85
71 57 12 50 20 76 43 93 85
71 57 12 50 20 76 43 85 93
11
DSaA 2012/2013
Bubblesort  example
71 57 12 50 20 76 43 85 93 12 20 50 43 57 71 76 85 93
12 20 43 50 57 71 76 85 93
57 12 50 20 71 76 43 85 93
12 20 43 50 57 71 76 85 93
57 12 50 20 71 43 76 85 93
12 20 43 50 57 71 76 85 93
12 50 20 57 71 43 76 85 93
12 20 43 50 57 71 76 85 93
12 20 50 57 71 43 76 85 93
12 20 50 57 43 71 76 85 93
12 20 43 50 57 71 76 85 93
12 20 50 57 43 71 76 85 93
12 20 50 43 57 71 76 85 93
12
DSaA 2012/2013
Bubblesort - code
void bubbleSort(int arr[],int n)
{
int i,j,aux;
for(i=n-1;i>=0;i--)
{
for(j=0;j if(arr[j]>arr[j+1])
{
aux=arr[j];
arr[j]=arr[j+1];
arr[j+1]=aux;
}
//showArr(arr,n);
}
}
13
DSaA 2012/2013
Bubblesort - property
" complexity
 worse-case, average complexity: O(n2)
" property
 stable
 in-place algorithm
 easy to implement
 online (act as an insertsort)
 short-distance
14
DSaA 2012/2013
Mergersort - merge
12 15 50 55 57 20 43 62 77 85
55 57 62 77 85
12 15 20 43 50 55
12
62 77 85
15 50 55 57 20 43 62 77 85 57
12 15 20 43 50 55 57
12 15
62 77 85
50 55 57 20 43 62 77 85
20 12 15 20 43 50 55 57 62
12 15
77 85
50 55 57 43 62 77 85
12 15 20 43 12 15 20 43 50 55 57 62 77
55 57
50 85
62 77 85
12 15 20 43 50 12 15 20 43 50 55 57 62 77 85
15
DSaA 2012/2013
Mergesort - example
55 15 57 12 50 20 77 43 85 62
55 15 57 12 50 20 77 43 85 62
55 15 57 12 50 20 77 43 85 62
55 15 57 12 50 20 77 43 85 62
55 15 20 77
15 55 20 77
15 55 57 12 50 20 43 77 62 85
12 15 50 55 57 20 43 62 77 85
12 15 20 43 50 55 57 62 77 85
16
DSaA 2012/2013
Mergesort - code
void auxMergeSort(int arr[],int arrAux[], int nFrom, int nTo)
{
if(nFrom {
int nCenter=(nFrom+nTo)/2;
auxMergeSort(arr,arrAux,nFrom,nCenter);
auxMergeSort(arr,arrAux,nCenter,nTo);
mergeArr(arr,arrAux,nFrom,nCenter,nTo); // to implement !!!
}
}
void mergeSort(int arr[],int len)
{
int *arr2=new int[len];
auxMergeSort(arr,arr2,0,len);
delete []arr2;
}
17
DSaA 2012/2013
Mergesort - property
" complexity
 worse-case, average complexity: O(n log n)
" property
 stable
 extra memory
 offline (online act as an insertsort)
18
DSaA 2012/2013
Quicksort  pseudocode, example
quicksort(A,p,r)
{
if(p {
q=partitioning(A,p,r);
quicksort(A,p,q);
quicksort(A,q+1,r);
}
}
55 15 57 12 50 20 77 43 85 62
50 55 15 57 12 20 77 43 85 62 50
15 12 20 43 50 55 57 77 85 62
50 43 15 57 12 20 77 55 85 62
15 12 20 43 50 55 57 62 77 85
50 43 15 20 12 57 77 55 85 62
12 15 20 43 50 55 57 62 77 85
15 20 55 57 12 43 15 20 50 57 77 55 85 62
<=50 >50
19
DSaA 2012/2013
Quicksort - code
void auxQuicksort(int arr[],int nFrom, int nTo){
if(nTo-nFrom>1)
{
int pivot,idxBigger, idxLower, temp;
pivot = arr[nFrom]; // if other pivot, swat it with nFrom element
idxBigger = nFrom + 1;
idxLower = nTo-1;
do{ //the partitioning
while (idxBigger <= idxLower && arr[idxBigger] <= pivot){
idxBigger++;
}
while (arr[idxLower] > pivot){
idxLower--;
}
if (idxBigger < idxLower) {
temp = arr[idxBigger];
arr[idxBigger] = arr[idxLower];
arr[idxLower] = temp;
}
}while (idxBigger < idxLower);
arr[nFrom] = arr[idxLower]; //put pivot in correct position
arr[idxLower] = pivot;
auxQuicksort(arr, nFrom, idxLower);
auxQuicksort(arr, idxLower+1, nTo);
}
}
void quicksort(int arr[],int len) { auxQuicksort(arr,0,len); }
20
DSaA 2012/2013
Quicksort - property
" complexity:
 worst-case: W(n)=O(n2)
 average-case: A(n)=O(nlogn)
" property:
 unstable
 algorithm  divide and conquer
 in-place
 offline
21
DSaA 2012/2013
Heap - definition
" The binary heap is an array object that can be viewed as a nearly complete
binary tree. The tree is completely filled on all levels except possibly the
lowest, which is filled from the left up to a point.
" The value of a node is at most the value of its parent
Root
78
Parent
60 45
Child
Node
54 4 12 31
Leaf
2
47 1
heap as an array:
0 1 2 3 4 5 6 7 8 9
1) a node with index i has two children
78 60 45 54 4 12 31 47 1 2
with indexes 2*i+1 and 2*i+2
2) a node with index i has a parent
with index i -ð1
Ä™ð Å›ð
Ä™ð Å›ð
2
ëð ûð
22
DSaA 2012/2013
Heapify - example
1) 2)
55 55
15 57 15 57
12 50 20 77 12 62 20 77
43 85 62 43 85 50
4 9 3 7 8
55 15 57 12 50 20 77 43 85 62 55 15 57 12 62 20 77 43 85 50
3) 4a)
55 55
15 57 15 77
85 62 20 77 85 62 20 57
43 12 50 43 12 50
2 5 6 1 3 4
55 15 57 85 62 20 77 43 12 50 55 15 77 85 62 20 57 43 12 50
23
DSaA 2012/2013
Heapify - example
4b) 5a)
55 55
85 77 85 77
15 62 20 57 43 62 20 57
43 12 50 15 12 50
3 7 8 0 1 2
55 85 77 15 62 20 57 43 12 50 55 85 77 43 62 20 57 15 12 50
5b) 5c)
85 85
55 77 62 77
43 62 20 57 43 55 20 57
15 12 50 15 12 50
1 3 4 4 9
85 55 77 43 62 20 57 15 12 50 85 62 77 43 55 20 57 15 12 50
24
DSaA 2012/2013
Heapify, heapAdjustment  code
void heapify(int heap[],int idx, int n)
{
int idxOfBigger=2*idx+1;
if(idxOfBigger {
if(idxOfBigger+1 idxOfBigger++;
if(heap[idx] {
swap(heap[idx],heap[idxOfBigger]);
heapify(heap,idxOfBigger,n);
}
}
}
void heapAdjustment(int heap[],int n)
{
for(int i=(n-1)/2;i>=0;i--)
heapify(heap, i, n);
}
25
DSaA 2012/2013
Heapsort - example
1b)
0) 1a)
85 50
77
62 77 62 77
62 57
43 55 20 57 43 55 20 57
43 55 20 50
15 12 50 15 12 85
15 12 85
77 62 57 43 55 20 50 15 12 85
85 62 77 43 55 20 57 15 12 50 50 62 77 43 55 20 57 15 12 85
2a) 2b) 3a)
62 15
12
62 57 55 57 55 57
43 55 20 50 43 12 20 50 43 12 20 50
15 77 85 15 77 85 62 77 85
12 62 57 43 55 20 50 15 77 85 62 55 57 43 12 20 50 15 77 85 15 55 57 43 12 20 50 62 77 85
26
DSaA 2012/2013
Heapsort  code, property
void heapSort(int heap[],int n)
{
heapAdjustment(heap, n);
for(int i=n-1;i>0;i--)
{
swap(heap[i],heap[0]);
heapify(heap,0,i);
}
}
" complexity:
 worse-case, average-case: O(nlogn)
" property:
 in-place
 non-stable
 can be used to implement priority queue
27
DSaA 2012/2013
CountingSort
" Assume that each of the n input element is an integer in the range 0
to k, for some integer k. When k=O(n) the sort runs in O(n) time.
" The basic idea of counting sort is to determine, for each input
element x, the number of elements less than x. This information can
be used to place element x directly into its position in the output
array
0 1 2 3 4 5 6 7
B 0 3 5
A 0 4 0 2 3 3 0 5
0 1 2 3 4 5
C
1 2 3 4 6 6
0 1 2 3 4 5 6 7
-1
B 0 0 2 3 3 5
+ + + + +
0 1 2 3 4 5 0 1 2 3 4 5
C C
3 0 1 2 1 1 0 1 3 3 6 6
0 1 2 3 4 5 6 7
B 0 0 0 2 3 3 4 5
0 1 2 3 4 5
C
2 2 3 5 6 7
0 1 2 3 4 5
C
-1 1 3 3 5 6
28
DSaA 2012/2013
CountingSort - code
void countingSort(int arr[],int n, int k)
{
k++;
int *pos=new int[k];
int *result=new int[n];
int i,j;
for(i=0;i pos[i]=0;
for(j=0;j pos[arr[j]]++;
pos[0]--;
for(i=1;i pos[i]+=pos[i-1];
for(j=n-1;j>=0;j--)
{
result[pos[arr[j]]]=arr[j];
pos[arr[j]]--;
}
for(j=0;j arr[j]=result[j];
}
29
DSaA 2012/2013
CountingSort - property
" Complexity:
 worse-case=average-case: O(n+k)
" property:
 extra memory O(n+k)
 stable
 offline
30
DSaA 2012/2013
Radixsort
RadixSort(A, d)
for i to d
use a stable sort to sort array A on digit i
293 231 3 3
495 22 22 22
329 293 329 195
248 3 231 231
22 495 235 235
3 195 248 248
Countingsort can be used !
256 235 256 256
Time: O(d*(n+k))
195 256 293 293
231 248 495 329
235 329 195 495
31
DSaA 2012/2013
Median or i-th smalest element
How to find minimum/maximum was presented in
selectSort. Complexity: O(n)
" How to find a median or i-th smalest element?
Sorting? Complexity: O(nlogn)
" Can be done faster using an idea from quicksort.
n
RANDOMIZED-SELECT(A, p, r, i)
n/2
if p = r
return A[p] n/4
q=RANDOMIZED-PARTITION(A, p, r)
n/8
k=q - p + 1
if i = k // the pivot value is the answer
2n
return A[q]
else if i < k
return RANDOMIZED-SELECT(A, p, q - 1, i)
The average-case
else
complexity: O(n)
return RANDOMIZED-SELECT(A, q + 1, r, i - k)
32
DSaA 2012/2013