Background
This post summarises various sorting techniques.
Sorting Techniques
I have written posts over time to show the implementation of some of the sorting techniques. Following are links to the same -
package Sorts;
import java.util.Arrays;
/**
* Created by Aniket on 3/3/14.
*/
public class HeapSort {
public int getLeft(int i){
return 2*i;
}
public int getRight(int i){
return 2*i+1;
}
public int getParent(int i){
return i/2;
}
public void maxHeapify(int[] array, int position){
int leftPosition = getLeft(position);
int rightPosition = getRight(position);
int largest = 0;
if(leftPosition <= array.length && array[leftPosition-1] > array[position-1]){
largest = leftPosition;
}
else {
largest = position;
}
if(rightPosition <= array.length && array[rightPosition-1] > array[largest-1]){
largest = rightPosition;
}
if(largest != position){
swap(array,position-1,largest-1);
maxHeapify(array, largest);
}
}
public void maxHeapifyForSort(int[] array, int position, int maxPos){
int leftPosition = getLeft(position);
int rightPosition = getRight(position);
int largest = 0;
if(leftPosition <= maxPos && array[leftPosition-1] > array[position-1]){
largest = leftPosition;
}
else {
largest = position;
}
if(rightPosition <= maxPos && array[rightPosition-1] > array[largest-1]){
largest = rightPosition;
}
if(largest != position){
swap(array,position-1,largest-1);
maxHeapifyForSort(array, largest,maxPos);
}
}
public void buildMaxHeap(int[] array){
for(int i=(array.length)/2;i>0;i--){
maxHeapify(array,i);
}
}
public void swap(int[] array, int i, int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public void heapSort(int[] array){
buildMaxHeap(array);
for(int i=array.length;i>0;i--){
swap(array,0,i-1);
maxHeapifyForSort(array,1,i-1);
}
}
public static void main(String args[]){
int[] array = new int[]{4,1,3,2,16,9,10,14,8,7};
System.out.println("Original Array : " + Arrays.toString(array));
//new HeapSort().buildMaxHeap(array);
new HeapSort().heapSort(array);
System.out.println("After Sorting Array : " + Arrays.toString(array));
}
}
package SortingTechniques;
import java.util.Arrays;
import java.util.Stack;
/**
* Created with IntelliJ IDEA.
* User: aniket
* Date: 19/2/14
* Time: 11:02 AM
*/
public class StackSort {
public void sortStack(Stack<Integer> stack){
int no = stack.pop();
if(stack.size() != 1){
sortStack(stack);
}
insert(stack,no);
}
private void insert(Stack<Integer> stack, int no){
if(stack.size() == 0){
stack.push(no);
}
else{
int newPeakedNo = stack.peek();
if(no >= newPeakedNo){
stack.push(no);
}
else{
int newPoppedNo = stack.pop();
insert(stack, no);
stack.push(newPoppedNo);
}
}
}
public static void main(String args[]){
Stack<Integer> stack = new Stack<>();
stack.push(5);
stack.push(4);
stack.push(3);
stack.push(2);
stack.push(1);
System.out.println("Stack Before Sort : " + Arrays.toString(stack.toArray()));
new StackSort().sortStack(stack);
System.out.println("Stack After Sort : " + Arrays.toString(stack.toArray()));
}
}
import java.util.Arrays;
/**
* Created with IntelliJ IDEA.
* User: aniket
* Date: 19/2/14
* Time: 8:03 PM
*/
public class CountingSort {
public int[] sort(int[] array) {
int maxValue = getMaxValue(array);
return countingSort(array,maxValue);
}
public int[] countingSort(int[] input, int maxValue){
int[] countArray = new int[maxValue+1];
for(int no : input){
countArray[no] = countArray[no] + 1;
}
for(int i=1;i<countArray.length;i++){
countArray[i] = countArray[i] + countArray[i-1];
}
int[] output = new int[input.length];
for(int i=output.length-1;i>=0;i--){
output[countArray[input[i]]-1] = input[i];
countArray[input[i]] = countArray[input[i]] -1;
}
return output;
}
private int getMaxValue(int[] array){
int maxValue = Integer.MIN_VALUE;
for(int no : array){
if(no > maxValue){
maxValue = no;
}
}
return maxValue;
}
public static void main(String args[]){
int[] array = new int[]{2,7,5,9,4,7,1,0};
System.out.println("Array Before Sort : " + Arrays.toString(array));
System.out.println("Array after Sort : " + Arrays.toString(new CountingSort().sort(array)));
}
}
import java.io.IOException;
import java.util.Arrays;
/**
* Created with IntelliJ IDEA.
* User: aniket
* Date: 19/2/14
* Time: 8:32 PM
*/
public class QuickSort {
public void quickSort(int[] array, int start, int end){
int i = start;
int j = end;
int pivot = array[(start + end)/2];
while (i <= j) {
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
swap(array, i, j);
i++;
j--;
}
}
if (start < j)
quickSort(array, start, j);
if (i < end)
quickSort(array, i, end);
}
public static void swap(int[] array, int index1, int index2){
if(index1 == index2)
return;
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
public static void main(String args[]) throws IOException {
int[] array = new int[]{2,7,5,9,4,7,1,0};
System.out.println("Array Before Sort : " + Arrays.toString(array));
new QuickSort().quickSort(array,0,array.length-1);
System.out.println("Array after Sort : " + Arrays.toString(array));
}
}
import java.util.Arrays;
/**
* Created with IntelliJ IDEA.
* User: aniket
* Date: 12/2/14
* Time: 11:24 AM
*/
public class MergeSort {
public void sort(int[] array) {
mergeSort(array,0,array.length-1);
}
private void mergeSort(int[] array, int start, int end){
if(start == end){
return;
}
int mid = (start + end)/2;
mergeSort(array, start, mid);
mergeSort(array, mid+1, end);
merge(array,start,mid,end);
}
private void merge(int[] array, int start, int mid, int end){
int[] leftArray = Arrays.copyOfRange(array,start,mid+1);
int[] rightArray = Arrays.copyOfRange(array,mid+1,end+1);
int i = 0;
int j = 0;
int counter = start;
while(i<leftArray.length && j<rightArray.length){
if(leftArray[i] < rightArray[j]){
array[counter] = leftArray[i];
i++;
}
else {
array[counter] = rightArray[j];
j++;
}
counter++;
}
if(i == leftArray.length){
while(j != rightArray.length){
array[counter] = rightArray[j];
j++;
counter++;
}
}
else{//j == rightArray.length
while(i != leftArray.length){
array[counter] = leftArray[i];
i++;
counter++;
}
}
}
public static void main(String args[]){
int[] array = new int[]{2,7,5,9,4,7,1,0};
System.out.println("Array Before Sort : " + Arrays.toString(array));
new MergeSort().sort(array);
System.out.println("Array after Sort : " + Arrays.toString(array));
}
}
import java.util.Arrays;
/**
* Created with IntelliJ IDEA.
* User: aniket
* Date: 12/2/14
* Time: 11:14 AM
*/
public class InsertionSort {
public void sort(int[] array) {
for(int i=1;i<array.length;i++){
int j = i;
while(j>0 && array[j-1]>array[j]){
Swapper.inMemorySwap(array,j-1,j);
j--;
}
}
}
public static void main(String args[]){
int[] array = new int[]{2,7,5,9,4,7,1,0};
System.out.println("Array Before Sort : " + Arrays.toString(array));
new InsertionSort().sort(array);
System.out.println("Array after Sort : " + Arrays.toString(array));
}
}
public static int[] insertionSort(int[] array) {
for(int i=1; i <array.length; i++) {
int key = array[i];
int j = i - 1;
while(j>=0 && array[j] > key ) {
array[j+1] = array[j];
j--;
}
array[j+1] = key;
}
return array;
}
import java.util.Arrays;
/**
* Created with IntelliJ IDEA.
* User: aniket
* Date: 11/2/14
* Time: 8:29 PM
*/
public class BubbleSort {
public void sort(int[] array) {
int arrayLength = array.length;
for(int i=0;i<arrayLength;i++){
for( int j=0;j<arrayLength-i-1;j++){
if(array[j] > array[j+1]){
Swapper.inMemorySwap(array,j,j+1);
}
}
}
}
public static void main(String args[]){
int[] array = new int[]{2,7,5,9,4,7,1,0};
System.out.println("Array Before Sort : " + Arrays.toString(array));
new BubbleSort().sort(array);
System.out.println("Array after Sort : " + Arrays.toString(array));
}
}
package Sorts;
import java.util.Arrays;
/**
* Created by Aniket on 2/19/14.
*/
public class BubbleSort {
public void sort(int[] array) {
int arrayLength = array.length;
for(int i=0;i<arrayLength;i++){
boolean isSorted = true;
for( int j=0;j<arrayLength-i-1;j++){
if(array[j] > array[j+1]){
isSorted = false;
Swapper.inMemorySwap(array,j,j+1);
}
}
if(isSorted){
System.out.println("Breaking at index : " + i);
break;
}
}
}
public static void main(String args[]){
int[] array = new int[]{2,7,5,9,4,7,1,0,1,2,3,};
System.out.println("Array Before Sort : " + Arrays.toString(array));
new BubbleSort().sort(array);
System.out.println("Array after Sort : " + Arrays.toString(array));
}
}
public void swap(int[] array, int x, int y) {
array[x] = array[x] + array[y];
array[y] = array[x] - array[y];
array[x] = array[x] - array[y];
}