11/4/2010

Naïve Sorting Algorithms

There are three standard algorithms

Bubble or exchange sort
Naïve Sorts
Insertion Sort

Selection Sort

Naïve sorting algorithms

Bubble Sort
Bubble sort: scan for flips, until all are fixed

Big Idea: Compare adjacent entries and swap when
3 2 1 6 5 4
A[i] > A[i+1]

Example: 2 3 1 6 5 4

2 1 3 6 5 4

2 1 3 5 6 4

2 1 3 5 4 6 Etc...

Naïve Sorting Insertion Sort

for i=1 to n-1
Big Idea: Assume the list [0,1…,i-1] is sorted. Insert A[i]
{ for j=0 to n-i-1
if (A[j] > A[j+1]) element to right place.
swap(A[j], A[j+1]);
Example:
if (no swaps) break;
}

What is the complexity of the algorithm, if

All keys are equal?

Keys are sorted in reverse order?

Keys are sorted?

keys are randomly distributed?

1
 11/4/2010

Insertion sort Insertion sort

Sorted subarray • Algorithm
105 47 13 99 30 222 for i = 1 to n-1 do
47 105 13 99 30 222 insert a[i] in the proper place
13 47 105 99 30 222 in a[0:i-1]
• Correctness
13 47 99 105 30 222
•Consider the Loop Invariant: after i steps, the sub-array A[0:i] is
13 30 47 99 105 222 sorted
•Show that loop invariant holds at the beginning and is true at the end
105 47 13 99 30 222 of the loop
•More on correctness of algorithms later

Selection Sort Complexity of Naïve Sorts

Big Idea: Find the max of the list and exchange with
Analysis
the last element
Bubble

Example:

Insertion

Selection

Divide-and-conquer

Merge Sort

2
 11/4/2010

Merging Two Sorted Arrays

All the work in merge sort is done at the merge step.

Example
Quick Sort
1 13 24 26 2 15 27 38

Quicksort idea
Quicksort

Quicksort was invented in 1960 by Tony Hoare.
Choose a pivot.

Quicksort has O(N2) worst-case performance, and on

average O(N log N).

More importantly, it is the fastest known comparison-

Rearrange so that
pivot is in the “right”
based sorting algorithm in practice.
spot.

Recurse on each half

and conquer!

Quicksort algorithm Quicksort algorithm

105 47 13 17 30 222 5 19

If array A has 1 (or 0) elements, then done.

19

Choose a pivot element x from A.
5 17 13 47 30 222 105

Divide A-{x} into two arrays:

B = {y∈A | y≤x} 13 47

C = {y∈A | y≥x} 5 17 30 222 105

Result is B+{x}+C.

Recurse on arrays B and C
105 222

3
 11/4/2010

Place the pivot algorithm Example

Assume we have an array of size n
Show how to place the pivot (choose middle element)

Pick a pivot x in the right place

34 24 56 17 19 45 90 23 36

Place the pivot x in the last place of the array

Have two pointers i = 0, j = n-2
while ( i <= j) {
while (A[j] > pivot) j--;
while (A[i] < pivot) i--;
swap (A[i], A[j]);
}
swap (A[i], pivot);

Naïve sorting algorithms

Bubble sort: scan for flips, until all are fixed
3 2 1 6 5 4
2 3 1 6 5 4
Ananda Gunawardena
2 1 3 6 5 4
2 1 3 5 6 4

2 1 3 5 4 6 Etc...

Insertion sort
Naïve Sorting Sorted subarray
for i=1 to n-1 105 47 13 99 30 222
{ for j=0 to n-i-1
if (A[j].compareTo(A[j+1])>0) 47 105 13 99 30 222
swap(A[j], A[j+1]);
if (no swaps) break; 13 47 105 99 30 222
}

What happens if 13 47 99 105 30 222

All keys are equal?

Keys are sorted in reverse order? 13 30 47 99 105 222

Keys are sorted?

keys are randomly distributed? 105 47 13 99 30 222

Exercise: Count the number of operations in bubble sort
and find a Big O analysis for bubble sort

4
 11/4/2010

Insertion sort How fast is insertion sort?

• Algorithm
To insert a[i] into a[0:i-1], slide all elements larger
for i = 1 to n-1 do than a[i] to the right.
insert a[i] in the proper place
tmp = a[i];
in a[0:i-1]
for (j = i; j>0 && a[j-1]>tmp; j--)
• Correctness
a[j] = a[j-1];
•Note: after i steps, the sub-array A[0:i] is
sorted a[j] = tmp;

# of slides = O(#inversions)
very fast if array is nearly sorted to begin with

Selection sort Sorting Comparison

• Algorithm
for i = n-1 to 1 do
Discuss the pros and cons of each of the naïve sorting
algorithms
Find the largest entry in the
in the subarray A[0:i]
Swap with A[i]

What is the runtime complexity of

selection sort?

Quick Sort in practice

Fastest algorithm

Algorithm

Find a pivot

Move all elements smaller than pivot to left
Advanced Sorting
Move all elements bigger than pivot to right

Recursively sort each half

O(n log n) algorithm

5
 11/4/2010

Merge Sort Heap Sort

Divide the array into two equal halves
Build a max heap

Divide each half recursively until each array is of size 1
Delete Max (attach to end of array) until heap is empty

Merge two (sorted) arrays of size 1
Resulting array is sorted

Complete the process recursively
Complexity

Bucket sort

In addition to comparing pairs of elements, we require

these additional restrictions:

all elements are non-negative integers

Bucket Sort
all elements are less than a predetermined maximum

value

Elements are usually keys paired with other data

Bucket
1
sort
3 3 1 2
Bucket sort characteristics

Runs in O(N) time.

Easy to implement each bucket as a linked list.

Is stable:

If two elements (A,B) are equal with respect to sorting,
and they appear in the input in order (A,B), then they
remain in the same order in the output.

1 2 3

6
 11/4/2010

Radix sort

If your integers are in a larger range then do bucket
sort on each digit

Radix Sort
Start by sorting with the low-order digit using a

STABLE bucket sort.

Then, do the next-lowest,and so on

Radix sort Radix sort characteristics

Example:
Each sorting step can be performed via bucket sort,
and is thus O(N).
2 0 1 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 1 1
5 1 0 1 1 0 0 1 0 1 0 1 0 2
If the numbers are all b bits long, then there are b
1 0 0 1 1 1 0 0 0 1 0 1 1 3 sorting steps.
7 1 1 1 1 0 1 0 1 0 1 0 0 4
3 0 1 1 0 0 1 1 1 0 1 0 1 5
Hence, radix sort is O(bN).
4 1 0 0 1 1 1 1 1 1 1 1 0 6
6 1 1 0 0 1 1 0 1 1 1 1 1 7

Each sorting step must be stable.

What about

Radix sort non-binary?
can be used for decimal numbers and
alphanumeric strings.

0 3 2 0 3 1 0 1 5 0 1 5
2 2 4 0 3 2 0 1 6 0 1 6
0 1 6 2 5 2 1 2 3 0 3 1
0 1 5 1 2 3 2 2 4 0 3 2
0 3 1 2 2 4 0 3 1 1 2 3
1 6 9 0 1 5 0 3 2 1 6 9
1 2 3 0 1 6 2 5 2 2 2 4
2 5 2 1 6 9 1 6 9 2 5 2