Arrays Flashcards
How to make a read-only BST from an array?
Just sort it you dummy (probably w/ quicksort to save on memory). You don’t need an extra data structure for a read-only BST. You just use a sorted array and use indices logic to search
what is regarded by many as the go to sorting algorithm of choice for large enough inputs?
a randomized version of quicksort
The 2 ways to randomize quicksort?
by randomizing the input (e.g. permute by sorting, which however takes nlogn time if using comparison sort), OR better yet, by randomized sampling (e.g. choosing random index for the pivot element)
Quick sort
Quicksort(A,p,r) {
if (r - p <= 0) return // length is one element or less and thus is sorted
q=partition(A,p,r)
quicksort(A,p,q-1)
quicksort(A,q+1, r)
}
partition(A,p,r){
let i =p-1
for(let j = p; j < r; j++) {
if(A[j] < A[r]) swap(A, ++i, j) // if current element we are processing x (at pos j) is less than the pivot element, expand the bounds of the lower section from [p, i] to [p, i' = i + 1] such that it is now overlapping with one element y ( which is >= A[r]) (at pos i') of the greater section, and swap x and y such that when greater section's range becomes become (i', j' = j + 1) after the increment statement in the for loop, A[j] = contains y which used to be located at A[i'
swap(A, i+1,j)
return i+1
}
//at the start of each iteration of the loop [p, i] represents less than section. (i, j) represents >=section. j is not yet processed so [j, r) represents unprocessed section. [r, r] represents the pivot element.
Swap(A, a, b) {
let x = A[a]
A[a] = A[b]
A[b] = x
}
How to randomize quicksort with random sampling?
RandomizedPartition(A,p,r){
i = Math.floor(Math.random() * (r-p+1)) + p
swap(A, i, r)
return partition (A, p, r)
}
RandomizedQuicksort(A, p, r){
q = randomizedPartition(A,p,r)
RandomizedQuicksort(A, p, q-1)
RandomizedQuicksort (A, q+1, r)
RandomizedQuicksort from scratch?
RandomizedPartition(A,p, r) {
k = Math.floor(Math.random() * (r - p + 1) + p)
Swap(A, k, r)
i =p-1
For (let j=p; j < r; j++) {
if(A[j] < A[r]) {
swap(A,++i, j)
}
}
swap(A, i+1, r)
return i + 1 //
}
Proof of randomized select being linear for expected time
high level version: Even though quicksort expected time is nlgn, randomized select is n because we recursively partition on just one side of the array and not both sides.
low level version:
Fundamental differences between nlogn sorting, linear sorting, and linear selection
nlgn sorting takes nlgn time bc it uses the comparison model, linear sorting achieves linearity by making assumptions about the input, linear selection achieves linearity by avoiding sorting
randomizedSelect
randomizedSelect(A,p,r, i) [Select the ith smallest element of the range A[p..r] where p is the 1st element (as opposed to 0th)]
q = randomizedPartition(A,p,r)
k = q - p + 1 // k=the # of elements in the red partition + the pivot element. this also means the last element (pivot element) in this range is the kth element in this range [p, q], because there are k elements in this range. // we know the pivot element @ pos q is in a spot such that it would be in the correct sorted spot in the entire array. // if i happens to be k, then we already know what the kth element is (A[q]) so we can just return that
if i ==k return A[q] if (i < k) return randomizedSelect(A, p, q- 1, i) else return randomizedSelect(A, q+ 1, r, i - k) //because we've already eliminated the first k elements as candidates
Partition, but with partition element as an input parameter
Partition(A, p, r, x) {// used in selection in worst case linear time algorithm
let i =p-1; for (let j=p; j
Select the ith element in worst case linear time
- Split the array into floor(n/5) groups of size of 5 ( and perhaps one group which may have size less than 5)
- Find the median of each of the groups, by first insertion sorting each group, and then selecting the median
- Use SELECT to recursively find the median of the ceil(n/5) medians. By convention if there are an even number of medians (meaning we could have two median of medians), we will choose the lower median of medians
- Partition the input array around the median of medians by using the modified version of partition that can take an element to partition around as a partition element
- Let k be one more than number of elements on the low side of the partition such that x is at the kth position, and there are n-k elements on the high side of the partition. If i=k return x , because Partition (particularly the swap after the for loop) guarantees that the partition element is always in it’s sorted spot . Otherwise use Select recursively to find the ith smallest element on the low side if i < k, or the (i-k)th smallest element on the high side if i > k lol
Select in worst case linear time
High level:
Like randomized-select the algorithm SELECT finds the desired element by recursively partitioning the input array. Here, however, we guarantee a good split upon partitioning the array
Proof of time for worst case linear select
Steps 1,2,4 are linear time.
Step 3 is T(n/5)
Step 5: to analyze running time of select, we must first determine the lower bound on # of elements that are greater than the partitioning element x. We know at least half the groups (minus perhaps the last one with <5 elements and the one containing x itself) have medians greater than c and therefore have >=3 elements greater than x. Therefore >= 3 * (1/2*ceil(n/5) - 2) elements are greater than x. Which is 3n/10 - 6. Thus worst case step 5 calls select recursively on 7n/10 + 6 elements (though I think it should be 7n/10 + 5 bc you should exclude x but who cares).
Assume when n <140, T(n) = O(n). Else T(n) <= T(n/5) + T(7n/10 + 6) + O(n)
We’ll
Java ArrayStack
A Stack implemented with an ArrayList . All stack operations are in O(1) time
Dynamic array
is a random access, variable-size list data structure that allows elements to be added or removed.
