CS计算机代考程序代写 AI algorithm ECE209_sorting2.pptx

ECE209_sorting2.pptx

ECE 209 Fall 2012 Sorting

10/24/12
  2
 

Quicksort: Big Picture

Choose a random element,
called the partitioning element, P.

Partition the array into two regions:

In one, all elements are smaller than P.
In the other, all elements are larger than P.

Element P goes in between,

which is its correct position in the sorted array.

Then (recursively) sort each of the two partitions.

ECE 209 Fall 2012 Sorting

10/24/12
  3
 

Quicksort: Big Picture

ECE 209 Fall 2012 Sorting

10/24/12
  4
 

Quicksort: Runtime Analysis

How many operations to sort an N-element array?

Let T(N) be operations to sort N elements.
Partition of N elements takes N-1 comparisons, N exch.
On avg, partition will divide the array into two equal parts.

T(N) ≈ N + 2T(N/2)

ECE 209 Fall 2012 Sorting

10/24/12
  5
 

Quicksort: Runtime Analysis

How many operations to sort an N-element array?

Let T(N) be operations to sort N elements.
Partition of N elements takes N-1 comparisons, N exch.
On avg, partition will divide the array into two equal parts.

T(N) ≈ N + 2T(N/2)

≈ N + 2(N/2 + 2T(N/4)) = 2N + 4T(N/4)

ECE 209 Fall 2012 Sorting

10/24/12
  6
 

Quicksort: Runtime Analysis

How many operations to sort an N-element array?

Let T(N) be operations to sort N elements.
Partition of N elements takes N-1 comparisons, N exch.
On avg, partition will divide the array into two equal parts.

T(N) ≈ N + 2T(N/2)

≈ N + 2(N/2 + 2T(N/4)) = 2N + 4T(N/4)
≈ 2N + 4(N/4 + 2T(N/8)) = 3N + 8T(N/8)

ECE 209 Fall 2012 Sorting

10/24/12
  7
 

Quicksort: Runtime Analysis

How many operations to sort an N-element array?

Let T(N) be operations to sort N elements.
Partition of N elements takes N-1 comparisons, N exch.
On avg, partition will divide the array into two equal parts.

T(N) ≈ N + 2T(N/2)

≈ N + 2(N/2 + 2T(N/4)) = 2N + 4T(N/4)
≈ 2N + 4(N/4 + 2T(N/8)) = 3N + 8T(N/8)

…repeated log2N times, until…

≈ (log2N)·N + 2log2N·T(1)
≈ Nlog2N + 2log2N
= O(NlogN)

ECE 209 Fall 2012 Sorting

10/24/12
  8
 

Is NlogN better than N2?
10000
 

664.39
 
0
 

2000
 

4000
 

6000
 

8000
 

10000
 

0
  10
  20
  30
  40
  50
  60
  70
  80
  90
  100
 

 
 N*N
 

 
 N*logN
 

ECE 209 Fall 2012 Sorting

10/24/12
  9
 

Quicksort: Algorithm

Given: a sequence, A, of n items (A1 to An)

If n = 1, exit (already sorted)

Let partition element P = An
Partition A according to P,

Let m = index of element P after partition

Perform Quicksort on sequence A1…Am-1
Perform Quicksort on sequence Am+1…An

ECE 209 Fall 2012 Sorting

10/24/12
  10
 

Quicksort: Code
int partition(Item a[], int left, int right);

void quicksort(Item a[], int left, int right) {
/* left is index of leftmost element,
right is index of rightmost element */
int m;
if (left >= right) return; /* termination condition */
/* partition and return index of partition element */
m = partition(a, left, right);

/* recursively sort sub-arrays */
quicksort(a, left, m-1);
quicksort(a, m+1, right);
return;
}

ECE 209 Fall 2012 Sorting

10/24/12
  11
 

Partition: Algorithm

Given: a sequence, A, of n items (A1 to An)

Let partition element P = An
Let i = 1, j = n-1
Repeat

Let i = index of leftmost element > P
Let j = index of rightmost element < P If i < j, exchange Ai and Aj Until i >= j
Exchange An with Ai (putting P in its correct place)
Return i

ECE 209 Fall 2012 Sorting

10/24/12
  12
 

Partition: Code
int partition(Item a[], int left, int right) {
int i = left-1, j = right;
Item p = a[right];
while (1) {
while (LESS(a[++i],p));
while (LESS(p,a[–j])) if (j == left) break;
if (i >= j) break;
EXCH(a[i],a[j]);
}
EXCH(a[i],a[right]);
return i;
}

ECE 209 Fall 2012 Sorting

10/24/12
  13
 

Quicksort Observations

O(N2) in the worst case.
For an array that’s already in sorted order, partition will divide the
array into a zero-element subarray and an (N-1)-element subarray.

How many activation records on stack?

Avg case — logN. Worst case — N.

Not very efficient for small arrays.

E.g., use selection sort when subarray becomes 10 elements or less.

ECE 209 Fall 2012 Sorting

10/24/12
  14
 

My Timing Experiment

Random
 
Order
 

Selec5on
 
Sort
 

12.8
 

Bubble
 
Sort
 

30.5
 

Quicksort
  0.015
 

array of 80,000 integers
times in seconds

ECE 209 Fall 2012 Sorting

10/24/12
  15
 

My Timing Experiment

Random
 
Order
 

In-­‐order
 

Selec5on
 
Sort
 

12.8
  12.6
 

Bubble
 
Sort
 

30.5
  0
 

Quicksort
  0.015
  crashed
 

array of 80,000 integers
times in seconds

ECE 209 Fall 2012 Sorting

10/24/12
  16
 

My Timing Experiment

Random
 
Order
 

In-­‐order
  Reverse-­‐
 
order
 

Selec5on
 
Sort
 

12.8
  12.6
  13.2
 

Bubble
 
Sort
 

30.5
  0
  29.5
 

Quicksort
  0.015
  crashed
  crashed
 

array of 80,000 integers
times in seconds