Survey:

This time, we talk about eight kinds of sort algorithms: insertion sort, shell’s sort, simple selection sort, heap sort, bubble sort, quick sort, merge sort and radix sort.

Insertion sort:

Main Idea:

From the beginning of the list, get one value at a time and insert the value into right position of sorted list until all the values are sorted. And insertion sort is stalbe.

Process: (From Wikimedia)

Pseudocode:

for i ← 1 to length(A) - 1
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
end for

Implemention in Java:

public static void InsertionSort(int[] num)
{
     int j;
     int key;
     int i;  

     for (j = 1; j < num.length; j++){
        key = num[j];
        for(i = j - 1; (i >= 0) && (num[i] < key); i--){
            num[i+1] = num[i];
        }
        num[i+1] = key;
    }
}

Complexity:

Runtime: O(n^2)

Memery: O(1)

---

ShellSort:

Main Idea:

The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbor exchange.

Process:(From Wikimedia)

Pesedocode:

gaps = [701, 301, 132, 57, 23, 10, 4, 1]

foreach (gap in gaps)
{
    # Do a gapped insertion sort for this gap size.
    # The first gap elements a[0..gap-1] are already in gapped order
    # keep adding one more element until the entire array is gap sorted
    for (i = gap; i < n; i += 1)
    {
        # add a[i] to the elements that have been gap sorted
        # save a[i] in temp and make a hole at position i
        temp = a[i]
        # shift earlier gap-sorted elements up until the correct location for a[i] is found
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        # put temp (the original a[i]) in its correct location
        a[j] = temp
        }
    }

Implemention in Java:

public void shellSort() {
    int inner, outer;
    long temp;
    //find initial value of h
    int h = 1;
    while (h <= len / 3)
      h = h * 3 + 1; // (1, 4, 13, 40, 121, ...)

    while (h > 0) // decreasing h, until h=1
    {
      // h-sort the file
      for (outer = h; outer < len; outer++) {
        temp = data[outer];
        inner = outer;
        // one subpass (eg 0, 4, 8)
        while (inner > h - 1 && data[inner - h] >= temp) {
          data[inner] = data[inner - h];
          inner -= h;
        }
        data[inner] = temp;
      }
      h = (h - 1) / 3; // decrease h
    }
}

---

Simple Selection Sort

Main Idea:

Find the smallest(biggest) element in array, put it in the first place. Then find the second smallest… Do these until all the element are sorted.(I suppose it’s a little similar with bubble sort)

Process:(From Wikimedia)

Pesedocode:

for i ← 1 to length(A) - 1
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
end for

Complexity:

Runtime: O(n^2)
Memery: O(1)

Heapsort

Main Idea:

Use data structure heap which will store the smallest or biggest value of the array. Then pick up the root of heap once a time to sort.

Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.

This sort is the most important part in this article. I’ll talk about the relative operation and its performance and all the code.

Process:(From Wikimedia)

In the heap view(an example offered):

Data Structure:

Heap:

A heap is built out of the data. The heap is often placed in an array with the layout of a complete binary tree. The complete binary tree maps the binary tree structure into the array indices; each array index represents a node; the index of the node’s parent, left child branch, or right child branch are simple expressions. For a zero-based array, the root node is stored at index 0; if i is the index of the current node, then

iParent(i)     = floor((i-1) / 2)
iLeftChild(i)  = 2*i + 1
iRightChild(i) = 2*i + 2