# Java Algorithm: Sorting

1. Insertion Sort

1> Straight Insertion Sort: O(n^2), if the records are already sorted, then O(n).

2> Binary Insertion Sort (Reduced comparison count)

3> 2-Way Insertion Sort (Reduced comparison count and move record time)

4> Shell's Sort

2. Swap Sort

1> Bubble Sort: O(n^2)

2> Quick Sort: O(n*lgn), If the array is already ordered, then Quick Sort degenerated to Bubble Sort.

3. Selection Sort

1> Simple Selection Sort: O(n^2)

2> Tree Selection Sort

4> Heap Sort: O(n*lgn)

4. Merging Sort

1. Insertion Sort

1> Straight Insertion Sort

```package edu.xmu.datastructure.sort.insertion;

import static org.junit.Assert.assertEquals;
import java.util.List;
import org.junit.Test;

public class StraightInsertionSort {
@Test
public void insertSortTest() {
List<Integer> intList = Lists.newArrayList(49, 38, 65, 97, 76, 13, 27);
List<Integer> expIntList = Lists.newArrayList(13, 27, 38, 49, 65, 76,
97);

List<Integer> sortedIntList = StraightInsertionSort.insertSort(intList);
assertEquals(expIntList, sortedIntList);
}

public static List<Integer> insertSort(List<Integer> intList) {
List<Integer> sortedIntList = Lists.newArrayList(intList);
for (int i = 1; i < sortedIntList.size(); i++) {
int valueToBeInserted = sortedIntList.get(i);
int indexToBeInserted = i;

for (int j = i - 1; j >= 0; j--) {
if (valueToBeInserted < sortedIntList.get(j)) {
sortedIntList.set(j + 1, sortedIntList.get(j));
indexToBeInserted = j;
} else {
break;
}
}
sortedIntList.set(indexToBeInserted, valueToBeInserted);
}

return sortedIntList;
}
}```

2> Binary Insertion Sort

```package edu.xmu.datastructure.sort.insertion;

import static org.junit.Assert.assertEquals;
import java.util.List;
import org.junit.Test;

public class BinaryInsertionSort {
@Test
public void insertSortTest() {
List<Integer> intList = Lists.newArrayList(49, 38, 65, 97, 76, 13, 27);
List<Integer> expIntList = Lists.newArrayList(13, 27, 38, 49, 65, 76,
97);

List<Integer> sortedIntList = BinaryInsertionSort
.binaryInsertSort(intList);
assertEquals(expIntList, sortedIntList);
}

public static List<Integer> binaryInsertSort(List<Integer> intList) {
List<Integer> sortedIntList = Lists.newArrayList(intList);
for (int i = 1; i < sortedIntList.size(); i++) {
int valueToBeInserted = sortedIntList.get(i);
int indexToBeInserted = searchIndexToBeInserted(i, sortedIntList);

// Move elements from [indexToBeInserted, i - 1] to
// [indexToBeInserted + 1, i]
for (int j = i - 1; j >= indexToBeInserted; j--) {
if (valueToBeInserted < sortedIntList.get(j)) {
sortedIntList.set(j + 1, sortedIntList.get(j));
}
}
// Insert element to indexToBeInserted position
sortedIntList.set(indexToBeInserted, valueToBeInserted);
}

return sortedIntList;
}

public static int searchIndexToBeInserted(int hotIndex,
List<Integer> sortedIntList) {
int startIndex = 0;
int endIndex = hotIndex - 1;

while (startIndex <= endIndex) {
int middle = (startIndex + endIndex) / 2;
if (sortedIntList.get(hotIndex) < sortedIntList.get(middle)) {
endIndex = middle - 1;
} else {
startIndex = middle + 1;
}
}

return endIndex + 1;
}

@Test
public void searchIndexToBeInsertedTest() {
List<Integer> sortedIntList = Lists.newArrayList(1, 2, 3, 0);
int hotIndex = 3;
int indexToBeInserted = BinaryInsertionSort.searchIndexToBeInserted(
hotIndex, sortedIntList);
assertEquals(0, indexToBeInserted);

sortedIntList = Lists.newArrayList(1, 2, 3, 4, 0);
hotIndex = 4;
indexToBeInserted = BinaryInsertionSort.searchIndexToBeInserted(
hotIndex, sortedIntList);
assertEquals(0, indexToBeInserted);

sortedIntList = Lists.newArrayList(2, 4, 6, 8, 10);
hotIndex = 4;
indexToBeInserted = BinaryInsertionSort.searchIndexToBeInserted(
hotIndex, sortedIntList);
assertEquals(4, indexToBeInserted);

sortedIntList = Lists.newArrayList(2, 4, 6, 8, 10, 5);
hotIndex = 5;
indexToBeInserted = BinaryInsertionSort.searchIndexToBeInserted(
hotIndex, sortedIntList);
assertEquals(2, indexToBeInserted);
}
}```

3> Shell's Sort (When we create the deltaList=Lists.newArrayList(1), then Shell's Sort degenerated to Straight Insertion Sort).

```package edu.xmu.datastructure.sort.insertion;

import static org.junit.Assert.assertEquals;
import java.util.List;
import org.junit.Test;

public class ShellInsertionSort {
@Test
public void insertSortTest() {
List<Integer> intList = Lists.newArrayList(49, 38, 65, 97, 76, 13, 27);
List<Integer> expIntList = Lists.newArrayList(13, 27, 38, 49, 65, 76,
97);
List<Integer> deltaList = Lists.newArrayList(5, 3, 2, 1);
for (int delta : deltaList) {
ShellInsertionSort.shellInsertSort(intList, delta);
}
assertEquals(expIntList, intList);
}

public static void shellInsertSort(List<Integer> intList, int delta) {
for (int i = delta; i < intList.size(); i++) {
int valueToBeInserted = intList.get(i);
int indexToBeInserted = i;

for (int j = i - delta; j >= 0; j -= delta) {
if (valueToBeInserted < intList.get(j)) {
intList.set(j + delta, intList.get(j));
indexToBeInserted = j;
} else {
break;
}
}
intList.set(indexToBeInserted, valueToBeInserted);
}
}
}```

2. Swap Sort

1> Bubble Sort

```package edu.xmu.datastructure.sort.swap;

import static org.junit.Assert.assertEquals;
import java.util.List;
import org.junit.Test;

public class BubbleSort {

@Test
public void bubbleSortTest() {
List<Integer> expIntList = Lists.newArrayList(13, 27, 38, 49, 65, 76,
97);
List<Integer> intList = Lists.newArrayList(49, 38, 65, 97, 76, 13, 27);
BubbleSort.bubbleSort(intList);
assertEquals(expIntList, intList);
}

public static void bubbleSort(List<Integer> intList) {
for (int i = 0; i < intList.size(); i++) {
for (int j = 0; j < intList.size() - i - 1; j++) {
int prevValue = intList.get(j);
int currValue = intList.get(j + 1);
// The biggest value bubbles to the end of the list
if (prevValue > currValue) {
intList.set(j, currValue);
intList.set(j + 1, prevValue);
}
}
}
}
}```

2> Quick Sort

```package edu.xmu.datastructure.sort.swap;

import static org.junit.Assert.assertEquals;
import java.util.List;
import org.junit.Test;

public class QuickSort {

@Test
public void quickSortTest() {
List<Integer> expIntList = Lists.newArrayList(13, 27, 38, 49, 65, 76,
97);
List<Integer> intList = Lists.newArrayList(49, 38, 65, 97, 76, 13, 27);
QuickSort.quickSort(intList, 0, intList.size() - 1);
assertEquals(expIntList, intList);
}

public static void quickSort(List<Integer> intList, int startIndex,
int endIndex) {
if (startIndex < endIndex) {
int pivotIndex = splitList(intList, startIndex, endIndex);
quickSort(intList, startIndex, pivotIndex - 1);
quickSort(intList, pivotIndex + 1, endIndex);
}
}

@Test
public void splitListTest() {
List<Integer> expectedIntList = Lists.newArrayList(27, 38, 13, 49, 76,
97, 65);
List<Integer> intList = Lists.newArrayList(49, 38, 65, 97, 76, 13, 27);
int newPivotIndex = QuickSort.splitList(intList, 0, 6);
assertEquals(expectedIntList, intList);
assertEquals(3, newPivotIndex);
}

public static int splitList(List<Integer> intList, int pivotIndex, int high) {
int pivotValue = intList.get(pivotIndex);
int low = pivotIndex;

boolean shouldHighMove = true;
while (low < high) {
if (shouldHighMove) {
if (intList.get(high) < pivotValue) {
int lowValue = intList.get(low);
int highValue = intList.get(high);
intList.set(low, highValue);
intList.set(high, lowValue);
low++;
shouldHighMove = false;
} else {
shouldHighMove = true;
high--;
}
} else {
if (intList.get(low) > pivotValue) {
int lowValue = intList.get(low);
int highValue = intList.get(high);
intList.set(low, highValue);
intList.set(high, lowValue);
high--;
shouldHighMove = true;
} else {
shouldHighMove = false;
low++;
}
}
}
if (high != low) {
throw new RuntimeException("Defacted Algorithm!");
}
intList.set(low, pivotValue);
return low;
}
}```

3. Selection Sort

1> Simple Selection Sort

```package edu.xmu.datastructure.sort.selection;

import static org.junit.Assert.assertEquals;
import java.util.List;
import org.junit.Test;

public class SimpleSelectionSort {
@Test
public void insertSortTest() {
List<Integer> intList = Lists.newArrayList(49, 38, 65, 97, 76, 13, 27);
List<Integer> expIntList = Lists.newArrayList(13, 27, 38, 49, 65, 76,
97);

SimpleSelectionSort.selectionSort(intList);
assertEquals(expIntList, intList);
}

public static void selectionSort(List<Integer> intList) {
int minValue;
int indexToBeSwapped;
for (int i = 0; i < intList.size(); i++) {
minValue = Integer.MAX_VALUE;
indexToBeSwapped = 0;

for (int j = i; j < intList.size(); j++) {
int temp = intList.get(j);
if (minValue > temp) {
minValue = temp;
indexToBeSwapped = j;
}
}
int value = intList.get(i);
intList.set(i, minValue);
intList.set(indexToBeSwapped, value);
}
}
}```

Simple Selection Sort (Extract getMinValueIndex out, make code easier to read)

```package edu.xmu.datastructure.sort.selection;

import static org.junit.Assert.assertEquals;
import java.util.List;
import org.junit.Test;

public class SimpleSelectionSort {
@Test
public void insertSortTest() {
List<Integer> intList = Lists.newArrayList(49, 38, 65, 97, 76, 13, 27);
List<Integer> expIntList = Lists.newArrayList(13, 27, 38, 49, 65, 76,
97);

SimpleSelectionSort.selectionSort(intList);
assertEquals(expIntList, intList);
}

public static void selectionSort(List<Integer> intList) {
for (int i = 0; i < intList.size(); i++) {
int minValueIndex = getMinValueIndex(i, intList);
int minValue = intList.get(minValueIndex);

int tempValue = intList.get(i);
intList.set(i, minValue);
intList.set(minValueIndex, tempValue);
}
}

private static int getMinValueIndex(int startIndex, List<Integer> intList) {
int minValue = Integer.MAX_VALUE;
int minValueIndex = 0;
for (int j = startIndex; j < intList.size(); j++) {
int temp = intList.get(j);
if (minValue > temp) {
minValue = temp;
minValueIndex = j;
}
}
return minValueIndex;
}
}```

2> Tree Selection Sort (Tournament Sort): It's just a transition selection sort algorithm between "Simple Selection Sort" and "Heap Sort"

```package edu.xmu.datastructure.sort.selection;

import static org.junit.Assert.assertEquals;
import java.util.List;
import org.junit.Test;

public class TreeSelectionSort {

@Test
public void selectionSortTest() {
List<Integer> intList = Lists.newArrayList(49, 38, 65, 97, 76, 13, 27);

List<Integer> expIntList = Lists.newArrayList(13, 27, 38, 49, 65, 76,
97);

List<Integer> orderedIntList = TreeSelectionSort
.treeSelectionSort(intList);
assertEquals(expIntList, orderedIntList);
}

public static List<Integer> treeSelectionSort(List<Integer> intList) {

BinarySelectionTreeNode rootNode = buildTree(intList);
List<Integer> orderedIntList = Lists.newArrayListWithCapacity(intList
.size());
int minValue;
for (int i = 0; i < intList.size(); i++) {
rootNode.reElectMinValue();

minValue = rootNode.getValue();

rootNode.removeMinValue(minValue);
}
return orderedIntList;
}

public static BinarySelectionTreeNode buildTree(List<Integer> intList) {
List<BinarySelectionTreeNode> leafNodes = Lists
.newArrayListWithExpectedSize(intList.size());

for (int value : intList) {
BinarySelectionTreeNode leafNode = new BinarySelectionTreeNode();
leafNode.setValue(value);
}

List<BinarySelectionTreeNode> rootNode = buildFromNodes(leafNodes);
return rootNode.get(0);
}

private static List<BinarySelectionTreeNode> buildFromNodes(
List<BinarySelectionTreeNode> nodes) {
if (nodes.size() <= 1) {
return nodes;
}

if (nodes.size() % 2 != 0) {
}
List<BinarySelectionTreeNode> mergedNodes = Lists
.newArrayListWithCapacity(nodes.size() / 2);

for (int i = 0; i < nodes.size(); i += 2) {
BinarySelectionTreeNode mergedNode = new BinarySelectionTreeNode();
BinarySelectionTreeNode lChildNode = nodes.get(i);
BinarySelectionTreeNode rChildNode = nodes.get(i + 1);

mergedNode.setlChild(lChildNode);
mergedNode.setrChild(rChildNode);
}
return buildFromNodes(mergedNodes);
}

public static class BinarySelectionTreeNode {
private int value = Integer.MAX_VALUE;
private BinarySelectionTreeNode lChild;
private BinarySelectionTreeNode rChild;

public void removeMinValue(int minValue) {
if (null == lChild && null == rChild) {
if (minValue == this.value) {
this.value = Integer.MAX_VALUE;
}
} else {
if (this.value == minValue) {
this.value = Integer.MAX_VALUE;
lChild.removeMinValue(minValue);
rChild.removeMinValue(minValue);
}
}
}

public int reElectMinValue() {
int minValue = Integer.MAX_VALUE;
if (null == lChild && null == rChild) {
minValue = this.value;
} else {
int lMinValue = lChild.reElectMinValue();
int rMinValue = rChild.reElectMinValue();
minValue = lMinValue < rMinValue ? lMinValue : rMinValue;
}
this.value = minValue;
return minValue;
}

public int getValue() {
return value;
}

public void setValue(int value) {
this.value = value;
}

public BinarySelectionTreeNode getlChild() {
return lChild;
}

public void setlChild(BinarySelectionTreeNode lChild) {
this.lChild = lChild;
}

public BinarySelectionTreeNode getrChild() {
return rChild;
}

public void setrChild(BinarySelectionTreeNode rChild) {
this.rChild = rChild;
}

}
}```

3> Heap Sort

```package edu.xmu.datastructure.sort.selection;

import static org.junit.Assert.assertEquals;
import java.util.List;
import org.junit.Test;

public class HeapSort {
@Test
public void heapSortTest() {
// 49
// 38 65
// 97 76 13 27
List<Integer> intList = Lists.newArrayList(Integer.MAX_VALUE, 49, 38,
65, 97, 76, 13, 27);
List<Integer> expIntList = Lists.newArrayList(Integer.MAX_VALUE, 13,
27, 38, 49, 65, 76, 97);
HeapSort.heapSort(intList);
assertEquals(expIntList, intList);
}

public static void heapSort(List<Integer> intList) {
for (int i = intList.size() / 2; i >= 1; i--) {
}

for (int i = intList.size() - 1; i >= 1; i--) {
int maxValue = intList.get(1);
int tailValue = intList.get(i);

intList.set(1, tailValue);
intList.set(i, maxValue);
}
}

// Max Heap
private static void adjustHeap(List<Integer> intList, int startIndex,
int endIndex) {
int rootNodeValue = intList.get(startIndex);
int currentIndex = startIndex;
for (int i = startIndex * 2; i <= endIndex; i *= 2) {
if (i + 1 > endIndex) {
// For the benefit of obsolete index
// When we put the max value at the end of array
// Then [start, end - 1]
// But here intList.get(i + 1) may unintentionally get the
// already set as max and thus unreachable
} else if (intList.get(i) < intList.get(i + 1)) {
i += 1;
}

if (rootNodeValue > intList.get(i)) {
// rootNode is bigger than its children
break;
}

intList.set(currentIndex, intList.get(i));
currentIndex = i;
}
intList.set(currentIndex, rootNodeValue);
}
}```

4. Merge Sort

```package edu.xmu.datastructure.sort.merge;

import static org.junit.Assert.assertEquals;
import java.util.List;
import org.junit.Test;

public class MergeSort {

@Test
public void mergeSortTest() {
List<Integer> intList = Lists.newArrayList(49, 38, 65, 97, 76, 13, 27);
List<Integer> expIntList = Lists.newArrayList(13, 27, 38, 49, 65, 76,
97);
List<Integer> sortedIntList = MergeSort.mergeSort(intList, 0,
intList.size() - 1);
assertEquals(expIntList, sortedIntList);
}

public static List<Integer> mergeSort(List<Integer> intList,
int startIndex, int endIndex) {
List<Integer> mergedList;
if (startIndex == endIndex) {
mergedList = Lists.newArrayList(intList.get(startIndex));
} else {
int middleIndex = (startIndex + endIndex) / 2;

List<Integer> leftList = mergeSort(intList, startIndex, middleIndex);
List<Integer> rightList = mergeSort(intList, middleIndex + 1,
endIndex);

mergedList = mergeSortedList(leftList, rightList);
}

return mergedList;
}

@Test
public void mergeListTest() {
List<Integer> leftList = Lists.newArrayList(1, 3, 5, 7);
List<Integer> rightList = Lists.newArrayList(0, 2);

List<Integer> expectedMergedList = Lists.newArrayList(0, 1, 2, 3, 5, 7);
List<Integer> mergedList = MergeSort.mergeSortedList(leftList,
rightList);

assertEquals(expectedMergedList, mergedList);

leftList = Lists.newArrayList(1, 3, 5, 7);
rightList = Lists.newArrayList(0, 2, 4, 6, 8, 9);

expectedMergedList = Lists.newArrayList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
mergedList = MergeSort.mergeSortedList(leftList, rightList);

assertEquals(expectedMergedList, mergedList);
}

/**
* Merge two ascending sorted list into one single asc list
*
* @param leftList
* @param rightList
* @return
*/
public static List<Integer> mergeSortedList(List<Integer> leftList,
List<Integer> rightList) {
List<Integer> mergedList = Lists.newArrayList();

int leftSize = leftList.size();
int rightSize = rightList.size();
int leftIndex = 0;
int rightIndex = 0;
int leftValue = Integer.MAX_VALUE;
int rightValue = Integer.MAX_VALUE;

while (!(leftIndex == leftSize && rightIndex == rightSize)) {
if (leftIndex < leftSize) {
leftValue = leftList.get(leftIndex);
} else {
leftValue = Integer.MAX_VALUE;
}
if (rightIndex < rightSize) {
rightValue = rightList.get(rightIndex);
} else {
rightValue = Integer.MAX_VALUE;
}

if (rightValue < leftValue) {
rightIndex++;
} else {
leftIndex++;
}
}

return mergedList;
}
}```

1> http://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

2> "Data Structure(C version)" - Yan, Weimin

Java Algorithm: Sorting

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊