Data Structure – Selection Sort

in this sort, it’s very much like bubble sort since in bubble the largest element should be in the RIGHT side, in Selection sort we are looking for SMALLEST items and select that then find its proper location which will be the most LEFT side and REPLACE it with whatever in that location.

still, LEFT side is smallest and right side has the largest, but the number os swaps are decreased however to find the proper location we have to do a lot of comparisons.

Orders:

  • the worst case scenario O(N^2)
  • average case scenarios O(N^2) –> but in practice
  • Selection sort is better than Bubble sort,
  • Selection sort is worse than Insertion sort,
  •  best case scenario O(N^2) — since it has lots of comparisons.

where to use:

  • not good for large unsorted data sets, and in General.
  • since it has a few swaps N, it might be good in cases where the cost of Comparisons is cheaper than swaps.
  • from space and memory perspectives, since it’s working on the array, itself, it’s good.

how to code:

/**
*
* @author Navid_
*/
public class SelectionSort {

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

/**
* 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) {
SelectionSort ss = new SelectionSort();

ss.showContent(SelectionSort.myArray);
ss.sort(SelectionSort.myArray);
ss.showContent(SelectionSort.myArray);

}

public void sort(int[] myArray) {

for (int i = 0; i < myArray.length; i++) {
//find smallest
int smallestIndex = searchToFindSmallest(myArray, i, myArray.length);

// now repalce the smallest with the next item in the unsorted array
swap(myArray, smallestIndex, i);

showContent(myArray);
}

}

/**
* smallest item index will be returned.
*
* @return
*/
public int searchToFindSmallest(int[] arr, int startSearch, int limitSearch) {

int smallest = startSearch;
boolean foundSthNew = false;
for (int index = startSearch; index < limitSearch; index++) {
if (arr[index] < arr[smallest]) {
// so we find something smaller
System.out.printf("Found a samllest item ... arr[%d]=%d\n",index,arr[index] );
smallest = index;
foundSthNew = true;
}
}

if (foundSthNew) {

return smallest;
} else {
return -1;
}
}

private void swap(int[] myArray, int smallestIndex, int i) {

int tmp = 0;
if (smallestIndex == -1) {
System.out.println("no swapping anymore.\n");
return;
}
tmp = myArray[i];
myArray[i] = myArray[smallestIndex];
myArray[smallestIndex] = tmp;
System.out.printf("Swapping arr[%d]=%d with arr[%d]=%d\n",i,myArray[i],smallestIndex,myArray[smallestIndex]);
}

}

and it’s output will be something like this …

run:
[ 10, 2, 5, 20, 90, 12, 31, 5,  ]
Found a samllest item ... arr[1]=2
Swapping arr[0]=2 with arr[1]=10
[ 2, 10, 5, 20, 90, 12, 31, 5,  ]
Found a samllest item ... arr[2]=5
Swapping arr[1]=5 with arr[2]=10
[ 2, 5, 10, 20, 90, 12, 31, 5,  ]
Found a samllest item ... arr[7]=5
Swapping arr[2]=5 with arr[7]=10
[ 2, 5, 5, 20, 90, 12, 31, 10,  ]
Found a samllest item ... arr[5]=12
Found a samllest item ... arr[7]=10
Swapping arr[3]=10 with arr[7]=20
[ 2, 5, 5, 10, 90, 12, 31, 20,  ]
Found a samllest item ... arr[5]=12
Swapping arr[4]=12 with arr[5]=90
[ 2, 5, 5, 10, 12, 90, 31, 20,  ]
Found a samllest item ... arr[6]=31
Found a samllest item ... arr[7]=20
Swapping arr[5]=20 with arr[7]=90
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
no swapping anymore.
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
no swapping anymore.
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
[ 2, 5, 5, 10, 12, 20, 31, 90,  ]
BUILD SUCCESSFUL (total time: 0 seconds)
Advertisements

Data Structure – Insertion Sort

it’s similar to bubbleSort, but it happened only in 1 PASS

by comparing every two items from left to right in array, pull one item from array then find its proper place and insert it there, then shift the rest of items – normally it would be SORTED items.

LEFT considered SORTED

items in RIGHT side considered UNSORTED.

when to use:

  • small datasets
  • nearly sorted large datasets
  • because the number of comparisons and swaps is relatively small.

orders:

  • very similar to  bubble sort
  • O(N^2) in worst case and average case
  • and for large semi-sorted data or small datasets we can say O(N)

space:

doesn’t need more data spaces so it can be done in the same place or in devices with minimum spaces.

how to implement:


/**
*
* @author Navid_
*/
public class InsertionSort {

public static int[] arr = new int[]{5, 10, 13, 90, 1};

public void sort(int[] array) {

int tmp = 0;
for (int i = 0; i + 1 < array.length; i++) { //loop through array if (array[i] >= array[i + 1]) {
// find the guy that needs to be inserted somewhere
System.out.printf("found an item to sort...array[%d] = %d\n", i + 1, array[i + 1]);
tmp = array[i + 1]; // save the unsorted guy
for (int k = i + 1; k >= 0; k--) {

//just handling when the first item is still larger than temp;
if (k == 0) {

System.out.printf("shifting to the RIGHT = %d and REPLACING the FIRST item in array with = %d, then BREAK.\n", array[k], tmp);
array[k] = tmp;
showContent(array);
break;
}

// trying to find the location and insert
if (array[k - 1] > tmp) {
System.out.printf("SHIFT to RIGHT= %d.\n", array[k - 1]);
array[k] = array[k - 1];
showContent(array);
} else {
System.out.printf("Found Place to INSERT so inserting ... array[%d] = %d.\n", k - 1, tmp);
array[k - 1] = tmp;
showContent(array);
break;
}

}

}

}

}

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

/**
* 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) {

InsertionSort is = new InsertionSort();

is.showContent(InsertionSort.arr);
is.sort(InsertionSort.arr);
is.showContent(InsertionSort.arr);

}

}

and its output will be something like this …

run:
[ 5, 10, 13, 90, 1,  ]
found an item to sort...array[4] = 1
SHIFT to RIGHT= 90.
[ 5, 10, 13, 90, 90,  ]
SHIFT to RIGHT= 13.
[ 5, 10, 13, 13, 90,  ]
SHIFT to RIGHT= 10.
[ 5, 10, 10, 13, 90,  ]
SHIFT to RIGHT= 5.
[ 5, 5, 10, 13, 90,  ]
shifting to the RIGHT = 5 and REPLACING the FIRST item in array with = 1, then BREAK.
[ 1, 5, 10, 13, 90,  ]
[ 1, 5, 10, 13, 90,  ]
BUILD SUCCESSFUL (total time: 0 seconds)

NOTE:

so for small amount of items you can still

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 &lt; myArray.length; index++) { tmp = 0; if (myArray[index] &gt;= 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 &gt; 0; j--) {

for (int i = 0; i + 1 &lt; j; i++) { tmp = 0; if (myArray[i] &gt;= 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!");

}

&nbsp;

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);
}

}

}

}