jeremymanning.md

Problem 912: Sort an Array

Initial thoughts (stream-of-consciousness)

• My first thought was that we could just return sorted(nums)
• But...I'm seeing that we're supposed to solve this with no built in functions. They want an algorithm with $O(n \log n)$ time complexity and "the smallest space complexity possible," which would be $O(1)$ space. Off the top of my head, I remember a few sorting algorithms:
  • Bubble sort, which has $O(n^2)$ time complexity and $O(1)$ space complexity-- so it's out, because time complexity is too poor
  • Merge sort, which I believe has $O(n \log n)$ time complexity and...maybe $O(n)$ space complexity?
  • Quick sort, which I think also has $O(n \log n)$ time complexity and $O(n)$ space complexity
• So none of these are going to work. We need something with $O(n \log n)$ time complexity and $O(1)$ space complexity.
• I'm just going to look up a list of sorting algorithms. I found a list here:

Refining the problem, round 2 thoughts

• It looks like what we need is heapsort. Other than remembering that I've learned about heapsort at some point (e.g., I remember the name) I have absolutely no recollection of how it works. I'm guessing we need to build a heap (though I can't remember how to do this). And I think the "point" of a heap is that as you "pop" from a heap you always get the maximum (for a max heap) or minimum (for a min heap) value, so sorting is just a matter of "heapifying" the list and then popping from it until all elements are gone. But I'm going to need to look up how to implement this. From Wikipedia:

• Ok...so let's turn this into Python!
  • Note 1: I'll replace a with nums and compute count as len(nums) rather than passing it in as input; otherwise I'll do a straight copy of the pseudocode.
  • Note 2: In the same Wikipedia page, the iLeftChild function is defined as follows (so I'll write this up too):

Attempted solution(s)

classSolution: defsortArray(self, nums: List[int]) ->List[int]: defiLeftChild(i): return2*i+1count=len(nums) start=count//2end=countwhileend>1: ifstart>0: # Heap constructionstart-=1else: # Heap extractionend-=1nums[end], nums[0] =nums[0], nums[end] # SiftDown(nums, start, end)root=startwhileiLeftChild(root) <end: child=iLeftChild(root) ifchild+1<endandnums[child] <nums[child+1]: child+=1ifnums[root] <nums[child]: nums[root], nums[child] =nums[child], nums[root] root=childelse: breakreturnnums

• Given test cases pass
• I'm just going to submit...

• Out of curiosity, how much better is the "built-in" version?

classSolution: defsortArray(self, nums: List[int]) ->List[int]: returnsorted(nums)

Well then...