First, I read the article about this algorithm related to partition, (in Chinese) - May 6, 2015
and then, find similar article to read later:
February 2, 2016
Julia reviewed the quick sort algorithm, and then, practice the C# code to write partition:
Quick sort algorithm writing in C# - less than 20 minutes (18 minutes to write the code with comments)
1. First, using partition, and then, divide and conquer, use recursive function calls to solve the problem.
Most important technique, is to design a partition - 2-way partition, how to design the partition, choose pivot point, and how to do partition step by step.
Let us work on a simple example and have discussion, show the procedure of partition.
Let us say that array 1, 2, 3, 4, 5, 6, sorted
and then, we like to derive the above sorted array using this one, 1, 3, 2, 5, 4, 6
The idea of pivot position, is to choose last number in the array, for example, choose last one in the array, 6,
the position of pivot point, left side <= 6, right side > 6
So, do you see the problem, 6 is not ideal case.
Let us work on another order: 1, 6, 2, 5, 4, 3,
Overview of test case design 1, 6, 2, 5, 4, 3:
Tips:
left partition: 2 values, right partition 3 values, partition only needs two swaps, first swap for left partition, second one is for pivot point positioning. <- remember my choice, design test case. Julia tried to make her test case easy to follow.
So, this way, the test case is set up to demo the algorithm clearly and efficient enough.
Overview of test case design 1, 6, 2, 5, 4, 3:
Tips:
left partition: 2 values, right partition 3 values, partition only needs two swaps, first swap for left partition, second one is for pivot point positioning. <- remember my choice, design test case. Julia tried to make her test case easy to follow.
So, this way, the test case is set up to demo the algorithm clearly and efficient enough.
work on last one in the array, 3, using it as pivot: 1, 2 left side,
6, 5, 4 right side; and then, put the pivot point in-between, leave as is, left/ right side goes to subproblem, use recursive call.
Use a diagram to show progress:
current <- iterate from start - 0 to last one - right -1, leave A[right] for pivot point
another pointer -> mark first node > pivot point value 3, s
So, two pointers, one is moving to iterate whole array except last one - pivot point.
Second one is to mark the position of first node > pivot value, let us call it end.
After review, two pointers will mark the right partition:
right side start and end position.
6 5 4
end - 2
current - 4 // not 5, start from 0
left partition:
left -> end -1
Does this tip help to program? Relax a little bit.
Julia's practice:
No comments:
Post a Comment