Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- The code works in 3 steps:
- 1) comparision: compare neighbor elements array[j] and array[j+1], if array[j] <= array[j+1] move on, else goto 2.
- 2) find insertion point: now if array[j] > array[j+1], scan backwards to find the point where array[x] < array[j+1] <= array[x+1] for x < j (obviously only until x hits the start)
- 3) insert: shift elements x+1 ... j one up such that it becomes x+2 ... j+1 and insert former element at position x+1
- If you apply that code to the pairings (2-1, 2-3, 1-3, 2-4, 3-4, 2-2, 2-1, 2-1, 4-1, 3-1, 1-1, 2-2) it gets obvious what the code does.
- -- [2,1],3,4,2,1,2 -> 1./2./3. compare [2,1], find and insert 1 before 2
- -- 1,[2,3],4,2,1,2 -> 1./2. compare [2,3], find insert point for 3 (since order of 3 < order of 2)
- -- [1,3],2,4,2,1,2 -> 3. compare [1,3], found insert point for 3 before 2
- -- 1,3,[2,4],2,1,2 -> 1./2. compare [2,4], find insert point for 4 (since order of 4 < order of 2)
- -- 1,[3,4],2,2,1,2 -> 3. compare [3,4], found insert point for 4 before 2
- -- 1,3,4,[2,2],1,2 -> 1. compare [2,2], skip
- -- 1,3,4,2,[2,1],2 -> 1./2. compare [2,1], find insert point for 1
- -- 1,3,4,[2,1],2,2 -> 2. compare [2,1], find insert point for 1
- -- 1,3,[4,1],2,2,2 -> 2. compare [4,1], find insert point for 1
- -- 1,[3,1],4,2,2,2 -> 2. compare [3,1], find insert point for 1
- -- [1,1],3,4,2,2,2 -> 3. compare [1,1], fond insert point for 1 before 3
- -- 1,1,3,4,2,[2,2] -> 1. compare [2,2], skip
- -- sorted: 1,1,3,4,2,2,2
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement