Sorting algorithums > Data Structures & Algorithums

Why Sort?
A classic problem in computer science!
Data requested in sorted order
 e.g.,

find students in increasing gpa order

Sorting is first step in bulk loading B+ tree index.
Sorting useful for eliminating duplicate copies in a

collection of records
Sorting is useful for summarizing related groups of
tuples
Sort-merge join algorithm involves sorting.
Problem: sort 100Gb of data with 1Gb of RAM.
 why

not virtual memory?

Bubble sort
Compare each element (except the last one) with its

neighbor to the right

 If they are out of order, swap them
 This puts the largest element at the very end
 The last element is now in the correct and final place

Compare each element (except the last two) with its


 If they are out of order, swap them
 This puts the second largest element next to last
 The last two elements are now in their correct and final places

Compare each element (except the last three) with its


 Continue as above until you have no unsorted elements on the

left

Example of bubble sort
7 2 8 5 4

2 7 5 4 8

2 5 4 7 8

2 4 5 7 8

2 7 8 5 4

2 7 5 4 8

2 5 4 7 8

2 4 5 7 8

2 7 8 5 4

2 5 7 4 8

2 4 5 7 8

(done)

2 7 5 8 4

2 5 4 7 8

2 7 5 4 8

Sorting - Bubble
From the first element
Exchange pairs if they’re out of order


Last one must now be the largest

Repeat from the first to n-1
Stop when you have only one element to check

Bubble Sort
/* Bubble sort for integers */
#define SWAP(a,b)
{ int t; t=a; a=b; b=t; }
void bubble( int a[], int n ) {
int i, j;
for(i=0;i<n;i++) { /* n passes thru the array */
/* From start to the end of unsorted part */
for(j=1;j<(n-i);j++) {
/* If adjacent items out of order, swap */
if( a[j-1]>a[j] ) SWAP(a[j-1],a[j]);
}
}
}

Bubble Sort - Analysis
#define SWAP(a,b)
int i, j;
for(j=1;j<(n-i);j++) {
if( a[j-1]>a[j] ) SWAP(a[j-1],a[j]);
}
}
O(1) statement
}

#define SWAP(a,b)
int i, j;
for(j=1;j<(n-i);j++) {
if( a[j-1]>a[j] ) SWAP(a[j-1],a[j]);
}
}
Inner loop
O(1) statement
}
n-1, n-2, n-3, … , 1 iterations

#define SWAP(a,b)
int i, j;
for(j=1;j<(n-i);j++) {
if( a[j-1]>a[j] ) SWAP(a[j-1],a[j]);
}
}
}
Outer loop n iterations

#define SWAP(a,b)
int i, j;
Overall
1
n(n+1)
for(j=1;j<(n-i);j++) {
Σ i =
= O(n2)
2
i=n-1
if( a[j-1]>a[j] ) SWAP(a[j-1],a[j]);
}
}
inner loop iteration count
} outer loop iterations
n

Sorting - Simple
Bubble sort
O(n2)
Very simple code

Insertion sort
Slightly better than bubble sort


Fewer comparisons

Also O(n2)

Selection sort
Given an array of length n,

0 through n-1 and select the smallest
 Swap it with the element in location 0
Search elements 1 through n-1 and select the smallest
Search elements

Continue in this fashion until there’s nothing left to

search

Example and analysis of
selectionsort
The selection sort might swap an
7 2 8 5 4

2 7 8 5 4
2 4 8 5 7
2 4 5 8 7

array element with itself--this is
harmless, and not worth checking for
Analysis:
The outer loop executes n-1 times
The inner loop executes about n/2
times on average (from n to 2 times)
Work done in the inner loop is

2 4 5 7 8

constant (swap two array elements)

(n-1)*(n/2)
You should recognize this as O(n2)
Time required is roughly

13

Selection sort
How does it work:

 first find the smallest in the array and exchange it with the element in

the first position, then find the second smallest element and
exchange it with the element in the second position, and continue in
this way until the entire array is sorted.
 How does it sort the list in a non increasing order?

Selection sort is:

 The simplest sorting techniques.
 a good algorithm to sort a small number of elements
 an incremental algorithm – induction method

Selection sort is Inefficient for large lists.

Incremental algorithms  process the input elements oneby-one and maintain the solution for the elements processed
so far.

Selection Sort Algorithm
Input: An array A[1..n] of n elements.
Output: A[1..n] sorted in nondecreasing order.
1. for i ← 1 to n - 1
2. k ← i
3. for j ← i + 1 to n {Find the i th smallest element.}
4. if A[j] < A[k] then k ← j
5. end for
6. if k ≠ i then interchange A[i] and A[k]
7. end for

Sorting
 Card players all know how to sort …
 First card is already sorted
 With all the rest,

Scan back from the end until you find the first card larger than
the new one,
Move all the lower ones up one slot
insert it

A

K

10

2

J

2

2
9

Q

9

One step of insertion sort
sorted
3

4

next to be inserted

7 12 14 14 20 21 33 38 10 55 9 23 28 16

less than
10
3

4

temp
10

7 10 12 14 14 20 21 33 38 55 9 23 28 16
sorted

Algorithm: INSERTIONSORT
Input: An array A[1..n] of n elements.
Output: A[1..n] sorted in nondecreasing order.
1. for
i ← 2 to n
2. x ← A[i]
3. j ← i - 1
4. while (j >0) and (A[j] > x)
5. A[j + 1] ← A[j]
6.
j← j-1
7. end while
8. A[j + 1] ← x
9. end for
Example sort : 34 8 64 51 32 21

Analysis of insertion sort
We run once through the outer loop, inserting
each of n elements; this is a factor of n
On average, there are n/2 elements already sorted
The inner loop looks at (and moves) half of these
This gives a second factor of n/4

Hence, the time required for an insertion sort of
an array of n elements is proportional to n2/4
Discarding constants, we find that insertion sort is
O(n2)

Summary
Bubble sort, selection sort, and insertion sort are all

O(n2)
As we will see later, we can do much better than this
with somewhat more complicated sorting algorithms
Within O(n2),
 Bubble sort is very slow, and should probably never be used

for anything
 Selection sort is intermediate in speed
 Insertion sort is usually the fastest of the three--in fact, for
small arrays (say, 10 or 15 elements), insertion sort is faster
than more complicated sorting algorithms

Selection sort and insertion sort are “good enough” for

small arrays

Radix Sort
Consider the following 9 numbers:
493 812 715 710 195 437 582 340 385
We should start sorting by comparing and ordering the one's digits:

Digit

Sublist

0

  340 710

1

2

  812 582

3
4

  493

  715 195
385

  437

5
6
7
8
9

Notice that the numbers were added onto
the list in the order that they were found,
which is why the numbers appear to be
unsorted in each of the sublists above.
Now, we gather the sublists (in order from
the 0 sublist to the 9 sublist) into the main
list again:
340 710 812 582 493 715 195
385 437

Now, the sublists are created again, this time based on the ten's digit:
Now the sublists are gathered in order from 0 to 9:
710 812 715 437 340 582 385 493 195
Digit

Sublist

0

1

  710 812 715

2
3
4
5
6
7

  437
  340

8

  582 385

9

  493 195

Now the sublists are gathered in
order from 0 to 9:
710 812 715 437 340
582 385 493 195

Finally, the sublists are created according to the hundred's digit:
At last, the list is gathered up again:
195 340 385 437 493 582 710 715 812
Digit

Sublist

0
1
2

  195

3

  340 385

4

  437 493

5
6

  582

7

  710 715

8
9

  812

At last, the list is gathered up
again:
195 340 385 437 493
582 710 715 812

Disadvantages
Still, there are some tradeoffs for Radix Sort that can make it less
preferable than other sorts.
The speed of Radix Sort largely depends on the inner basic
operations, and if the operations are not efficient enough, Radix
Sort can be slower than some other algorithms such as Quick
Sort and Merge Sort. These operations include the insert and
delete functions of the sublists and the process of isolating the
digit you want.
In the example above, the numbers were all of equal length, but
many times, this is not the case. If the numbers are not of the
same length, then a test is needed to check for additional digits
that need sorting. This can be one of the slowest parts of Radix
Sort, and it is one of the hardest to make efficient.

Radix Sort can also take up more space than other sorting
algorithms, since in addition to the array that will be sorted, you
need to have a sublist for each of the possible digits or letters. If
you are sorting pure English words, you will need at least 26
different sublists, and if you are sorting alphanumeric words or
sentences, you will probably need more than 40 sublists in all!
Since Radix Sort depends on the digits or letters, Radix Sort is
also much less flexible than other sorts. For every different type
of data, Radix Sort needs to be rewritten, and if the sorting order
changes, the sort needs to be rewritten again. In short, Radix Sort
takes more time to write, and it is very difficult to write a general
purpose Radix Sort that can handle all kinds of data.

Merge Sort
7 29 4 → 2 4 7 9
7 2 → 2 7
7→ 7

2→ 2

9 4 → 4 9
9→ 9

4→ 4

Merge Sort
Merge sort is based on

the divide-and-conquer
paradigm. It consists of
three steps:
 Divide: partition input

sequence S into two
sequences S1 and S2 of
about n/2 elements each
 Recur: recursively sort S1
and S2
 Conquer: merge S1 and S2
into a unique sorted
sequence

Algorithm mergeSort(S, C)
Input sequence S, comparator C
Output sequence S sorted
according to C
if S.size() > 1 {
(S1, S2) := partition(S, S.size()/2)
S1 := mergeSort(S1, C)
S2 := mergeSort(S2, C)
S := merge(S1, S2)
}
return(S)

Merge Sort Execution Tree (recursive calls)
An execution of merge-sort is depicted by a binary

tree

 each node represents a recursive call of merge-sort and stores

unsorted sequence before the execution and its partition
 sorted sequence at the end of the execution
 the root is the initial call
 the leaves are calls on subsequences of size 0 or 1


7 2 9 4 → 2 4 7 9

7 2 → 2 7

7→ 7

2→ 2
Divide-and-Conquer

9 4 → 4 9

9→ 9

4→ 4

Execution Example

Partition

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 2 9 4 → 2 4 7 9

7 2 → 2 7

7→ 7

2→ 2

3 8 6 1 → 1 3 8 6

9 4 → 4 9

9→ 9

4→ 4

Divide-and-Conquer

3 8 → 3 8

3→ 3

6 1 → 1 6

8→ 8
29

6→ 6

1→ 1

Execution Example (cont.)

Recursive call, partition

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9

7 2 → 2 7

7→ 7

2→ 2

3 8 6 1 → 1 3 8 6

9 4 → 4 9

9→ 9

4→ 4

Divide-and-Conquer

3 8 → 3 8

3→ 3

6 1 → 1 6

8→ 8
30

6→ 6

1→ 1


Recursive call, partition

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9

7 2→ 2 7

7→ 7

2→ 2

3 8 6 1 → 1 3 8 6

9 4 → 4 9

9→ 9

4→ 4

Divide-and-Conquer

3 8 → 3 8

3→ 3

6 1 → 1 6

8→ 8
31

6→ 6

1→ 1


Recursive call, base case

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9

7 2→ 2 7

7→ 7

2→ 2

3 8 6 1 → 1 3 8 6

9 4 → 4 9

9→ 9

4→ 4

Divide-and-Conquer

3 8 → 3 8

3→ 3

6 1 → 1 6

8→ 8
32

6→ 6

1→ 1

Recursive call, base case

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9

7 2→ 2 7

7→ 7

2→ 2

3 8 6 1 → 1 3 8 6

9 4 → 4 9

9→ 9

4→ 4

Divide-and-Conquer

3 8 → 3 8

3→ 3

6 1 → 1 6

8→ 8
33

6→ 6

1→ 1


Merge

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9

7 2→ 2 7

7→ 7

2→ 2

3 8 6 1 → 1 3 8 6

9 4 → 4 9

9→ 9

4→ 4

Divide-and-Conquer

3 8 → 3 8

3→ 3

6 1 → 1 6

8→ 8
34

6→ 6

1→ 1


Recursive call, …, base case, merge

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9

72→2 7

7→ 7

2→ 2

3 8 6 1 → 1 3 8 6

9 4 → 4 9

9→ 9

4→ 4

Divide-and-Conquer

3 8 → 3 8

3→ 3

6 1 → 1 6

8→ 8
35

6→ 6

1→ 1


Merge

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9

7 2→ 2 7

7→ 7

2→ 2

3 8 6 1 → 1 3 8 6

9 4 → 4 9

9→ 9

4→ 4

Divide-and-Conquer

3 8 → 3 8

3→ 3

6 1 → 1 6

8→ 8
36

6→ 6

1→ 1

Recursive call, …, merge, merge

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9

7 2→ 2 7

7→ 7

2→ 2

3 8 6 1 → 1 3 6 8

9 4 → 4 9

9→ 9

4→ 4

Divide-and-Conquer

3 8 → 3 8

3→ 3

6 1 → 1 6

8→ 8
37

6→ 6

1→ 1


Merge

7 2 9 43 8 6 1 → 1 2 3 4 6 7 8 9

7 29 4→ 2 4 7 9

7 2→ 2 7

7→ 7

2→ 2

3 8 6 1 → 1 3 6 8

9 4 → 4 9

9→ 9

4→ 4

Divide-and-Conquer

3 8 → 3 8

3→ 3

6 1 → 1 6

8→ 8
38

6→ 6

1→ 1

Another Analysis of Merge-Sort
 The height h of the merge-sort tree is O(log n)
 at each recursive call we divide in half the sequence,

 The work done at each level is O(n)
 At level i, we partition and merge 2i sequences of size n/2i

 Thus, the total running time of merge-sort is O(n log n)
depth

#seqs

size

0

1

n

Cost for
level
n

1

2

n/2

n

i

2i

n/2i

n

…

…

…

…

logn

2logn = n n/2logn = 1

n
Divide-and-Conquer

Summary of Sorting Algorithms
(so far)

Vectors

Algorithm

Time

Notes

Selection Sort

O(n2)

Slow, in-place
For small data sets

Insertion Sort

O(n2) WC, AC
O(n) BC

Slow, in-place
For small data sets

Heap Sort

O(nlog n)

Fast, in-place
For large data sets

Merge Sort

O(nlogn)

Fast, sequential data access
For huge data sets

7 4 9 6 2 → 2 4 6 7 9
4 2 → 2 4
2→ 2

Divide-and-Conquer

7 9 → 7 9
9→ 9

Quick-Sortrandomized
Quick-sort is a
sorting algorithm based on
the divide-and-conquer
paradigm:

x

 Divide: pick a random

element x (called pivot) and
partition S into




L elements less than x
E elements equal x
G elements greater than x

x
L

E

 Recur: sort L and G
 Conquer: join L, E and G

Divide-and-Conquer

x

G

Analysis of Quick Sort using
Recurrence Relations
• Assumption: random pivot

expected to give equal
sized sublists
• The running time of Quick
Sort can be expressed as:
T(n) = 2T(n/2) + P(n)
• T(n) - time to run quicksort()

on an input of size n
• P(n) - time to run partition() on
input of size n
Divide-and-Conquer

Algorithm QuickSort(S, l, r)
Input sequence S, ranks l and r
Output sequence S with the
elements of rank between l and r
rearranged in increasing order
if l ≥ r
return
i ← a random integer between l and r
x ← S.elemAtRank(i)
(h, k) ← Partition(x)
QuickSort(S, l, h − 1)
QuickSort(S, k + 1, r)

Quicksort
Efficient sorting algorithm
Discovered by C.A.R. Hoare

Example of Divide and Conquer algorithm
Two phases
Partition phase


Divides the work into half

Sort phase


Conquers the halves!

Quicksort
Partition
Choose a pivot
Find the position for the pivot so that

all elements to the left are less
 all elements to the right are greater


< pivot

pivot

> pivot

Quicksort algorithm to each half
Apply the same
Conquer

< pivot
< p’

p’

> pivot
> p’

pivot

< p”

p”

> p”

Quicksort

Implementation
quicksort( void *a, int low, int high )
{
int pivot;
/* Termination condition! */
if ( high > low )
{
pivot = partition( a, low, high );
quicksort( a, low, pivot-1 );
quicksort( a, pivot+1, high );
}
}

Divide
Conquer

int partition( int *a, int low, int high ) {
int left, right;
int pivot_item; Partition
pivot_item = a[low];
pivot = left = low;
right = high;
while ( left < right ) {
/* Move left while item < pivot */
while( a[left] <= pivot_item ) left++;
/* Move right while item > pivot */
while( a[right] >= pivot_item ) right--;
if ( left < right ) SWAP(a,left,right);
}
/* right is final position for the pivot */
a[low] = a[right];
a[right] = pivot_item;
return right;
}

Quicksort -

This example
uses int’s
to keep things
simple!

int left, right;
pivot = left = low;
right = high;
Any item will do as the pivot,
while ( left < right ) { choose the leftmost one!
}
23 12 15 38 42 18 36 29 27
a[low] = a[right];
return right;
low
high
}

Quicksort -

int left, right;
pivot = left = low;
Set left and right markers
right = high;
while( a[left] <= pivot_item ) left++; right
left
if (23 12 right 38 SWAP(a,left,right);27
left < 15
) 42 18 36 29
}
a[low]low a[right];
=
high
pivot: 23
return right;
}

Quicksort -


Quicksort - Partition
int left, right;
int pivot_item;
pivot = left = low;
right = high;

Move the markers
until they cross over

left
}
a[low] = a[right]; 15 38 42 18 36 29
23 12
return right;
low
pivot: 23
}

right
27
high


int left, right;
int pivot_item;
pivot = left = low;
right = high;

Move the left pointer while
it points to items <= pivot
left
right
}
Move right
/* right is final position for the pivot */ similarly
a[low] = a[right];
23 12 15 38 42
a[right] = pivot_item; 18 36 29 27
return right;
}
low
high
pivot: 23


int left, right;
int pivot_item;
pivot = left = low;
right = high;

Swap the two items
on the wrong side of the pivot



}
left
right
a[low] = a[right];
23 12 15 38 42
return right;
pivot: 23
}
low
high


int left, right;
int pivot_item;
pivot = left = low;
right = high;

left and right
have swapped over,
so stop



}
left
/* right isright
final position for the pivot */
a[low] = a[right];
23 12 15 18 42
return right;
}
low
high
pivot: 23


int left, right;
int pivot_item;
pivot = left = low;
right = high;
right

left

23

while( 18 42 38 36 29 27
12 15 a[left] <= pivot_item ) left++;

low
high
pivot: 23
}
a[low] = a[right];
Finally, swap the pivot
and right
return right;
}


int left, right;
int pivot_item;
pivot = left = low;
right = high;
right


18

pivot: 23

while( 23 42 38 36 29 27
12 15 a[left] <= pivot_item ) left++;

low
high
}
a[low] = a[right];
Return the position
a[right] = pivot_item; of the pivot
return right;
}

Quicksort - Conquer
pivot

pivot: 23
18

12

15

Recursively
sort left half

23

42

38

36

29

27

Recursively
sort right half

Sorting algorithums > Data Structures & Algorithums

Recommended

More Related Content

What's hot (20)

Similar to Sorting algorithums > Data Structures & Algorithums (20)

More from Ain-ul-Moiz Khawaja (17)

Recently uploaded (20)

Sorting algorithums > Data Structures & Algorithums