Introduction to AlgorithmsIntroduction to Algorithms z ...

[Pages:7]Introduction to Algorithms

Sorting in Linear Time

CSE 680 Prof. Roger Crawfis

Comparison Sorting Review

z Insertion sort:

z Pro's:

z Easy to code z Fast on small inputs (less than ~50 elements) z Fast on nearly-sorted inputs

z Con's:

z O(n2) worst case z O(n2) average case z O(n2) reverse-sorted case

Comparison Sorting Review

z Merge sort:

z Divide-and-conquer:

z Split array in half z Recursively sort sub-arrays z Linear-time merge step

z Pro's:

z O(n lg n) worst case - asymptotically optimal for comparison sorts

z Con's:

z Doesn't sort in place

Comparison Sorting Review

z Heap sort:

z Uses the very useful heap data structure

z Complete binary tree z Heap property: parent key > children's keys

z Pro's:

z O(n lg n) worst case - asymptotically optimal for comparison sorts

z Sorts in place

z Con's:

z Fair amount of shuffling memory around

Comparison Sorting Review

z Quick sort:

z Divide-and-conquer:

z Partition array into two sub-arrays, recursively sort z All of first sub-array < all of second sub-array

z Pro's:

z O(n lg n) average case z Sorts in place z Fast in practice (why?)

z Con's:

z O(n2) worst case

z Na?ve implementation: worst case on sorted input z Good partitioning makes this very unlikely.

Non-Comparison Based Sorting

z Many times we have restrictions on our keys

z Deck of cards: Ace->King and four suites z Social Security Numbers z Employee ID's

z We will examine three algorithms which under certain conditions can run in O(n) time.

z Counting sort z Radix sort z Bucket sort

Counting Sort

z Depends on assumption about the numbers being sorted

z Assume numbers are in the range 1.. k

z The algorithm:

z Input: A[1..n], where A[j] {1, 2, 3, ..., k} z Output: B[1..n], sorted (not sorted in place) z Also: Array C[1..k] for auxiliary storage

Counting Sort

1

CountingSort(A, B, k)

2

for i=1 to k

3

C[i]= 0;

This is called

a histogram.

4

for j=1 to n

5

C[A[j]] += 1;

6

for i=2 to k

7

C[i] = C[i] + C[i-1];

8

for j=n downto 1

9

B[C[A[j]]] = A[j];

10

C[A[j]] -= 1;

Counting Sort Example

Counting Sort

1

CountingSort(A, B, k)

2

for i=1 to k

Takes time O(k)

3

C[i]= 0;

4

for j=1 to n

5

C[A[j]] += 1;

6

for i=2 to k

Takes time O(n)

7

C[i] = C[i] + C[i-1];

8

for j=n downto 1

9

B[C[A[j]]] = A[j];

10

C[A[j]] -= 1;

What is the running time?

Counting Sort

z Total time: O(n + k)

z Works well if k = O(n) or k = O(1)

z This algorithm / implementation is stable.

z A sorting algorithm is stable when numbers with the same values appear in the output array in the same order as they do in the input array.

Counting Sort

z Why don't we always use counting sort?

z Depends on range k of elements.

z Could we use counting sort to sort 32 bit integers? Why or why not?

Counting Sort Review

z Assumption: input taken from small set of numbers of size k

z Basic idea: z Count number of elements less than you for each element. z This gives the position of that number ? similar to selection sort.

z Pro's: z Fast z Asymptotically fast - O(n+k) z Simple to code

z Con's: z Doesn't sort in place. z Elements must be integers. countable z Requires O(n+k) extra storage.

Radix Sort

z How did IBM get rich originally? z Answer: punched card readers for

census tabulation in early 1900's.

z In particular, a card sorter that could sort cards into different bins

z Each column can be punched in 12 places z Decimal digits use 10 places

z Problem: only one column can be sorted on at a time

Radix Sort

z Intuitively, you might sort on the most significant digit, then the second msd, etc.

z Problem: lots of intermediate piles of cards (read: scratch arrays) to keep track of

z Key idea: sort the least significant digit first

RadixSort(A, d) for i=1 to d StableSort(A) on digit i

Radix Sort Example

Radix Sort Correctness

z Sketch of an inductive proof of correctness (induction on the number of passes):

z Assume lower-order digits {j: j ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download