Java Sort Algorithm

java sort algorithmWelcome to my Java sort algorithm tutorial. Here I will cover all of the elementary sorting algorithms : Bubble, Selection and Insertion sort.

I also created a new method we can use to analyze the arrays so we can learn how the sorts work. I want this video to be very interactive so that you really understand the sort algorithms.

I also cover the linear and binary search algorithms. The code below will help you learn these algorithms perfectly.

If you like videos like this, it helps to tell Google+

Code From the Video

 

public class ArrayStructures {
		
	private int[] theArray = new int[50];
	
	private int arraySize = 10;
	
	public void generateRandomArray(){
		
		for(int i = 0; i < arraySize; i++){
			
			theArray[i] = (int)(Math.random()*10)+10;
			
		}
		
	}
	
	public void printArray(){
		
		System.out.println("----------");
		for(int i = 0; i < arraySize; i++){
			
			System.out.print("| " + i + " | ");
			System.out.println(theArray[i] + " |");
			
			System.out.println("----------");
			
		}
		
	}
	
	public int getValueAtIndex(int index){
		
		if(index < arraySize) return theArray[index];
		
		return 0;
		
	}
	
	public boolean doesArrayContainThisValue(int searchValue){
		
		boolean valueInArray = false;
		
		for(int i = 0; i < arraySize; i++){
			
			if(theArray[i] == searchValue){
				
				valueInArray = true;
				
			}
			
		}
		
		return valueInArray;
		
	}
	
	public void deleteIndex(int index){
		
		if(index < arraySize){
			
			for(int i = index; i < (arraySize - 1); i++){
				
				theArray[i] = theArray[i+1];
				
			}
			
			arraySize--;
			
		}
		
	}
	
	public void insertValue(int value){
		
		if(arraySize < 50){
			
			theArray[arraySize] = value;
			
			arraySize++;
			
		}
		
	}
	
	public String linearSearchForValue(int value){
		
		boolean valueInArray = false;
		
		String indexsWithValue = "";
		
		for(int i = 0; i < arraySize; i++){
			
			if(theArray[i] == value){
				
				valueInArray = true;
				
				indexsWithValue+= i + " ";
				
			}
			
			printHorzArray(i, -1);
			
		}
		
		if(!valueInArray){
			
			indexsWithValue = "None";
			
		}
		
		System.out.print("The Value was Found in the Following: " + indexsWithValue);
		
		System.out.println();
		
		return indexsWithValue;
		
	}
	
public void printHorzArray(int i, int j){
		
		for(int n = 0; n < 51; n++)System.out.print("-");
		
		System.out.println();
		
		for(int n = 0; n < arraySize; n++){
			
			System.out.print("| " + n + "  ");
			
		}
		
		System.out.println("|");
		
		for(int n = 0; n < 51; n++)System.out.print("-");
		
		System.out.println();
		
		for(int n = 0; n < arraySize; n++){
			
			System.out.print("| " + theArray[n] + " ");
			
		}
		
		System.out.println("|");
		
		for(int n = 0; n < 51; n++)System.out.print("-");
		
		System.out.println();
		
		// END OF FIRST PART
		
		
		// ADDED FOR BUBBLE SORT
		
		if(j != -1){
		
			// ADD THE +2 TO FIX SPACING
			
			for(int k = 0; k < ((j*5)+2); k++)System.out.print(" ");
			
			System.out.print(j);
			
		}
		
		
		// THEN ADD THIS CODE
		
		if(i != -1){
			
			// ADD THE -1 TO FIX SPACING
			
			for(int l = 0; l < (5*(i - j)-1); l++)System.out.print(" ");
			
			System.out.print(i);
			
		}
		
		System.out.println();
		
	}
	
	// This bubble sort will sort everything from 
		// smallest to largest
		
		public void bubbleSort(){
			
			// i starts at the end of the Array
			// As it is decremented all indexes greater
			// then it are sorted
			
			for(int i = arraySize - 1; i > 1; i--){
				
				// The inner loop starts at the beginning of 
				// the array and compares each value next to each 
				// other. If the value is greater then they are 
				// swapped
				
				for(int j = 0; j < i; j++){
					
					// To change sort to Descending change to <
					
					if(theArray[j] > theArray[j + 1]){
						
						swapValues(j, j+1);
						
						printHorzArray(i, j);
						
					}
					
				}
				
			}
			
		}
		
		public void swapValues(int indexOne, int indexTwo){
			
			int temp = theArray[indexOne];
			theArray[indexOne] = theArray[indexTwo];
			theArray[indexTwo] = temp;
			
		}
		
		
		// The Binary Search is quicker than the linear search
		// because all the values are sorted. Because everything
		// is sorted once you get to a number larger than what
		// you are looking for you can stop the search. Also
		// you be able to start searching from the middle 
		// which speeds the search. It also works best when 
		// there are no duplicates
		
		public void binarySearchForValue(int value){
			
			int lowIndex = 0;
			int highIndex = arraySize - 1;
			
			while(lowIndex <= highIndex){
				
				int middleIndex = (highIndex + lowIndex) / 2;
				
				if(theArray[middleIndex] < value) lowIndex = middleIndex + 1;
				
				else if(theArray[middleIndex] > value) highIndex = middleIndex - 1;
				
				else {
					
					System.out.println("\nFound a Match for " + value + " at Index " + middleIndex);
					
					lowIndex = highIndex + 1;
					
				}
				
				printHorzArray(middleIndex, -1);
				
			}
			
		}
		
		// Selection sort search for the smallest number in the array
		// saves it in the minimum spot and then repeats searching
		// through the entire array each time
		
		public void selectionSort(){
			
			for(int x=0; x < arraySize; x++){
				  int minimum = x;
				  
				  for(int y=x; y < arraySize; y++){
				  
					  // To change direction of sort just change 
					  // this from > to <
					  
					  if(theArray[minimum]>theArray[y]){
						  minimum = y;
					  }
				  }
				  
				  swapValues(x, minimum);
				  
				  printHorzArray(x, -1);
			}
			
		}
		
		// The Insertion Sort is normally the best of 
		// the elementary sorts. Unlike the other sorts that
		// had a group sorted at any given time, groups are
		// only partially sorted here.
		
		public void insertionSort(){
			
			for (int i = 1; i < arraySize; i++){
				  int j = i;
				  int toInsert = theArray[i];
				  while ((j > 0) && (theArray[j-1] > toInsert)){
					  theArray[j] = theArray[j-1];
					  j--;
					  
					  printHorzArray(i, j);
					  
				  }
				  theArray[j] = toInsert;
				  
				  printHorzArray(i, j);
				  
				  System.out.println("\nArray[i] = " + theArray[i] + " Array[j] = " + theArray[j] + " toInsert = " + toInsert + "\n");
				  
			}
			
		}
	
	public static void main(String[] args){
		
		ArrayStructures newArray = new ArrayStructures();
		
		newArray.generateRandomArray();
		
		newArray.printHorzArray(-1,-1);
		
		// newArray.linearSearchForValue(10);
		
		// newArray.bubbleSort();
		
		// We must Sort first
		
		// newArray.binarySearchForValue(17);
		
		// newArray.selectionSort();
		
		newArray.insertionSort();
		
	}

}

22 Responses to “Java Sort Algorithm”

  1. Punit says:

    Hi Darek,
    i always have a confusion, why we use two looping statements in sorting algorithms, it may looks silly question, but need some clarification.

  2. N Vinod says:

    Very Effective tutorial,Excellent work,Keep it up

  3. Raj says:

    Hi Derek,

    I was asked in the interview, how will you sort an array with 1 million values in it? Please let me know your thoughts on this.

    Thanks
    Raj

    • Derek Banas says:

      Hi Raj

      QuickSort is normally faster then heap sort because of how it manages data in memory, but QuickSorts worst case performance is considerably worse then Heap Sort.

  4. Rishikesh says:

    Hi Derek,

    Your bubbleSort() function does not work correctly for a reverse
    sorted array as the outer for loop iterates n-2 times when it should be iterating n-1 times.

    To verify this for yourself, in your generateRandomArray() function, sort and reverse the array using inbuilt java functions
    and then call the bubbleSort function.

    (This is the second time I am trying to report this error. Hope you fix it.)

    • Derek Banas says:

      I’ll take a look at it. Sorry about not getting back to you quicker

      • Avinash says:

        The correct bubble sort is:
        public void bubbleSort(){

        // i starts at the end of the Array
        // As it is decremented all indexes greater
        // then it are sorted

        for(int i = arraySize – 1; i > 0; i–){

        // The inner loop starts at the beginning of
        // the array and compares each value next to each
        // other. If the value is greater then they are
        // swapped

        for(int j = 0; j < i; j++){

        // To change sort to Descending change to theArray[j + 1]){

        swapValues(j, j+1);

        printHorzArray(i, j);

        }

        }

        }

        }

  5. Aidan McGrath says:

    Derek Banas,

    Just want to say that I’ve been learning more about serious problem solving in your tutorials than any other resource on the internet or otherwise.

    I take my hat off and thank-you.

    Thanks,

    Aidan

  6. bb says:

    Thank you for preparing awesome tutorials. And giving them to internet free =)

  7. Darius says:

    Please Someone Post a Flash Sorting Program code !!!

  8. gaspy says:

    Derek……you have been my online teacher and mentor for about 2 months now….and will continue to be for a long long time….thanks for taking your time to do allthe great stuff.

Leave a Reply

Your email address will not be published.

Google+