Data Structure – Sorting Algorithms in Java

some notes about Sort algorithm and their performance measurements:

we need to pay attention to some concepts on how these algorithms are designed:

  1. linear — do the sort in place and take an array as a whole.
    1. Bubble Sort
    2. Selection Sort
    3. Insertion Sort
  2. divide and conquer — break the questions into smaller chunks
    1. Merge Sort
    2. Quick Sort

to measure performance

  1. number of swaps (Swap Methods)
  2. number of comparisons (Find methods )

to measure their orders: BIG- O notation

 

Data Structure – Bubble Sort

for sorting an array using bubble sort you can use this. you can copy paste the code and run them, see the output and compare how different they are working.


/**
*
* @author Unknown_
*/
public class BubbleSort {

public static int[] myArray = new int[]{10, 2, 5, 20, 90, 12, 31, 5};

/**
* basic sorting -- check as much as you can to make sure it has sorted everything in array.
* @param myArray
*/
public void sort(int[] myArray) {

if (myArray.length == 0) {
return;
}

int counter = myArray.length;
while (counter != 0) {
int tmp = 0;
for (int index = 0; index + 1 < myArray.length; index++) { tmp = 0; if (myArray[index] >= myArray[index + 1]) {
tmp = myArray[index];
myArray[index] = myArray[index + 1];
myArray[index + 1] = tmp;

}
showContent(myArray);
}
counter--;
}

}

/**
* enhanced
*
* @param myArray
*/
public void sort2(int[] myArray) {

if (myArray.length == 0) {
return;
}

int tmp = 0;
for (int j = myArray.length; j > 0; j--) {

for (int i = 0; i + 1 < j; i++) { tmp = 0; if (myArray[i] >= myArray[i + 1]) {
tmp = myArray[i];
myArray[i] = myArray[i + 1];
myArray[i + 1] = tmp;

}
System.out.printf("i = %d , j= %d ", i, j);
showContent(myArray);
}
}
}

/**
* resetting array content to what it was.
*/
public static void resetData() {
myArray = new int[]{10, 2, 5, 20, 90, 12, 31, 5};
}

/**
* showing content of array
* @param arr
*/
public void showContent(int[] arr) {

System.out.print("[ ");
for (int i : arr) {
System.out.printf("%d, ", i);
}
System.out.println(" ]");
}

public static void main(String[] args) {
BubbleSort bs = new BubbleSort();

bs.showContent(BubbleSort.myArray);
bs.sort(BubbleSort.myArray);
bs.showContent(BubbleSort.myArray);

bs.resetData();

System.out.println("---------Sort2-------");
bs.showContent(BubbleSort.myArray);
System.out.println("====== starting ====");
bs.sort2(BubbleSort.myArray);
System.out.println("====== finished ====");
bs.showContent(BubbleSort.myArray);

}

}

and its output became something like this …

run:
[ 10, 2, 5, 20, 90, 12, 31, 5,  ]
[ 2, 10, 5, 20, 90, 12, 31, 5,  ]
[ 2, 5, 10, 20, 90, 12, 31, 5,  ]
[ 2, 5, 10, 20, 90, 12, 31, 5,  ]
[ 2, 5, 10, 20, 90, 12, 31, 5,  ]
[ 2, 5, 10, 20, 12, 90, 31, 5,  ]
[ 2, 5, 10, 20, 12, 31, 90, 5,  ]
[ 2, 5, 10, 20, 12, 31, 5, 90,  ]
[ 2, 5, 10, 20, 12, 31, 5, 90,  ]
[ 2, 5, 10, 20, 12, 31, 5, 90,  ]
[ 2, 5, 10, 20, 12, 31, 5, 90,  ]
[ 2, 5, 10, 12, 20, 31, 5, 90,  ]
[ 2, 5, 10, 12, 20, 31, 5, 90,  ]
[ 2, 5, 10, 12, 20, 5, 31, 90,  ]
[ 2, 5, 10, 12, 20, 5, 31, 90,  ]
[ 2, 5, 10, 12, 20, 5, 31, 90,  ]
[ 2, 5, 10, 12, 20, 5, 31, 90,  ]
[ 2, 5, 10, 12, 20, 5, 31, 90,  ]
[ 2, 5, 10, 12, 20, 5, 31, 90,  ]
[ 2, 5, 10, 12, 5, 20, 31, 90,  ]
[ 2, 5, 10, 12, 5, 20, 31, 90,  ]
[ 2, 5, 10, 12, 5, 20, 31, 90,  ]
[ 2, 5, 10, 12, 5, 20, 31, 90,  ]
[ 2, 5, 10, 12, 5, 20, 31, 90,  ]
[ 2, 5, 10, 12, 5, 20, 31, 90,  ]
[ 2, 5, 10, 5, 12, 20, 31, 90,  ]
[ 2, 5, 10, 5, 12, 20, 31, 90,  ]
[ 2, 5, 10, 5, 12, 20, 31, 90,  ]
[ 2, 5, 10, 5, 12, 20, 31, 90,  ]
[ 2, 5, 10, 5, 12, 20, 31, 90,  ]
[ 2, 5, 10, 5, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
---------Sort2-------
[ 10, 2, 5, 20, 90, 12, 31, 5,  ]
====== starting ====
i = 0 , j= 8 [ 2, 10, 5, 20, 90, 12, 31, 5,  ]
i = 1 , j= 8 [ 2, 5, 10, 20, 90, 12, 31, 5,  ]
i = 2 , j= 8 [ 2, 5, 10, 20, 90, 12, 31, 5,  ]
i = 3 , j= 8 [ 2, 5, 10, 20, 90, 12, 31, 5,  ]
i = 4 , j= 8 [ 2, 5, 10, 20, 12, 90, 31, 5,  ]
i = 5 , j= 8 [ 2, 5, 10, 20, 12, 31, 90, 5,  ]
i = 6 , j= 8 [ 2, 5, 10, 20, 12, 31, 5, 90,  ]
i = 0 , j= 7 [ 2, 5, 10, 20, 12, 31, 5, 90,  ]
i = 1 , j= 7 [ 2, 5, 10, 20, 12, 31, 5, 90,  ]
i = 2 , j= 7 [ 2, 5, 10, 20, 12, 31, 5, 90,  ]
i = 3 , j= 7 [ 2, 5, 10, 12, 20, 31, 5, 90,  ]
i = 4 , j= 7 [ 2, 5, 10, 12, 20, 31, 5, 90,  ]
i = 5 , j= 7 [ 2, 5, 10, 12, 20, 5, 31, 90,  ]
i = 0 , j= 6 [ 2, 5, 10, 12, 20, 5, 31, 90,  ]
i = 1 , j= 6 [ 2, 5, 10, 12, 20, 5, 31, 90,  ]
i = 2 , j= 6 [ 2, 5, 10, 12, 20, 5, 31, 90,  ]
i = 3 , j= 6 [ 2, 5, 10, 12, 20, 5, 31, 90,  ]
i = 4 , j= 6 [ 2, 5, 10, 12, 5, 20, 31, 90,  ]
i = 0 , j= 5 [ 2, 5, 10, 12, 5, 20, 31, 90,  ]
i = 1 , j= 5 [ 2, 5, 10, 12, 5, 20, 31, 90,  ]
i = 2 , j= 5 [ 2, 5, 10, 12, 5, 20, 31, 90,  ]
i = 3 , j= 5 [ 2, 5, 10, 5, 12, 20, 31, 90,  ]
i = 0 , j= 4 [ 2, 5, 10, 5, 12, 20, 31, 90,  ]
i = 1 , j= 4 [ 2, 5, 10, 5, 12, 20, 31, 90,  ]
i = 2 , j= 4 [ 2, 5, 5, 10, 12, 20, 31, 90,  ]
i = 0 , j= 3 [ 2, 5, 5, 10, 12, 20, 31, 90,  ]
i = 1 , j= 3 [ 2, 5, 5, 10, 12, 20, 31, 90,  ]
i = 0 , j= 2 [ 2, 5, 5, 10, 12, 20, 31, 90,  ]
====== finished ====
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
BUILD SUCCESSFUL (total time: 0 seconds)

order of complexity is

O(N^2) in the worst case and average case scenario.

O(n) when the array is pre-sorted even in a large number of data.

it doesn’t use  any additional memory and everything will happen in place.

it needs many iterations through the array (Named it PASS) to finish the sorting. in my first algorithm you can find this PASS checking by WHILE loop and in the second algorithm it’s the outer FOR loop.

Exceptions Part 1 – Basics

if an application doesn’t behave as it supposes, there is a way to let outside world know. this way is to raise an exception.

below is the exception hierarchy in java
since Exception itself is an object and to be raised they should be thrown, the need to extends from Objects class and then Throwable interface.

Objects|
+- Throwable (interface)         
          |
+ ----------------------------------+
|                                    Exception
|                      ---------------+---------------------
|                      |                                    |
Error                  RunTimeException                     rest of the Exceoptions
[counted as Checked]   [Checked Exceptions]                [Unchecked Exceptions]

Checked & Unchecked Exceptions

Checked and unchecked exceptions are the two main categories that java separated all the unintended status of application into.

Unchecked Exceptions is the category that technically JVM will take care of that and when they raise the application terminated and won’t get into a situation that users left in a limbo with no information. so we are developer don’t need to take care of them in our application.

Checked exceptions are the unintentional behaviour of the application that might not be our preferable and they needed to be handled by developers.

Method Stack & Exception:

when an checked exception happenes, it needs to be handled somewhere in code. so the matter is where and who needs to handle it. this only means, when in memory stack methods will be pushed in top of each other from buttom of stack to the place that throws the exception, anyone of these methods can be responsible for handling that exception. the only factor is which one make sense more to handles that.

quick notes: try -finally – normally to handle closing files or streams. or network sockets.

 

you can use something like below snippet in any part of your code. even in try nad finally block, for example you are trying to handle file related exceptions so you can catch it or not catch it and let callers method handles it.


public void myMethod() throws IOException{

// doing something with file streams

try{

//doing the rest of stuff

}finally{

//doing some cleaning if I need.

}

}

Exception Part 2 – Customized Exceptions

Since all the exception in java are extended from exception class and counted as Objects, you can also extend the same way and generate your own exceptions, however most of them time existed standard exceptions are quite enough for application and normally it’s better to use the existed ones, but there are cases that you might need your own customized version of exceptions or currently existed ones might not address your need. so, in that case, you can simply extend from Exception class (and not from RunTimeException class) to make sure they could be unchecked Exceptions and also make sure you have a proper constructor for that.

about the constructors, you have below options …

  1. One without any parameters
  2. One with some details such as message
  3. one with some details such as message and the originally-thrown exception.

however you can define your own, but technically above constructors will satisfy most of the needs.

also Exception class itself provides almost everything you may need for further implementation, so remember to call super to use them, whenever you need.


public class MySpecialException extends Exception{

public MySpecialException(String reason, String additionalMessage){

super(reason + " = " +additionalMessage );}

}

public MySpecialException(String reason, String additionalMessage, Throwable e){

super(reason + " = " +additionalMessage, e );}

}

}

then inside your code you can easily call it like below snippet code.


public void myMethod() throws MySpecialException {

if(something happened wrong){
throw new MySpecialException("Reason of the issue","something really bad happened!");

}

 

try{

//opening a file for example

}catch(FileNotFoundException e){

throw new MySpecialException("Reason of the issue","something really bad happened!", e);

}

 

Working with Files JDK 1.6 or older

there is an easy way to work with files in JDK 8 but in older version when we need to read the files there was a quick coding line we had to do. in here I brought a simple example on how to open and read a text file in older versions of java.


import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
*
* @author Unknown_
*/
public class TextFile_OlderJDK {

public static void main(String[] args) {
BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader("myFile.txt"));
String line = null;
while ((line = reader.readLine()) != null) {
System.out.println("" + line);
}
} catch (FileNotFoundException ex) {
Logger.getLogger(TextFile_OlderJDK.class.getName()).log(Level.SEVERE, null, ex);
} catch (IOException ex) {
Logger.getLogger(TextFile_OlderJDK.class.getName()).log(Level.SEVERE, null, ex);
} catch (Exception e) {
e.printStackTrace();
} finally {

// this will run every time
try {
if (reader != null) {
reader.close();
}
} catch (IOException ex) {
Logger.getLogger(TextFile_OlderJDK.class.getName()).log(Level.SEVERE, null, ex);
}

}

}

}

 

Passing By-Value & By-Reference

for me there was a very big confusion when I tried to learn java at the beginning. so I will try to clear the situation for anyone who might have some questions about how Java treats with parameters inside its methods.

  • Method parameters as primitive type: the value will be copied into the methods scope and the result won’t affect outside the methods unless you return the result. so it’s by value.
  • Method parameters as class reference: the value will be copied into the methods scope and the result won’t affect outside the methods unless you return the result. so it’s by value.

so it shows, it doesn’t matter whether parameters of the methods are primitive types or class instance, the params will always be copied for methods and outside of the methods don’t have access to its internal changes.

if you want to take affect the by-reference you can use and update the content of the objects using references inside the method. that’s the only way I am using to change whatever I want and make that consistent outside of my methods body.

so since the parameters are immutable, any changes won’t affect outside, so for changing outside variables, the only way is to update and do the change inside the methods using the class variables itself, for example:

public void myChangerMethod(Person p1, Person p2){

// doing anything with p1 nad p2 won’t affect unless you can use these references to

Person p_temp = p1;

p1 = p2;

p2 = p_temp; // these lines won’t change anything outside of this method.

//change their object content itself. something like below:

String name_temp = p1.getName();

p1.setName(P2.getName()); // modifying content

p2.setName(name_temp); // modifying the first content.

}

 

Reflection – A Quick WrapUp :)

ok, I talked about reflection in couple posts specifically and indirectly I referred to them in a few others, but just to wrap up, Reflections are very useful and very powerful tool that every developers needed them in their toolbox. now, when you read and practice what I have explained so nfar, you can see the connections between that package with others and also you can see its footprints everywhere in Java frameworks and other utilities.

Reflection generally can be used to retrive the information about every Class Type.

you can load and reload Class definition into memory and you can trace everything inside classes, even inner classes (as I explained in my examples in Reflections)

Also Reflection will be used in Annotation processing behind the scene by JDK.

Also for Serialization, Java itself uses reflection to get the SerialVerUID fields to validate the classes.

to make that easy, I can just tell that wherever you saw something might use Class Type, you can now think of Reflection.