Code Review: Quicksort

March 25, 2017

Introduction

Sorting is the most important things in a programmer's life. Julia was so excited to know her first review of quicksort algorithm was chosen as the answer. But she has to keep up learning and makes a wise investment on learning quicksort.

Code review

Integer quicksort in Java

Quick Search - Julia's first answer on code review

March 13, 2017

Julia got a big surprise today, her first day work on code review to answer a question on quick search was selected as the answer today, after more than 3 months, she noticed that she got 25 reputation.

The code review link is here. She has to celebrate a little bit, it was a long time she tried to find some activities to help others while she is struggling to invent herself, keep up with others in this computer science technology world.

Julia searched her blog using quicksort, and then she found somethings to review related to quicksort.

Make it more memorable, Julia uses an image and music to celebrate her good working spirit.

Jessica Simpson - Take my breath away

When  Julia read this news, she was so excited, take my breath away, a little exaggerated, reminded her a song - the old lovely song, feels good to help others and make her own mark. One step a time, ...

Actionable Items

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. Review the C# implementation of quicksort, write a new one.

Leetcode 215: Find kth largest element in the array

May 15, 2016

 Problem statement:
 https://leetcode.com/problems/kth-largest-element-in-an-array/

 Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

 Read some blogs about this problem:

 http://www.jianshu.com/p/f52a88550588

 Julia likes to spend 10 - 20 minutes to review "Quick Select" - the idea, similar to Quick Sort, most important part is to partition.

 Time complexity: O(nlogn) in quicksort, but O(n) in quick select.

 1. Quick sort: Time complexity: O(nlogn)

 2. Use Heap sort, O(klogN)
Java Solution, using priority queue, code to study:
https://github.com/jianminchen/LeetCode-Java-Solutions/blob/master/215.kth-largest-element-in-an-array.java

Spend 20 minutes to read the blog:  4:23pm - 4:43 pm
1. http://www.cnblogs.com/yuzhangcmu/p/4164807.html

2. https://en.wikipedia.org/wiki/Introselect (read 10 minutes - 4:30pm - 4:40pm)

3. http://stackoverflow.com/questions/7559608/median-of-three-values-strategy

4. http://www.quora.com/What-is-the-most-efficient-algorithm-to-find-the-kth-smallest-element-in-an-array-having-n-elements

5. http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/ (4:50pm - 5:20pm)

30 minutes to review the solutions, write down short notes:
6 methods:
1. Use bubble k times - O(nk)
Modify bubble sort to run the outer loop at most k times
Like bubble sort, other sorting algorithms like selection sort can also be modified to get the k largest element.

2. Use temporary array
Time complexity: O((n-k)*k)

3. Use sorting
1. Sort the elements in descending order in O(nlogn)
4. Print the first k numbers of the sorted array O(k)
Time complexity: O(nlogn)

4. Use Max Heap
1. Build a Max Heap tree in O(n)
2. Use Extract Max k times to get k maximum elements from the Max Heap O(klogn)
Time complexity: O(n+klogn)

5. Use order statistics:
1) use order statistics algorithm to find the kth largest element.
Julia, take some time to review the article: see the topic selection in worst-case linear time O(n). (10 - 15 minutes)
Write down main ideas using your own words:
Use a deterministic algorithm that runs in O(n) in the worst case.

2)

3-way partition problem: Dutch national flag problem and its variants

May 6, 2015

First, I read the article about this algorithm related to partition, (in Chinese)   - May 6, 2015

https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.07.md

and then, find similar article to read later:

http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/

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)

https://shepherdyuan.wordpress.com/2014/08/03/sorting-algorithms/

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

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. 

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:

https://github.com/jianminchen/AlgorithmsPractice/blob/master/quickSortAlgorithm.cs