Implement the sorting algorithms
文章目录
The sorting algorithms are very important in programming interview. I have to be able to write them on a paper without even an error.
Bubble Sort
The immediate thought of bubble sort is that swapping the ajacent elements
if they are of the wrong order in each pass until there are no swapping.
For example, consider the array [5, 1, 4, 2, 8]
,
First pass:
[5, 1, 4, 2, 8] => [1, 5, 4, 2, 8] => [1, 4, 5, 2, 8] => [1, 4, 2, 5, 8] => [1, 4, 2, 5, 8]
Second pass:
[1, 2, 4, 5, 8] => [1, 2, 4, 5, 8] => [1, 2, 4, 5, 8] => [1, 2, 4, 5, 8] => [1, 2, 4, 5, 8]
Third pass:
[1, 2, 4, 5, 8] => [1, 2, 4, 5, 8] => [1, 2, 4, 5, 8] => [1, 2, 4, 5, 8] => [1, 2, 4, 5, 8]
Here we found that the array has been sorted after the second pass, but we have apply the third pass so that we can know the array has been sorted because there are no swapping in that pass.
There is an optimization that can improve the performance. Observer that
in the second pass, there is no need to compare 5
to 8
, since they
are in the right order in the first pass. Hence, there is no need to compare
the last ith
element in the ith
pass.
Here is the code.
For this test cases, the average run time is 0.9s.
Select Sort
Just like its name, select sort is to select the smallest or the biggest element of the rest elements every pass. This algorithm is very easy and I can write down it with an eyes on.
Here is the code.
For this test cases, the average run time is 0.4s.
Insert Sort
Just like playing poker, insertsort will insert an element in a position of a sorted subsequence by moving the notmatch elements backward. In the worst case, the time complexity is O(n^2). However, if the list is already sorted, it requires only O(n) time complexity.
Here is the code.
For this test cases, the average run time is also 0.22s.
Shell Sort
Shell sort is one kind of insert sort. The idea that relatively sorted list can be sorted more easy is used in shell sort. It will sort the list for several times and each time with some of the elements. These elements is divided by a fixed gap and the gap will decrease until becoming 1. If the gap is 1, it’s the same as the insert sort. But now it will be more fast than the original insert sort.
Here is the code.
For this test cases, the average run time is also 0.18s.
Quick Sort
This is the most important algorithm in the interview. I must learn to write it on a paper with an eye on.
Recursive version
Select an element as the one to be compared(socalled pivot), and then put it at the end of the list. Iterate the whole list and let those elements that are smaller(larger) than the pivot in a part, the others in another part. Do the same work recursively in the two parts.
Here is the code.
For this test cases, the average run time is 0.07s.
Iterate version
The recursive version is just the depthfirst search, so we can change it into stack operation.
Here is the code.
For this test cases, the average run time is also 0.07s.
Merge Sort
Merge sort is in terms of socalled Divided and Conquered method. Dividing each sequence into two subsequences and merge them after they are sorted. Merge sort is generally faster than Quick sort(As my test cases show) but is slower than Heap sort.
I implemented three versions of merge sort.
Merge using a temporary array
In the merge process, I used a buffer to store the sorted array from the two sorted subarrays and then copy the elements to the original array.
Here is the code.
For this test cases, the average run time is 0.042s.
Merge using Insert sort
In the merge process, we can using insert sort to merge the two sorted arrays. Since the two arrays is sorted, it’s fast to merge them.
Note this method is inplace.
Here is the code.
For this test cases, the average run time is also 0.045s.
Merge by exchanging memory
How to do it? Suppose we have two subarrays, say a
and b
and a
start from begin
, b
start from mid
.

iterate
a
formbegin
toi
untila[i]
larger thanb[mid]
. 
iterate
b
frommid
toj
untilb[j]
larger thana[i]
. 
exchange the subblock
a[i..mid]
withb[mid..j]
. 
now replace
begin
with the start point of the rest subarray and repeate step 1, 2, 3.
For more information, please visit this.
Note this method is also inplace.
Here is the code.
For this test cases, the average run time is also 0.045s.
Heap Sort
A heap is very useful in sorting algorithm or in algorithms that find the top nth elements. I use a binary tree to build the tree and the binary tree is built from an array instead of a linked list. This makes me write the heap sort very easy.
Heap sort is faster than quick sort in many cases, expecially in large data set.
Here is the code.
For this test cases, the average run time is also 0.022s.
Summary
Here is the running time of these sorting algorithm with the same test cases.