Friday, October 23, 2009

Sorting Algorithms (Bubble sort, Selection sort & Insertion Sort)

I want to refresh my mind about sorting algorithms and here are the first three simple sorting algorithms in this article - Bubble Sort, Selection Sort and Insertion Sort. I attribute the explanations to Wikipedia.

import java.util.Random;

public class SortingAlgorithm {

private final int SIZE = 2000;
private Random myRand = new Random();
private int[] numbers = new int[SIZE];

public SortingAlgorithm(){}

private void randomizeNumbers(){
for (int i = 0; i < numbers.length; i++) {
numbers[i] = myRand.nextInt( 2000 ) + 1;
}
}

private void printArray(){
for(int i: numbers){
System.out.print(i + " ");
}
System.out.println();
}

public void bubbleSort() {
randomizeNumbers();
System.out.println("BUBBLE SORT");
System.out.println("Presorted numbers: ");
printArray();
long start = System.nanoTime();

/**
* Bubblesort algorithm
* Wikipedia:
* works by repeatedly stepping through the list to be sorted,
* comparing each pair of adjacent items and swapping them if
* they are in the wrong order. The pass through the list is
* repeated until no swaps are needed, which indicates that the
* list is sorted. The algorithm gets its name from the way smaller
* elements "bubble" to the top of the list.
* Complexity:
* Worst = O(n^2)
* Average = O(n^2)
* Best = O(n)
*/
int n = numbers.length;
for (int pass=1; pass < n; pass++) {
for (int i=0; i < n-pass; i++) {
if (numbers[i] > numbers[i+1]) {
int temp = numbers[i];
numbers[i] = numbers[i+1];
numbers[i+1] = temp;
}
}
}

long elapsed = (System.nanoTime() - start);
System.out.println("Bubble-sorted numbers: ");
printArray();
System.out.println("Elapsed time: " + elapsed + "ns\n");
}

public void selectionSort(){
randomizeNumbers();
System.out.println("SELECTION SORT");
System.out.println("Presorted numbers: ");
printArray();
long start = System.nanoTime();

/**
* Selectionsort Algoritm
* Wikipedia:
* 1. Find the minimum value in the list
* 2. Swap it with the value in the first position
* 3. Repeat the steps above for the remainder of the list (starting
* at the second position and advancing each time)
* Complexity:
* Worst = O(n^2)
* Average = O(n^2)
* Best = O(n^2)
*/
for (int i=0; i<numbers.length-1; i++) {
int minIndex = i;
for (int j=i+1; j<numbers.length; j++) {
if (numbers[minIndex] > numbers[j]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = numbers[i];
numbers[i] = numbers[minIndex];
numbers[minIndex] = temp;
}
}

long elapsed = (System.nanoTime() - start);
System.out.println("Selection-sorted numbers: ");
printArray();
System.out.println("Elapsed time: " + elapsed + "ns\n");
}

public void insertionSort(){
randomizeNumbers();
System.out.println("INSERTION SORT");
System.out.println("Presorted numbers: ");
printArray();
long start = System.nanoTime();

/**
* Insertionsort Algorithm
* Wikipedia:
* much less efficient on large lists than more advanced algorithms
* such as quicksort, heapsort, or merge sort. However, insertion sort
* provides several advantages:
* 1. simple implementation
* 2. efficient for (quite) small data sets
* 3. adaptive, i.e. efficient for data sets that are already substantially
* sorted: the time complexity is O(n + d), where d is the number of inversions
* 4. more efficient in practice than most other simple quadratic (i.e. O(n^2)) algorithms
* such as selection sort or bubble sort
* Complexity:
* Worst = O(n^2)
* Average = O(n^2)
* Best = O(n)
*/
int in, out;
for(out=1; out<numbers.length; out++){
int temp = numbers[out];
in = out;
while(in>0 && numbers[in-1] >= temp){
numbers[in] = numbers[in-1];
--in;
}
numbers[in] = temp;
}

long elapsed = (System.nanoTime() - start);
System.out.println("Insertion-sorted numbers: ");
printArray();
System.out.println("Elapsed time: " + elapsed + "ns\n");
}

public static void main(String[] args) {
SortingAlgorithm sa = new SortingAlgorithm();
sa.bubbleSort();
sa.selectionSort();
sa.insertionSort();
}
}

0 comments:

Post a Comment