Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: Sorting Algorithms

  1. #1
    Little Star
    Join Date
    May 2009
    Posts
    30
    Thanks
    0
    Thanked 9 Times in 7 Posts

    Default Sorting Algorithms

    Hello, today I will try to give a quick overview of sorting algorithms that we can use.

    Note: To keep it simple I will use lists that are made of integers (for sorting).

    Introduction

    First I will show you how to implement Selection sort and Insertion sort algorithms, they both are O(n^2) algorithms and should be used only for small lists (lets say less than 6-10 numbers).
    Then we will get on with better ways to sort big integer lists by using Merge Sort, Heap Sort and Quick Sort. All of them have an average case performance of O(nlogn).
    At the end we will discuss algorithms that can sort lists in O(n) time, such as Bucket Sort, Counting Sort and Radix sort.

    If you see any spelling errors or want to add information that might be usefull, please send me a PM and I will try to fix it. I know I am not the best at explaining things, so I would appreciate if people would help me out here!

    Practical Example

    To give you a simple example lets say we have two computers (A and B).
    Computer A can execute 10^9 instructions per second.
    Computer B can execute 10^7 instructions per second.
    So computer A is 100 times faster than computer B in raw computing power.
    Both computers must sort an array of one million numbers.
    Computer A (faster one) will run Insertion Sort.
    Computer B (slower one) will run Merge Sort.
    To make the difference even more dramatic, suppose that the world's craftiest programmer codes insertion sort in machine language for computer A, and the resulting code requires 2n^2 instructions to sort n numbers (So the constant c = 2).
    While Merge Sort is programmed by an average programmer using a high-level language with an inefficient compiler, with the resulting code taking 50n logn instructions (So the constant c = 50).

    To sort one million numbers computer A takes: 2 * (10^6)^2 / 10^9 = 2000 seconds.
    while computer B takes 50 * 10^6 log(10^6) / 10^7 ≈ 100 seconds.

    If we try to sort 10 million numbers, the difference between two will increase even more
    insertion sort will take 2.3 days, while merge sort will do it under 20 minutes.

    So as you can see, even tho we had a more powerfull computer, and constants were very different, we could not beat O(nlogn) algorithm with an O(n^2) algorithm on big arrays. Also I hope that you understood why Insertion sort algorithm is better for sorting small lists, than merge sort. (because constant of insertion will always be smaller than merge sort's if we program on same computer with same programming language)

    Selection sort: Selection sort - Wikipedia, the free encyclopedia

    public class SelecionSort {
    	/**
    	 * Sorts the given list in place.
    	 * Worst Case Performance O(n^2)
    	 * Best Case Performance O(n^2)
    	 * Average Case Performance O(n^2)
    	 * Insertion sort can be- and usually is a much faster sorting algorithm, than selection sort.
    	 * Selection sort is superior because it does less swaps.
    	 * @param list - int array that you want to sort.
    	 */
    	public static void sortNumbers(Integer[] list){
    		//go through the list
    		for (int i=0; i<list.length;i++){
    			//define min
    			int min = i;
    			//go through the remaining list and see if there is smaller number
    			for (int j=i+1;j<list.length;j++){
    				//if there is a smaller number
    				if (list[j] < list[min]){
    					//remember its place
    					min = j;
    				}
    			}
    			if (i != min){
    				//swap the min element, moving it to its proper place in the list.
    				int temp = list[min];
    				list[min] = list[i];
    				list[i] = temp;
    			}
    		}
    	}
    	/**
    	 * Just for testing purposes.
    	 */
    	public static void main(String[] args){
    		Integer[] list = new Integer[5];
    		list[0] = 32;
    		list[1] = 24;
    		list[2] = 235;
    		list[3] = 1;
    		list[4] = 0;
    		sortNumbers(list);
     
    		for (int i = 0;i<list.length;i++){
    			System.out.println(list[i]);
    		}
    	}
     
    }

    Insertion Sort: Insertion sort - Wikipedia, the free encyclopedia

    public class InsertionSort {
     
    	/**
    	 * Sorts the given list in place.
    	 * Worst Case Performance O(n^2)
    	 * Best Case Performance O(n)
    	 * Average Case Performance O(n^2)
    	 * @param list - int array that you want to sort.
    	 */
    	public static void sortNumbers(int[] list){
    		//go through the list of the numbers, starting with number two (we say that number one is already sorted)
    		for (int i=1; i<list.length -1; i++){
    			//store the value of the number we are dealing with (because it's place can be taken by other bigger numbers)
    			int value = list[i];
    			//define j (its a pointer to the already sorted list, starting at the largest number - back of the sorted list)
    			int j = i-1;
    			//as long as value is lower than the number in sorted list and we are still in the list
    			while (j >= 0 && list[j] > value){
    				// we are going to move the higher number(from the sorted list) one step to the right (so it will make space for the current value number - witch is lower)
    				list[j+1] = list[j];
    				//and we move our pointer in the list to next place - lower number
    				j--;
    			}
    			//once we come to the right spot, we insert our value number in there and start with next i value.
    			list[j+1] = value;
    		}
    	}
     
    }

    Those two algorithms (Selection and Insertion) are good for sorting small lists, but when lists start to become big you better use faster algorithms such as following:

    Merge Sort: Merge sort - Wikipedia, the free encyclopedia

    public class MergeSort {
     
    	/**
    	 * Merges two arrays into one.
    	 * @param A array that contains the two arrays.
    	 * @param temp temporary array that we will work with
    	 * @param lo lowest index value in the array
    	 * @param mid middle index value in the array (represents break between low and high values)
    	 * @param hi highest index value in the array
    	 */
    	private static void Merge(int[] A, int[] temp, int lo, int mid, int hi){
    		int i = lo;
    		int j = mid;
     
    		for (int k = lo; k < hi; k++){
    			if (i == mid) temp[k] = A[j++]; //if lo-mid array is empty
    			else if (j == hi) temp[k] = A[i++]; //if mid-hi array is empty
    			else if (A[j] > A[i]) temp[k] = A[i++]; //i is lower so we put it in the array first
    			else temp[k] = A[j++]; //j is lower or equal to i, so we put it in the array first.
    		}
     
    		//now we need to copy back temp array to its place in A array
    		for (int k = lo; k < hi; k++)
    			A[k] = temp[k]; //we are copying only the numbers we just merged.
     
    	}
     
    	private static void MergeSort(int[] A, int lo, int hi){
    		if (hi - lo == 1) return; //only one element in the array, return.
    		int mid = lo + (hi - lo) / 2; //find middle
    		MergeSort(A, lo, mid); //sort first part
    		MergeSort(A, mid, hi); //sort second part
    		Merge(A, new int[A.length], lo, mid, hi); //merge both parts
    	}
     
    	/**
    	 * Sorts the given list. (Not in place)
    	 * Worst Case Performance O(nlogn)
    	 * Best Case Performance O(nlogn)
    	 * Average Case Performance O(nlogn)
    	 * @param A list of int array.
    	 */
    	public static void sortNumbers(int[] A){
    		MergeSort(A, 0, A.length);
    	}
     
    	/**
    	 * Just for testing purposes.
    	 */
    	public static void main(String[] args){
    		int[] list = {156,344,54,546,767,23,34,64,234,654,234,65,234,65,87,3,5,76,24,2,3,7,9,5,34,32,4525,345,0};
    		sortNumbers(list);
     
    		for (int i = 0;i<list.length;i++){
    			System.out.println(list[i]);
    		}
    	}
     
    }

    Heap Sort: Heapsort - Wikipedia, the free encyclopedia

    public class HeapSort {
     
    	private static int heapSize; //this will help us to stop sorting list numbers that are already sorted.
     
     
    	/**
    	 * Sorts the given list in place.
    	 * Worst Case Performance O(nlogn)
    	 * Best Case Performance O(nlogn)
    	 * Average Case Performance O(nlogn)
    	 * @param A - list that needs to be sorted.
    	 */
    	public void sortNumbers(int[] A){
    		HeapSort(A);
    	}
     
    	/**
    	 * Read sortNumbers method description.
    	 * @param A - list that needs to be sorted.
    	 */
    	private void HeapSort(int[] A){
    		heapSize = A.length; //we need to sort all the list so heapSize == A.length
    		BuildMaxHeap(A); //first we build max heap
     
    		//now we have the biggest element in the heap on the top
    		//we will exchange it with the last element in the list
    		//reduce heapSize so this (biggest) element wont be sorted anymore
    		//and we will call MaxHeapify once again to get new biggest element on the top
    		//and once again we place it at the current end of the list, we do it all the way
    		//til we will have only one element left in the heap (which will be the lowest number)
    		//this way our array will get sorted, from smallest (at the start of the list) to biggest (at the end of the list).
     
    		for (int i = A.length-1; i>0; i--){
     
    			//exchange biggest number with the current last one
    			int temp = A[0];
    			A[0] = A[i];
    			A[i] = temp;
    			//reduce the heap size
    			heapSize--;
    			//find new biggest
    			MaxHeapify(A,0);
    		}
    	}
     
    	/**
    	 * Builds MaxHeap (runs in linear time so: O(n) )
    	 * if n = amount of numbers in the list, then n/2 = amount of leaves (nodes that have no children)
    	 * We need to call MaxHeapify from bottom and up, but we can skip all leaves so we start at index = n/2 and go up.
    	 * @param A - list that we will build MaxHeap of.
    	 */
    	private void BuildMaxHeap(int[] A){
    		for(int i = A.length/2-1;i>=0;i--){
    			MaxHeapify(A, i);
    		}
    	}
     
    	/**
    	 * Takes O(logn) or we can also say that if subtree with root at index i has height of h
    	 * then running time of algorithm is O(h)  (note that a binary tree with n elements has height = logn)
    	 * Sorts the array at the given index so that subtree meets heap requirements.
    	 * @param A array list
    	 * @param i index of the root of subtree that might be smaller than its children.
    	 */
    	private void MaxHeapify(int[] A, int i){
    		int l = Left(i); //lets find left child of the given index.
    		int r = Right(i);//lets find right child of the given index.
    		int max;
    		if (l < heapSize){ //lets check if left child is an existing child
     
    			//if it is an existing child
    			if (A[l] > A[i]){ //if left child is bigger than parent
    				max = l; //left child becomes maximum
    			}
    			else {
    				max = i; //otherwise parent is maximum
    			}
    		}
    		else { //if this index does not have left child
    			max = i;
    		}
     
    		if (r < heapSize){ //lets check if the right child is an existing child
     
    			//if it is existing child
    			if(A[r] > A[max]){ //if right child is bigger than our current maximum
    				max = r; //right child becomes our new maximum
    			}
    		}
     
    		if (max != i){ //if our parent is not maximum
    			//we need to swap max with parent
    			int temp = A[i];
    			A[i] = A[max];
    			A[max] = temp;
     
    			//at the end we need to run MinHeapify on the child that was just swapped 
    			//and see if it is supposed to go even further down the list
    			MaxHeapify(A, max);
    		}
    	}
     
    	/**
    	 * Returns Left child index of the given parent index.
    	 * @param i - parent index.
    	 * @return - index of parents left child.
    	 */
    	private int Left(int i){
    		return 2 * i;
    	}
     
    	/**
    	 * Returns Right child index of the given parent index.
    	 * @param i - parent index.
    	 * @return - index of parents right child.
    	 */
    	private int Right(int i){
    		return (2 * i) + 1;
    	}
     
    	/**
    	 * Just for testing purposes.
    	 */
    	public static void main(String[] args){
    		int[] list = {156,344,54,546,767,23,34,64,234,654,234,65,234,65,87,3,5,76,24,2,3,7,9,5,34,32,4525,345,0};
    		HeapSort hs = new HeapSort();
    		hs.sortNumbers(list);
     
    		for (int i = 0;i<list.length;i++){
    			System.out.println(list[i]);
    		}
    	}
     
    }

    Quick Sort: Quicksort - Wikipedia, the free encyclopedia

    public class QuickSort {
     
    	/**
    	 * Sorts the given list in place.
    	 * Worst Case Performance O(n^2)
    	 * Best Case Performance O(nlogn)
    	 * Average Case Performance O(nlogn)
    	 * @param list - int array that you want to sort.
    	 */
    	public void sortNumbers(int[] list){
    		Quicksort(list, 0,list.length-1);
    	}
     
    	public void Quicksort(int[] A, int start, int end){
    		if (start < end){
    			//we partition the list and get back two lists (lower than pivot, and bigger than pivot)
    			int middle = Partition(A, start, end);
    			//we then do a recursive call to sort out lower numbers than pivot
    			Quicksort(A, start, middle-1);
    			//and we do same with higher numbers than pivot
    			Quicksort(A, middle+1, end);
    			//NOTE: pivot is already in it's place, where he supposed to be (in a sorted list).
    		}
    	}
     
    	public int Partition (int[] A, int start, int end){
    		int pivot = A[end]; //we define pivot (the number we will be comparing other numbers to
    		int lo = start-1; // we define low value index
     
    		for (int hi = start; hi < end; hi++){ //we go throug the list, compare other numbers to pivot
    			if (A[hi] <= pivot){ //if pivot is lower that the current number
    				lo++; //we increase lo value
    				//and exchange current lo with hi (so we will have all lower numbers than pivot on one side
    				int temp = A[lo];
    				A[lo] = A[hi];
    				A[hi] = temp;
    			}
    		}
    		//at the end we put in pivot right inbetween low and high values and we know that pivot element is in the right place.
    		int temp = A[lo+1];
    		A[lo+1] = A[end];
    		A[end] = temp;
     
    		return lo+1; //we return the pivot elements place
    	}
     
    	public static void main(String[] args){
    		int[] list = {156,344,54,546,767,23,34,64,234,654,234,65,234,65,87,3,5,76,24,2,3,7,9,5,34,32,4525,345,0};
    		QuickSort qs = new QuickSort();
    		qs.sortNumbers(list);
     
    		for (int i = 0;i<list.length;i++){
    			System.out.println(list[i]);
    		}
    	}
     
    }


    Later on I will add algorithms that can sort lists in linear time. Yes, even faster algorithms, but they have quite big requirements on input and might not be so memory efficient.

    Hope this will help someone.
    -Dal.

  2. The Following 2 Users Say Thank You to Dalisra For This Useful Post:

    awesomesylin (April 10th, 2011), JavaPF (November 17th, 2009)


  3. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Sorting Algorithms

    You can also sort data via binary search trees (I believe it takes O(nlog(n)) time, but the actually implementation is somewhat slower than quicksort)

Similar Threads

  1. Having trouble insert/sorting array values w/ binary searching.
    By bh-chobo in forum Collections and Generics
    Replies: 4
    Last Post: October 8th, 2009, 02:38 AM
  2. [SOLVED] help with sorting...(comparator)
    By mdstrauss in forum Collections and Generics
    Replies: 2
    Last Post: July 26th, 2009, 06:25 AM
  3. Logic to implement a program to display decimal place of a number
    By chronoz13 in forum Algorithms & Recursion
    Replies: 2
    Last Post: June 11th, 2009, 03:53 AM
  4. [SOLVED] Java program to sort arrays containing dates
    By scottyadam in forum Collections and Generics
    Replies: 1
    Last Post: March 9th, 2009, 06:08 PM
  5. Java algorithm for bank program to connect database
    By araujo3rd in forum Algorithms & Recursion
    Replies: 1
    Last Post: December 10th, 2008, 12:34 PM