|
Two days to understand the ESSENCE?? I understand that there are a lot of details, and those can take a lot of time to master, but the essence should be really quick. To wit: 1. Merge sort. Given two sorted sequences, they can be merged in linear time. Given an algorithm that does so, we can sort a list in O(n log n) time, as follows: split the list into two equal halves, merge sort each half, and then merge the result. (The base case is that sorting lists of length 1 is really easy.) 2. Insertion sort. Let's say you want to sort in increasing order. To make things concrete, let's say your given list is [3, 1, 4, -1, 5, 9, 2, 6, -5, -3] You start by walking through the list: 3, 1, ... WAIT. That's not right, 1 should come before 3. Let's drag it to the front of the list where it belongs. We now have: [1, 3, 4, -1, 5, 9, 2, 6, -5, -3] Now we again walk through the list: 1, 3, 4, -1 ... WAIT. What's -1 doing here, let's drag it to the front of the line: [-1, 1, 3, 4, 5, 9, 2, 6, -5, -3] Again: -1, 1, 3, 4, 5, 9, 2, ... WAIT. What's 2 doing here, we need to drag it forward, but not all the way to the front: [-1, 1, 2, 3, 4, 5, 9, 6, -5, -3] And so on. Is this what you meant by essence? |