Algorithms
ROBERT SEDGEWICK | KEVIN WAYNE
Algorithms FOURTH EDITION
ROBERT SEDGEWICK | KEVIN WAYNE
Copyright By PowCoder代写 加微信 powcoder
http://algs4.cs.princeton.edu
2.3 PARTITIONING DEMOS
‣ Sedgewick 2-way partitioning
‣ Dijkstra 3-way partitioning
‣ Bentley-McIlroy 3-way partitioning ‣ dual-pivot partitioning
Algorithms
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
2.3 PARTITIONING DEMOS
‣ Sedgewick 2-way partitioning
‣ Dijkstra 3-way partitioning
‣ Bentley-McIlroy 3-way partitioning ‣ dual-pivot partitioning
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
stop i scan because a[i] >= a[lo]
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
stop j scan and exchange a[i] with a[j]
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
stop i scan because a[i] >= a[lo]
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
stop j scan and exchange a[i] with a[j]
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
stop i scan because a[i] >= a[lo]
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
stop j scan and exchange a[i] with a[j]
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
stop i scan because a[i] >= a[lo]
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
stop j scan because a[j] <= a[lo]
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
When pointers cross.
・Exchange a[lo] with a[j].
pointers cross: exchange a[lo] with a[j]
Quicksort partitioning demo
Repeat until i and j pointers cross.
・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[j] > a[lo]). ・Exchange a[i] with a[j].
When pointers cross.
・Exchange a[lo] with a[j].
partitioned!
Algorithms
ROBERT SEDGEWICK | KEVIN WAYNE
http://algs4.cs.princeton.edu
2.3 PARTITIONING DEMOS
‣ Sedgewick 2-way partitioning
‣ Dijkstra 3-way partitioning
‣ Bentley-McIlroy 3-way partitioning ‣ dual-pivot partitioning
Dijkstra 3-way partitioning demo
・Let v be partitioning item a[lo]. ・Scan i from left to right.
(a[i] < v): exchange a[lt] with a[i]; increment both lt and i (a[i] > v): exchange a[gt] with a[i]; decrement gt
(a[i] == v): increment i
before v invariant
Dijkstra 3-way partitioning demo
・Let v be partitioning item a[lo]. ・Scan i from left to right.
(a[i] < v): exchange a[lt] with a[i]; increment both lt and i (a[i] > v): exchange a[gt] with a[i]; decrement gt
(a[i] == v): increment i
before v invariant
Dijkstra 3-way partitioning demo
・Let v be partitioning item a[lo]. ・Scan i from left to right.
(a[i] < v): exchange a[lt] with a[i]; increment both lt and i (a[i] > v): exchange a[gt] with a[i]; decrement gt
(a[i] == v): increment i
before v invariant
Dijkstra 3-way partitioning demo
・Let v be partitioning item a[lo]. ・Scan i from left to right.
(a[i] < v): exchange a[lt] with a[i]; increment both lt and i (a[i] > v): exchange a[gt] with a[i]; decrement gt
(a[i] == v): increment i
before v invariant
Dijkstra 3-way partitioning demo
・Let v be partitioning item a[lo]. ・Scan i from left to right.
(a[i] < v): exchange a[lt] with a[i]; increment both lt and i (a[i] > v): exchange a[gt] with a[i]; decrement gt
(a[i] == v): increment i
before v invariant
Dijkstra 3-way partitioning demo
・Let v be partitioning item a[lo]. ・Scan i from left to right.
(a[i] < v): exchange a[lt] with a[i]; increment both lt and i (a[i] > v): exchange a[gt] with a[i]; decrement gt
(a[i] == v): increment i
before v invariant
Dijkstra 3-way partitioning demo
・Let v be partitioning item a[lo]. ・Scan i from left to right.
(a[i] < v): exchange a[lt] with a[i]; increment both lt and i (a[i] > v): exchange a[gt] with a[i]; decrement gt
(a[i] == v): increment i
before v invariant
Dijkstra 3-way partitioning demo
・Let v be partitioning item a[lo]. ・Scan i from left to right.
(a[i] < v): exchange a[lt] with a[i]; increment both lt and i (a[i] > v): exchange a[gt] with a[i]; decrement gt
(a[i] == v): increment i
before v invariant
Dijkstra 3-way partitioning demo
・Let v be partitioning item a[lo]. ・Scan i from left to right.
(a[i] < v): exchange a[lt] with a[i]; increment both lt and i (a[i] > v): exchange a[gt] with a[i]; decrement gt
(a[i] == v): increment i
before v invariant
Dijkstra 3-way partitioning demo
・Let v be partitioning item a[lo]. ・Scan i from left to right.
(a[i] < v): exchange a[lt] with a[i]; increment both lt and i (a[i] > v): exchange a[gt] with a[i]; decrement gt
(a[i] == v): increment i
before v invariant
after
Dijkstra 3-way partitioning demo
・Let v be partitioning item a[lo]. ・Scan i from left to right.
(a[i] < v): exchange a[lt] with a[i]; increment both lt and i (a[i] > v): exchange a[gt] with a[i]; decrement gt
(a[i] == v): increment i
before v invariant
after
Dijkstra 3-way partitioning demo
・Let v be partitioning item a[lo]. ・Scan i from left to right.
(a[i] < v): exchange a[lt] with a[i]; increment both lt and i (a[i] > v): exchange a[gt] with a[i]; decrement gt
(a[i] == v): increment i
before v invariant
after
Dijkstra 3-way partitioning demo
・Let v be partitioning item a[lo]. ・Scan i from left to right.
(a[i] < v): exchange a[lt] with a[i]; increment both lt and i (a[i] > v): exchange a[gt] with a[i]; decrement gt
(a[i] == v): increment i
before v invariant
after
Dijkstra 3-way partitioning demo
・Let v be partitioning item a[lo]. ・Scan i from left to right.
(a[i] < v): exchange a[lt] with a[i]; increment both lt and i (a[i] > v): exchange a[gt] with a[i]; decrement gt
(a[i] == v): increment i
before v invariant
after
(a[i] == v): increment i
before v invariant
after
Dijkstra 3-way partitioning demo
・Let v be partitioning item a[lo]. ・Scan i from left to right.
(a[i] < v): exchange a[lt] with a[i]; increment both lt and i (a[i] > v): exchange a[gt] with a[i]; decrement gt
(a[i] == v): increment i
before v invariant
after
・If (a[i] == a[lo]), exchange a[i] with a[p] and increment p. ・If (a[j] == a[lo]), exchange a[j] with a[q] and decrement q.
Bentley-McIlroy 3-way partitioning demo
Phase I. Repeat until i and j pointers cross. ・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[i] > a[lo]). ・Exchange a[i] with a[j].
・If (a[i] == a[lo]), exchange a[i] with a[p] and increment p. ・If (a[j] == a[lo]), exchange a[j] with a[q] and decrement q.
Bentley-McIlroy 3-way partitioning demo
Phase I. Repeat until i and j pointers cross. ・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[i] > a[lo]). ・Exchange a[i] with a[j].
・If (a[i] == a[lo]), exchange a[i] with a[p] and increment p. ・If (a[j] == a[lo]), exchange a[j] with a[q] and decrement q.
Bentley-McIlroy 3-way partitioning demo
Phase I. Repeat until i and j pointers cross. ・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[i] > a[lo]). ・Exchange a[i] with a[j].
・If (a[i] == a[lo]), exchange a[i] with a[p] and increment p. ・If (a[j] == a[lo]), exchange a[j] with a[q] and decrement q.
Bentley-McIlroy 3-way partitioning demo
Phase I. Repeat until i and j pointers cross. ・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[i] > a[lo]). ・Exchange a[i] with a[j].
・If (a[i] == a[lo]), exchange a[i] with a[p] and increment p. ・If (a[j] == a[lo]), exchange a[j] with a[q] and decrement q.
exchange a[i] with a[j]
Bentley-McIlroy 3-way partitioning demo
Phase I. Repeat until i and j pointers cross. ・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[i] > a[lo]). ・Exchange a[i] with a[j].
・If (a[i] == a[lo]), exchange a[i] with a[p] and increment p. ・If (a[j] == a[lo]), exchange a[j] with a[q] and decrement q.
Bentley-McIlroy 3-way partitioning demo
Phase I. Repeat until i and j pointers cross. ・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[i] > a[lo]). ・Exchange a[i] with a[j].
・If (a[i] == a[lo]), exchange a[i] with a[p] and increment p. ・If (a[j] == a[lo]), exchange a[j] with a[q] and decrement q.
Bentley-McIlroy 3-way partitioning demo
Phase I. Repeat until i and j pointers cross. ・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[i] > a[lo]). ・Exchange a[i] with a[j].
・If (a[i] == a[lo]), exchange a[i] with a[p] and increment p. ・If (a[j] == a[lo]), exchange a[j] with a[q] and decrement q.
exchange a[i] with a[j]
Bentley-McIlroy 3-way partitioning demo
Phase I. Repeat until i and j pointers cross. ・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[i] > a[lo]). ・Exchange a[i] with a[j].
・If (a[i] == a[lo]), exchange a[i] with a[p] and increment p. ・If (a[j] == a[lo]), exchange a[j] with a[q] and decrement q.
exchange a[i] with a[p] and increment p
Bentley-McIlroy 3-way partitioning demo
Phase I. Repeat until i and j pointers cross. ・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[i] > a[lo]). ・Exchange a[i] with a[j].
・If (a[i] == a[lo]), exchange a[i] with a[p] and increment p. ・If (a[j] == a[lo]), exchange a[j] with a[q] and decrement q.
Bentley-McIlroy 3-way partitioning demo
Phase I. Repeat until i and j pointers cross. ・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[i] > a[lo]). ・Exchange a[i] with a[j].
・If (a[i] == a[lo]), exchange a[i] with a[p] and increment p. ・If (a[j] == a[lo]), exchange a[j] with a[q] and decrement q.
Bentley-McIlroy 3-way partitioning demo
Phase I. Repeat until i and j pointers cross. ・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[i] > a[lo]). ・Exchange a[i] with a[j].
・If (a[i] == a[lo]), exchange a[i] with a[p] and increment p. ・If (a[j] == a[lo]), exchange a[j] with a[q] and decrement q.
exchange a[i] with a[j]
Bentley-McIlroy 3-way partitioning demo
Phase I. Repeat until i and j pointers cross. ・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[i] > a[lo]). ・Exchange a[i] with a[j].
・If (a[i] == a[lo]), exchange a[i] with a[p] and increment p. ・If (a[j] == a[lo]), exchange a[j] with a[q] and decrement q.
exchange a[j] with a[q] and decrement q
Bentley-McIlroy 3-way partitioning demo
Phase I. Repeat until i and j pointers cross. ・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[i] > a[lo]). ・Exchange a[i] with a[j].
・If (a[i] == a[lo]), exchange a[i] with a[p] and increment p. ・If (a[j] == a[lo]), exchange a[j] with a[q] and decrement q.
Bentley-McIlroy 3-way partitioning demo
Phase I. Repeat until i and j pointers cross. ・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[i] > a[lo]). ・Exchange a[i] with a[j].
・If (a[i] == a[lo]), exchange a[i] with a[p] and increment p. ・If (a[j] == a[lo]), exchange a[j] with a[q] and decrement q.
Bentley-McIlroy 3-way partitioning demo
Phase I. Repeat until i and j pointers cross. ・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[i] > a[lo]). ・Exchange a[i] with a[j].
・If (a[i] == a[lo]), exchange a[i] with a[p] and increment p. ・If (a[j] == a[lo]), exchange a[j] with a[q] and decrement q.
exchange a[i] with a[j]
Bentley-McIlroy 3-way partitioning demo
Phase I. Repeat until i and j pointers cross. ・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[i] > a[lo]). ・Exchange a[i] with a[j].
・If (a[i] == a[lo]), exchange a[i] with a[p] and increment p. ・If (a[j] == a[lo]), exchange a[j] with a[q] and decrement q.
exchange a[i] with a[p] and increment p
Bentley-McIlroy 3-way partitioning demo
Phase I. Repeat until i and j pointers cross. ・Scan i from left to right so long as (a[i] < a[lo]). ・Scan j from right to left so long as (a[i] > a[lo]). ・Exchange a[i] with a[j].
・If (a[i] == a[lo]), exchange a[i] with a[p] and increment p. ・If (a[j] == a[lo]), exchange a[j] with a[q] and decrement q.
exchange a[j] with a[q] and decrement q
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com