Some Notes on Sorting Algorithms...
Big O Complexity Cheat Sheet
http://bigocheatsheet.com/
Comparator Interface
When comparing two objects we'll be using the Comparator interface:
http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html
Comparator takes two arguments: left and right. Implementation is typically:
left < right = -1
left > right = 1
left = right = 0
String implements the Comparable interface and the examples below use Strings.
http://docs.oracle.com/javase/7/docs/api/java/lang/String.html
So you can compare strings like this:
String s1 = "A";
String s2 = "B";
s1.compareTo(s2);
A < B = -1
A > B = 1
A = B = 0
This could be more generic than using Strings but using a particular data type makes the examples shorter for the moment.
Terminology
Stability: When two items with the same value stay in the same relative position after sort
In Place: Whether or not algorithm uses separate data structure to sort
Bubble Sort
Implementation:
- start at the beginning of the list
- compare the first and second items
- if the first is bigger than the second, swap
- repeat with each subsequent pair until end of list
- biggest item will be at the bottom
- start again at the beginning of the list and skip the last item as already sorted
- continue starting over at beginning of list and skipping already sorted items until all items sorted
Sample Code:
package com.radicalsoftware.example.sort;
import java.util.ArrayList;
import java.util.List;
public class BubbleSort {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("Zero");
list.add("Alpha");
list.add("Cat");
list.add("Boy");
list.add("Dog");
list.add("Rose");
list.add("Lion");
list.add("Fire");
list.add("Dragon");
list.add("Math");
list.add("Logic");
sort(list);
for (String s: list){
System.out.println(s);
}
}
public static List<String> sort(List<String> list){
assert list != null : "list cannot be null";
int size = list.size();
for (int pass = 1; pass < size; ++pass){
for (int left = 0; left < (size - pass); ++left){
int right = left + 1;
if (list.get(left).compareTo(list.get(right)) > 0){
swap(list, left, right);
}
}
}
return list;
}
private static <T> void swap(List<T> list, int left, int right){
T obj = list.get(left);
list.set(left, list.get(right));
list.set(right, obj);
}
}
Selection Sort
- similar to sorting books on a book shelf
- unstable
- for each spot in the list
- scan all items in list to find the smallest (or largest) item
- put the smallest (or largest) item in that spot
- move to the next spot and repeat skipping already sorted items
Sample Code:
package com.radicalsoftware.sort;
import java.util.ArrayList;
import java.util.List;
public class SelectionSort {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("Zero");
list.add("Alpha");
list.add("Cat");
list.add("Boy");
list.add("Dog");
list.add("Rose");
list.add("Lion");
list.add("Fire");
list.add("Dragon");
list.add("Math");
list.add("Logic");
sort(list);
for (String s: list){
System.out.println(s);
}
}
public static List<String> sort(List<String> list){
assert list != null : "list cannot be null";
int size = list.size();
for (int slot = 0; slot < size-1; ++slot){
int smallest = slot;
//find the smallest in remaining items
for (int checkSlot = slot + 1; checkSlot < size; ++checkSlot){
if (list.get(slot).compareTo(list.get(checkSlot)) > 0){
smallest = checkSlot;
break;
}
}
//if smallest does not equal current slot then swap
if (smallest != slot)
swap(list, smallest, slot);
}
return list;
}
private static <T> void swap(List<T> list, int left, int right){
T obj = list.get(left);
list.set(left, list.get(right));
list.set(right, obj);
}
}
Insertion Sort
- similar to sorting cards where you sort all the numbers within each suit
- create a new list and insert items into it
- use an iterator instead of an index
- insert the first item into the list
- use linked list so can scan and insert each item into correct relative location
Sample Code:
package com.radicalsoftware.sort;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class InsertionSort {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("Zero");
list.add("Alpha");
list.add("Cat");
list.add("Boy");
list.add("Dog");
list.add("Rose");
list.add("Lion");
list.add("Fire");
list.add("Dragon");
list.add("Math");
list.add("Logic");
List<String> sortedList = sort(list);
for (String s: sortedList){
System.out.println(s);
}
}
public static List<String> sort(List<String> list){
assert list != null : "list cannot be null";
final List<String> sortedList = new LinkedList<String>();
for (String s: list){
int slot = sortedList.size();
while (slot > 0){
if (s.compareTo(sortedList.get(slot - 1)) >= 0){
break;
}
--slot;
}
sortedList.add(slot, s);
}
return sortedList;
}
}
Shell Sort
- breaks large lists into smaller lists
- based on concept of H-sorting - every Hth item is sorted relative to other items
- not stable
Sample Code:
package com.radicalsoftware.sort;
import java.util.ArrayList;
import java.util.List;
public class ShellSort {
private static final int[] _increments = {1, 3, 5, 7, 11, 20};
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("Zero");
list.add("Alpha");
list.add("Cat");
list.add("Boy");
list.add("Dog");
list.add("Rose");
list.add("Lion");
list.add("Fire");
list.add("Dragon");
list.add("Math");
list.add("Logic");
list.add("Money");
list.add("Food");
list.add("Stars");
list.add("Moon");
sort(list);
for (String s: list){
System.out.println(s);
}
}
public static List<String> sort(List<String> list){
assert list != null : "list cannot be null";
for (int i = 0; i < _increments.length; i++){
int increment = _increments[i];
if (list.size() < increment * 2)
break;
hSort(list, increment);
}
return list;
}
private static void hSort(List<String> list, int increment){
for (int startIndex = 0; startIndex < increment; ++startIndex){
for (int i = startIndex + increment; i < list.size(); i += increment){
String value = list.get(i);
int j;
for (j = i; j > startIndex; j -= increment){
String previousValue = list.get(j - increment);
if (value.compareTo(previousValue) >=0)
break;
list.set(j, previousValue);
}
list.set(j, value);
}
}
}
}
Quick Sort
- uses recursion
- does the work first, then the recursion
- divide and conquer, recursively sorting smaller parts of list
- place an item in final position, smaller items left, larger items right
- divided into two parts (not necessarily two halves)
- not stable
- use quick sort until length of list is 10 or less and then use insertion sort
Best case: O(n Log(n)) -- partition element is middle element
Worst Case: O(n2) -- completely unbalanced
Implementation
- Choose partition item (last, mean of first, last and middle, etc.)
- indexes start at beginning and end (less the partition item) and advance towards each other
- left index stops when finds item larger than partitioning item
- right index stops when finds item smaller than partitioning item
- when both stop swap items
- point where indexes meet - insert partitioning item
- then sort the sublists to the right and left of the partitioning item
Sample Code:
package com.radicalsoftware.sort;
import java.util.ArrayList;
import java.util.List;
public class QuickSort {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("Alpha");
list.add("Zero");
list.add("Cat");
list.add("Boy");
list.add("Dog");
list.add("Rose");
list.add("Lion");
list.add("Fire");
list.add("Dragon");
list.add("Math");
list.add("Logic");
sort(list);
for (String s: list){
System.out.println(s);
}
}
public static void sort(List<String> list){
assert list != null : "list cannot be null";
quicksort(list, 0, list.size()-1);
}
public static void quicksort(List<String> list, int startIndex, int endIndex){
if (startIndex < 0 || endIndex >= list.size())
return;
if (endIndex <= startIndex)
return;
String value = list.get(endIndex);
int partition = partition(list, value, startIndex, endIndex -1);
if (list.get(partition).compareTo(value) < 0)
++partition;
if (partition != endIndex)
swap(list, partition, endIndex);
//sort right and left of partition
quicksort(list, startIndex, partition -1);
quicksort(list, partition + 1, endIndex);
}
private static int partition(List<String> list, String value,
int leftIndex, int rightIndex) {
int left = leftIndex;
int right = rightIndex;
while (left < right){
if(list.get(left).compareTo(value)< 0){
++left;
continue;
}
if(list.get(right).compareTo(value)>=0){
--right;
continue;
}
swap(list, left, right);
++left;
}
return left;
}
private static void swap(List<String> list, int left, int right){
String obj = list.get(left);
list.set(left, list.get(right));
list.set(right, obj);
}
}
Merge Sort
- not in place
Implementation:
- divide the list in half recursively until you get to one item arrays
- merge each array together two at a time
-- pointer at the beginning of each two array merging
-- compare elements and put the smaller into a new array
-- move pointer of array you took element from +1
-- repeat for all elements
-- repeat for all arrays
package com.radicalsoftware.sort;
import java.util.ArrayList;
import java.util.List;
public class MergeSort {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("Zero");
list.add("Alpha");
list.add("Cat");
list.add("Boy");
list.add("Dog");
list.add("Rose");
list.add("Lion");
list.add("Fire");
list.add("Dragon");
list.add("Math");
list.add("Logic");
list.add("Salmon");
List<String> sortedList = sort(list);
for (String s: sortedList){
System.out.println(s);
}
}
public static List<String> sort(List<String> list){
assert list != null : "list cannot be null";
return mergesort(list, 0, list.size()-1);
}
private static List<String> mergesort(List<String> list, int startIndex,
int endIndex) {
int middleIndex = (startIndex + endIndex)/2;
if (startIndex < endIndex){
List<String> left = mergesort(list, startIndex, middleIndex);
List<String> right = mergesort(list, middleIndex + 1, endIndex);
return merge(left, right);
}
List<String> mergedList = new ArrayList<String>();
mergedList.add(list.get(startIndex));
return mergedList;
}
private static List<String> merge(List<String> left, List<String> right) {
List<String> mergedList = new ArrayList<String>();
int rightIndex = 0;
int leftIndex = 0;
while(leftIndex < left.size() || rightIndex < right.size()){
boolean rightHasMore = rightIndex < right.size();
boolean leftHasMore = leftIndex < left.size();
if (!rightHasMore ||
(leftHasMore &&
left.get(leftIndex).compareTo(right.get(rightIndex)) <= 0)){
mergedList.add(left.get(leftIndex));
leftIndex++;
}else{
if(rightHasMore){
mergedList.add(right.get(rightIndex));
rightIndex++;
}
}
}
return mergedList;
}
}
Heap Sort
- in place (uses less memory than mergesort which has to allocate additional storage)
- comparison based sort
- selection sort family
- slower than well implemented quick sort, but better worst case
- in place
- not stable
Implementation
An array viewed as a nearly complete binary tree (meaning a subsequent level is not started until the previous level is completely filled).
http://www.youtube.com/watch?v=B7hVxCmfPtM
Bucket, counting and radix sort:
http://www.youtube.com/watch?v=woTbZMli6z4
Bucket Sort
- stable sort
- range of keys can't be too big
- linear time
Counting Sort
- stable sort
- range of keys can't be too big
- linear time
Implementation:
- histogram
- indicies
- place
Radix sort
- stable
- only good when
- use counting sort trick on the least significant digit
- not in place
- linear time
- unlimited number of keys
- uses the stability of bucket sort and counting sort
