Java程序辅导

MIPS Assembly:
Quicksort
CptS 260
Introduction to Computer Architecture
Week 4.1
Mon 2014/06/30
This Week
• 06/30 Mon Quicksort (overview)
• 07/01 Tue Quicksort (partition, HW6)
• 07/02 Wed Review
– HW1 – HW5 Topics
– MIPS Simple Datapath
– MIPS Assembly
• Stack frame
• Function calling functions
• 07/03 Thu Midterm Exam
– In class
– Closed book (MIPS reference card will be attached)
Quicksort
• Yet Another Sorting Algorithm
– Hoare 1960
• “Best” average-case performance!
– Best case ~ O(n log n)
– On average, 1.39 × best-case
– worst-case ~ O(n2)
• Online Resources
– Wikipedia, “Quicksort”, Repeated elements
– www.sorting-algorithms.com/quick-sort-3-way
Quicksort: Implementation Overview
• A Confluence of “Big Concepts”
– Array (of integers)
– Pointers (to integer)
– Recursion
– MIPS multiple return values: $v0, $v1
• Divide and Conquer
– Works for any array sequence!
3 7 8 5 2 1 9 5 4A:
begin end
QUICKSORT( begin, end )
{
if (begin >= end) return;
p = PARTITION( begin, end );
QUICKSORT ( begin, p );
QUICKSORT ( p + 1, end );
}
DIVIDE-AND-CONQUER( b, e )
{
if (b >= e) return;
p = SPLIT ( b, e );
DIVIDE-AND-CONQUER ( b, p );
DIVIDE-AND-CONQUER ( p + 1, e );
}
First Hurdle: HW Interface and Conversions
• The HW Interface is Non-Negotiable
– Heed the HW PDFs!!
– Heed all MIPS conventions: $a*, $v*

 You May Make Your Own
Internal (Private) Interface
You Do The Conversion!
Grading Harness
test_n
∀ t:
HW PDF
$a0: int A[]
$a1: int len
$a0: int * lo = …
$a1: int * hi = …
3 7 8 5 2 1 9 5 4A:
Partition in Set Theory
• Set Theory / Ontology
– A disjoint covering
• Computer Science (algorithm)
– Given A set S
– and predicate P (function that returns true or false)
partition(S, P) = Strue Sfalse rearranges elements
returns: the midpoint ↑
HW6: Outline of Tasks quicksort ( a0: int A[]
, a1: int len )
your adapter here …
// returns nothing
swap ( a0: int *, a1: int *)
// exchanges *a0 and *a1
// returns $v0 == end of S=
partition( a0: word * lo
, a1: word * hi )
{ … }
// returns $v0 == start of S=
//       and $v1 == start of S>=
enlarge ( a0: int * mid )
{ … }
quicksort_ab ( a0: …
, a1: … )
{ … }
Quicksort: Three-Way (“Fat”) Partition
• HW6 Requirements
– Partition handles base cases
– Two return values: $v0, $v1
• Many partition algorithms
– One write pointer (Wikipedia)
– Two-pointer swap
– Two write pointers
– Your Idea Here …
Wikipedia:
One read “pointer”, One write “pointer”
• http://en.wikipedia.org/wiki/Quicksort, In-place version
// Returns the pivot index
int partition(A, left, right)
int pivot := A[right]
// Move pivot to end
//  swap A[pi], A[right]
int wr := left
for i = left to right – 1
if A[i] <= pivot
swap A[i], A[wr]
++wr
// Move pivot to middle
swap A[wr], A[right]
return wr
3 7 8 5 2 1 9 5 4
i
wr
left right
Three-Way Partition using Two-Pointer Swap:
Swapping the Pivot
while (lo < hi)
{
// seek left
while (*lo <= pivot) ++lo;
// seek right
while (*hi >= pivot) ––hi;
// exchange
swap(lo++, hi ––);
}
// move pivot to end of S=
swap(last, lo);
3 7 8 5 2 1 9 5
lo hi
4
1 7
2 8
3 1 2 5 8 7 9 5 4
brute{sort,part}.asm – Output
brutesort.asm – Pretty Printing
void endl (void) # print_char(‘\n’)
void print_int ($a0 : a) # “a ” (with trailing space)
void print_array_int # “a0 a1 … ae ”  (with trailing space)
($a0 = int A[], $a1 = int * E) # in half-open interval [A, E)
void print_array_withz # “a0 … ae | z0 … ze \n”
( $a0 = int A[]
, $a1 = int len
, $a2 = int lenz)
len
lenz
void brutesort_ettu # struct TestCase { int len; int A[]; };
($a0 = TestCase * T) # prints T–>A[] (before)
# quicksort(T–>len, T–>A[])
# prints T–>A[] (after)
Swapping the Pivot:
Enumerating Some Cases
• Contributing factors (?):
– Array parity: even odd
– Middle element (if odd) < p ==p > p
– Degenerate cases: lo-fails hi-fails
Swapping the Pivot:
Ascending, Descending
oddeven
1 2 3 5 6
lo
hi
4 1 2 5 6
lo
hi
4
swap to
swap(last, lo);
6 8 9 2 1 4 6 8 2 1 4
Ascending
Descending
Swapping the Pivot:
One Pointer Fails
oddeven
1 2 3 2 1
lo
hi
4 1 2 3 2
lo
hi
4
swap to
lo-fails
9 8 7 5 6
lo
hi
4 8 8 5 6
lo
hi
4hi-fails
1 n
# 3-way partition
i = 1, k = 1, p = n
while i < p
if A[i] < A[n] swap A[i++, k++]
else if A[i] == A[n] swap A[i, --p]
else i++
end
→ invariant: A[p .. n] all equal
→ invariant:
A[1..k-1] < A[p .. n] < A[k..p-1]
# move pivots to center
m = min(p-k, n-p+1)
swap A[k .. k+m-1, n-m+1 .. n]
# recursive sorts
sort A[1, k-1]
sort A[n-p+k+1, n]
3-Way Partition:
Two Write Pointers
• www.sorting-algorithms.com/quick-sort-3-way
– Pascal-like array notation: [1 .. n]
# choose pivot
# swap A[n, rand(1,n)]
i
k p
3 4 7 8 5 2 4 1 9 5 4 4
1 n
# 3-way partition
i = 1, k = 1, p = n
while i < p
if A[i] < A[n] swap A[i++, k++]
else if A[i] == A[n] swap A[i, --p]
else i++
end
→ invariant: A[p .. n] all equal
→ invariant:
A[1..k-1] < A[p .. n] < A[k..p-1]
# move pivots to center
m = min(p-k, n-p+1)
swap A[k .. k+m-1, n-m+1 .. n]
# recursive sorts
sort A[1, k-1]
sort A[n-p+k+1, n]
3-Way Partition:
Two Write Pointers
i
k p
3 4 7 8 5 2 4 1 9 5 4 4
1 n
# 3-way partition
i = 1, k = 1, p = n
while i < p
if A[i] < A[n] swap A[i++, k++]
else if A[i] == A[n] swap A[i, --p]
else i++
end
→ invariant: A[p .. n] all equal
→ invariant:
A[1..k-1] < A[p .. n] < A[k..p-1]
# move pivots to center
m = min(p-k, n-p+1)
swap A[k .. k+m-1, n-m+1 .. n]
# recursive sorts
sort A[1, k-1]
sort A[n-p+k+1, n]
3-Way Partition:
Two Write Pointers
i
k p
3 4 7 8 5 2 4 1 9 5 4 4
4
4
5
4
1 n
# 3-way partition
i = 1, k = 1, p = n
while i < p
if A[i] < A[n] swap A[i++, k++]
else if A[i] == A[n] swap A[i, --p]
else i++
end
→ invariant: A[p .. n] all equal
→ invariant:
A[1..k-1] < A[p .. n] < A[k..p-1]
# move pivots to center
m = min(p-k, n-p+1)
swap A[k .. k+m-1, n-m+1 .. n]
# recursive sorts
sort A[1, k-1]
sort A[n-p+k+1, n]
3-Way Partition:
Two Write Pointers
i
k p
3 5 7 8 5 2 4 1 9 4 4 4
i
k p
3 4 7 8 5 2 4 1 9 5 4 4
4
4
5
4
1 n
# 3-way partition
i = 1, k = 1, p = n
while i < p
if A[i] < A[n] swap A[i++, k++]
else if A[i] == A[n] swap A[i, --p]
else i++
end
→ invariant: A[p .. n] all equal
→ invariant:
A[1..k-1] < A[p .. n] < A[k..p-1]
# move pivots to center
m = min(p-k, n-p+1)
swap A[k .. k+m-1, n-m+1 .. n]
# recursive sorts
sort A[1, k-1]
sort A[n-p+k+1, n]
3-Way Partition:
Two Write Pointers
i
k p
3 5 7 8 5 2 4 1 9 4 4 4
2 4
5 9 7
1
i
k p
3 2 1 8 5 5 9 7 4 4 4 4
1 n
# 3-way partition
i = 1, k = 1, p = n
while i < p
if A[i] < A[n] swap A[i++, k++]
else if A[i] == A[n] swap A[i, --p]
else i++
end
→ invariant: A[p .. n] all equal
→ invariant:
A[1..k-1] < A[p .. n] < A[k..p-1]
# move pivots to center
m = min(p-k, n-p+1)
swap A[k .. k+m-1, n-m+1 .. n]
# recursive sorts
sort A[1, k-1] # A[01, 03]
sort A[n-p+k+1, n] # A[08, 12]
3-Way Partition:
Two Write Pointers
i
k p
3 2 1 8 5 5 9 7 4 4 4 4
# min(12 – 4, 12 – 8 + 1) = 5
# A[4 .. 8, 8 .. 12]
3 2 1 4 4 4 4 7 9 5 5 8
3 4 7 8 5 2 4 1 9 5 4 4
$v0 $v1