121 lines
2.1 KiB
Markdown
121 lines
2.1 KiB
Markdown
# Review 6
|
|
|
|
* Hajin Ju, 2024062806
|
|
|
|
## Problem 1
|
|
|
|
Illustrate the operation of `PARTITION` on the array $A = \set{2, 8, 7, 1, 3, 5, 6, 4}$
|
|
|
|
### Solution 1
|
|
|
|
```python {cmd output=html hide}
|
|
from __pyfunc__.r6 import *
|
|
from bs4 import BeautifulSoup
|
|
|
|
data = [2, 8, 7, 1, 3, 5, 6, 4]
|
|
hl = [0, 0, 0, 0, 0, 0, 1, 0]
|
|
|
|
print(
|
|
create_array_table(data,
|
|
[0, 0, 0, 0, 0, 0, 1, 0]
|
|
, 0, 0),
|
|
)
|
|
|
|
print(
|
|
create_array_table(data,
|
|
[1, 0, 0, 0, 0, 0, 1, 0],
|
|
1, 0)
|
|
)
|
|
|
|
print(
|
|
create_array_table(
|
|
[2, 8, 7, 1, 3, 5, 6, 4],
|
|
[1, 1, 0, 0, 0, 0, 1, 0],
|
|
1, 1)
|
|
)
|
|
|
|
print(create_array_table(
|
|
[2, 8, 7, 1, 3, 5, 6, 4],
|
|
[1, 0, 1, 0, 0, 0, 1, 0],
|
|
1, 2
|
|
))
|
|
|
|
print(create_array_table(
|
|
[2, 1, 7, 8, 3, 5, 6, 4],
|
|
[0, 1, 0, 1, 0, 0, 1, 0],
|
|
2, 2
|
|
))
|
|
|
|
print(create_array_table(
|
|
[2, 1, 3, 8, 7, 5, 6, 4],
|
|
[0, 0, 1, 0, 1, 0, 1, 0],
|
|
3, 2
|
|
))
|
|
|
|
print(create_array_table(
|
|
[2, 1, 3, 8, 7, 5, 6, 4],
|
|
[0, 0, 1, 0, 0, 1, 1, 0],
|
|
3, 3
|
|
))
|
|
|
|
print(create_array_table(
|
|
[2, 1, 3, 8, 7, 5, 6, 4],
|
|
[0, 0, 1, 0, 0, 0, 1, 0],
|
|
3, 4
|
|
))
|
|
|
|
print(create_array_table(
|
|
[2, 1, 3, 4, 7, 5, 6, 8],
|
|
[0, 0, 1, 1, 0, 0, 0, 1],
|
|
0, 0
|
|
))
|
|
|
|
```
|
|
|
|
## Problem 2
|
|
|
|
Answer questions about the following function `SELECT(A, p, r, i)` where $r-p + 1 = n$
|
|
|
|
```py
|
|
SELECT(A, p, r, i)
|
|
if p == r
|
|
return A[p]
|
|
q = PARTITION(A, p, r)
|
|
k = q - p + 1
|
|
if i == k
|
|
return A[q]
|
|
else if i < k
|
|
return SELECT(A, p, q - 1, i)
|
|
else
|
|
return SELECT(A, q + 1, r, i - k)
|
|
```
|
|
|
|
* What does it do?
|
|
* What is the worst-case running time?
|
|
* What is the best-case running time?
|
|
|
|
|
|
### Solution 2-a
|
|
|
|
`SELECT` selects `i`-th smallest element in the array `A`.
|
|
|
|
### Solution 2-b
|
|
|
|
The worst-case occurs when the `PARTITION` partitiend the array unbalanced.
|
|
|
|
So, time-complexity of the case is:
|
|
|
|
$$T(n) = T(n-1) + O(n)$$
|
|
|
|
$$\therefore T(n) = O(n^2)$$
|
|
|
|
### Solution 2-c
|
|
|
|
The best-case occurs when the `PARTITION` partitiend the array balanced, which means pivot is median.
|
|
|
|
So, time-complexity of the case is:
|
|
|
|
$$T(n) = T(0) + O(n)$$
|
|
|
|
$$\therefore T(n) = O(n)$$
|