Sorting algorithms

179. Largest Number

Solution

215. Kth Largest Element in an Array

# O(nlgn) time
def findKthLargest1(self, nums, k):
return sorted(nums, reverse=True)[k-1]

# O(nk) time, bubble sort idea, TLE
def findKthLargest2(self, nums, k):
for i in xrange(k):
for j in xrange(len(nums)-i-1):
if nums[j] > nums[j+1]:
# exchange elements, time consuming
nums[j], nums[j+1] = nums[j+1], nums[j]
return nums[len(nums)-k]

# O(nk) time, selection sort idea
def findKthLargest3(self, nums, k):
for i in xrange(len(nums), len(nums)-k, -1):
tmp = 0
for j in xrange(i):
if nums[j] > nums[tmp]:
tmp = j
nums[tmp], nums[i-1] = nums[i-1], nums[tmp]
return nums[len(nums)-k]

# O(k+(n-k)lgk) time, min-heap
def findKthLargest4(self, nums, k):
heap = []
for num in nums:
heapq.heappush(heap, num)
for _ in xrange(len(nums)-k):
heapq.heappop(heap)
return heapq.heappop(heap)

# O(k+(n-k)lgk) time, min-heap
def findKthLargest5(self, nums, k):
return heapq.nlargest(k, nums)[k-1]

# O(n) time, quick selection
def findKthLargest(self, nums, k):
# convert the kth largest to smallest
return self.findKthSmallest(nums, len(nums)+1-k)

def findKthSmallest(self, nums, k):
if nums:
pos = self.partition(nums, 0, len(nums)-1)
if k > pos+1:
return self.findKthSmallest(nums[pos+1:], k-pos-1)
elif k < pos+1:
return self.findKthSmallest(nums[:pos], k)
else:
return nums[pos]

# choose the right-most element as pivot
def partition(self, nums, l, r):
low = l
while l < r:
if nums[l] < nums[r]:
nums[l], nums[low] = nums[low], nums[l]
low += 1
l += 1
nums[low], nums[r] = nums[r], nums[low]
return low

Quickselect

Why quick select is O(n) if we have a perfect pivot chosen?

1/2+1/4+… = 1

When will we get the worst-case complexity for quickselect algorithm

function partition(list, left, right, pivotIndex) is
pivotValue := list[pivotIndex]
swap list[pivotIndex] and list[right] // Move pivot to end
storeIndex := left
for i from left to right − 1 do
if list[i] < pivotValue then
swap list[storeIndex] and list[i]
increment storeIndex
swap list[right] and list[storeIndex] // Move pivot to its final place
return storeIndex
// Returns the k-th smallest element of list within left..right inclusive
// (i.e. left <= k <= right).
function select(list, left, right, k) is
if left = right then // If the list contains only one element,
return list[left] // return that element
pivotIndex := ... // select a pivotIndex between left and right,
// e.g., left + floor(rand() % (right − left + 1))
pivotIndex := partition(list, left, right, pivotIndex)
// The pivot is in its final sorted position
if k = pivotIndex then
return list[k]
else if k < pivotIndex then
return select(list, left, pivotIndex − 1, k)
else
return select(list, pivotIndex + 1, right, k)

Direct translate pseudocode to C++ code

/*
Runtime: 16 ms, faster than 95.11% of C++ online submissions for Kth Largest Element in an Array.
Memory Usage: 10 MB, less than 96.23% of C++ online submissions for Kth Largest Element in an Array.
*/

class Solution {
public:
int partition(vector<int>& list, int left, int right,int pivot_index)
{
auto pivot_value = list[pivot_index];
swap(list[pivot_index], list[right]);
auto store_index = left;
for(int i=left; i<=right;++i)
{
if (list[i] < pivot_value)
{
swap(list[i], list[store_index++]);
}
}
swap(list[store_index], list[right]);
return store_index;
}

int select(vector<int>& list, int left, int right,int k)
{
if (left==right)return list[left];
auto pivot_index = left + rand()%(right - left + 1);
pivot_index = partition(list, left, right, pivot_index);
if (k==pivot_index)return list[pivot_index];
else if(k<pivot_index)
{
return select(list, left, pivot_index-1, k);
}
else
{
return select(list, pivot_index+1, right, k);
}

}
int findKthLargest(vector<int>& nums, int k)
{
return select(nums, 0, nums.size()-1, nums.size()-k);
}
};

148. Sort List

Reference

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Go: How to Take Advantage of the Symbols Table

Scraping from Wikipedia using Python and Selenium

Integrating LVM with Hadoop Cluster

Kernel Not Started — Python

Do you feel like you can’t handle the load?

How to Find the Right Software Development Company for Your Business

Zaio Research Project: Bootstrap

Go Serverless with AWS

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

How np.random.seed and np.random.randn works

Flatten a multi level DLL

Building an android application to control Tello drone flight and perform real-time object…

PyBlog — Profile