quicksort: a practice makes difference

February 2, 2016

Introduction

Julia likes to work on basic things on algorithm problem solving, like brute force solution, recursive function design, divide and conquer solution, partitioning; So, she can write code everyday on algorithm.

Review the quicksort algorithm, and then, practice using C# programming language. So many times Julia went through the review of quick sort algorithm, but to write it in less than 10 minutes, without a bug, without stress, takes more dedicated effort - maybe write a blog to share will help.   

Julia likes to rewrite the above paragraph in April 9, 2018.

Quicksort warmup

First review the blog - the quick algorithm written in Java programming language. Julia must like the idea of choosing pivot value - "// simple version - pick the right most value as the pivot ". As a sports programmer, Julia knows that the power of using a simple test case, she likes to do it here. 

Let us describe how quick sort works: - explain it using 5 minutes - 10 minutes to write the code 

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.

One of ideas to choose pivot position, is to choose last number in the array.  For the 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. No swap, second partition with 0 values; in other words, all values go to first partition. 

Two way partition

Let us work on another order: 1, 6, 2, 5, 4, 3, 

1. Choose pivot value - last element in the array, value 3
2. Work on partition the array, left partition <= 3, right partition > 3
3. Two partitions are 1, 2, 6, 5, 4, 3

4. Put the pivot point in-between, 1, 2, 3,  6, 5, 4
5. Divide and conquer, solve two small subproblems, use recursive call. 

Use a diagram to show progress:      

Scan the array once from left to right, and then keep track of the start position of right partition. Anything less than 3 will be in left partition.  

The easy way to remember is to find right partition's start position. 

Two way partition - test case

1, 2, 6, 5, 4, 3  -> move pivot value 3 between two partitions

1, 2, 3,  6, 5, 4

Step by step, 

first, after partitioning, the array is the following:

1, 2, 6, 5, 4, 3 

so right side partition starting from array's index value 2 to 4, values are highlighted in background color of green. 

Left side partition:

1  2

left partition, array's index is from 0 to 1. 

Right side partition -  start and end position. 

6 5 4 

right partition, array's index is from 2 to 4. 

And then the pivot value 3 is inserted in-between left partition and right partition. 

1, 2, 3,  6, 5, 4

Let us recap what we practice here, go over a simple test case, and then choose a pivot value, and then partition, divide and conquer, go to solve two small problems using recursive calls. 

Julia's practice:

Quick sort algorithm writing in C# - less than 20 minutes (18 minutes to write the code with comments)

2nd practice using C# 

Quicksort Lecture Study

Julia, spend one hours to read the webpage, and enjoy the great lecture. Reading is much important than coding. And then, work on some questions in the lecture.

princeton lecture notes

Questions and Answers

February 3, 2016

After reading her favourite lecture notes, Julia likes to respond something to entertain quicksort algorithm practice, put something together with her own thinking based on discussion from reading material:

Fact 1:
Q1. Quick sort algorithm will work even in worst case, no dead loop. Why? 
Arguments:
1. Each recursive function, at least one value is resolved, no more work for the value. That is pivot point. So, at most, each recursive call solves one value, n recursive call will solve all n values in the array. Is it fun to design the algorithm? Yes.

Q2. Quicksort function design - only solve one value to position correctly, in the whole array. This is not efficient? 
Arguments:
1. This is the fact. And it works fine. And if you remember that, you can write a quick sort algorithm in less than 5 minutes. 
2. So, position one value, partition array into two sections. 

Q3. Partition can use different strategies, only important and should work on more is to find one, work out as fast as you can. And make it easy to remember. What is your advice? 
Advice:
  Choose last one in the array as a pivot point, and then, find the partition - swap and maintain a partition (each value in the partition  >  pivot value) just on right side of array. Use two pointers to find the partition two values - start, end position. 

Q4. Is this algorithm using in-place without extra space? 
Answer: 
Yes, the answer is staying in the original array, no extra space (O(1), not O(n)). So, array is used to store result, only swap two nodes' value if need. 

Facts: at most how many swap?     it depends. O(n^2)
           How many recursive calls?  n 

Because it is using in-place, the quicksort function design takes 3 input arguments, original array, start, end. 

If you cannot come out best design using in-place, you may need extra time. 

Feb. 4, 2016 Q5. Work on Leetcode - partition list
86. Partition list
http://www.cnblogs.com/springfor/p/3862392.html

328. Odd Even Linked List

Follow up after 9 months

Nov. 24, 2016
Review the code review about quick sort. 
Answer the question, link is here.  

Follow up after 13 months

March 14, 2017
1. Read all algorithms in the blog, the blogger got Google and Linkedin offer. The algorithms may be a good study material for Julia.

2. Practice one more time, C# code. Add test case for partition method and quicksort method.