Java Sort Algorithm
Welcome 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+ [googleplusone]
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();
}
}
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.
One of the loops is starting at the end of the array and the other at the beginning. It is almost like a bat hitting a ball. The ball starts at one end and moves toward the bat. The bat hits it and it goes back to the beginning. The only difference in this situation is that after the bat hits the ball it moves closer to the balls starting position by 1 index. I hope that helps
Thanks for the example. 🙂
i will post again if i will have questions.
I’m glad to help 🙂
Can you create a Flash Sort programming I really need it for my defense
I’ll make sure I cover it when i get back into algorithms.
Hey Derek great tutorial as always, I was wondering if you can apply the same algorithm to Doubly Linked List and can you make a tutorial video of it.
Yes pretty much. I cover the doubly linked list here.
Very Effective tutorial,Excellent work,Keep it up
Thank you very much 🙂 I’m glad you enjoyed it
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
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.
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.)
I’ll take a look at it. Sorry about not getting back to you quicker
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);
}
}
}
}
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
Hi Aidan,
I’m very happy to hear that my tutorials have helped 🙂 Thanks for taking the time to tell me.
Thank you for preparing awesome tutorials. And giving them to internet free =)
You’re very welcome 🙂
Please Someone Post a Flash Sorting Program code !!!
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.
Thank you 🙂 I’m very happy I can help