Testing in Java Part 1 – Basics

Different types of testing:

  1. System test / End to End test normally will be done via QA
  2. Aggregate Test / testing component to make sure the business functionalities with all the dependencies could be done as they supposed to. it took longer than unit test since it has a database to set up and tear down, or clean up some stuff, etc.
  3. Unit test / testing each individual functionality. no dependencies.

 

3 Stages every test case needs to have:

  1.  prepare the environment for testing (preparing any requirement before actually testing the behaviour – it might happen in every method.)
  2. the behaviour to test (the actual function you want to test – if that’s too big, you’re testing a lot of functionalities and if something happened you need a way to find that between that complex tests)
  3. checking the result (Assertions)

making testing in orders might make dependencies between unit tests which don’t have any meaning other than, Aggregate testing instead of testing every individual function.

NOTE: every test methods in your test class, should only test one behaviour, even if preparing and function parts of couple test methods will be similar but and the differences will be in assertion parts, then it might show that you are testing differents parts/ behaviours of the function.

NOTE: Make your test methods names, expressing the behaviour of testing, make sure they expose what you want to test.

NOTE: One test class for one Class object.

NOTE: testing the throwing of an exception in the case of a failure of the application?

<br data-mce-bogus="1">

<strong>@Test(Expected=MyTypeOfException.class)</strong>

&nbsp;

 

 

 

 

Advertisements

Data Structure – Merge Sort

under divide and conquer algorithms in sort category, we are reaching to Merge Sort, which basically

  1. Takes the input array and BREAK/DIVIDE it into half.
  2. call the same BREAK/DIVIDE function on the smaller halves , again – RECURSIVE function, with a base condition of array.size =1
  3. array.size() = 1 counted as SORTED. now rebuilding.
  4. in the time of rebuilding process for the smaller chunk of data, we are using previous smaller chunk in each step, meaning, smaller sorted data as a result of last previous recursive call.
  5. and then rebuild the array after sorting the smaller previous parts.

NOTE: in this sorting algorithm, we need a copy of the array, in a merging process and that’s the tricky part.

 big picture:

we have two main function in Merge Sort

  1. Partitioning(array, startIndex, endIndex) // breaking into pieces
  2. Merging(array, startIndex, midIndex, endIndex) // sorting and rebuilding

/**
* breaking the array into smaller pieces, RECURSIVE happened here.
*
* @param arrSRC
* @param startIndex
* @param endIndex
*/
public void partitioning(int[] arrSRC, int startIndex, int endIndex) {

System.out.println("Begin Dividing/Breaking by this array...");
showContent(arrSRC, startIndex, endIndex);

if (endIndex - 1 == startIndex) {
System.out.println("Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.");
return;
}

System.out.println("Dividing/Breaking - into smaller chunk - Finding Mid Index.");
int mid = (startIndex + endIndex) / 2;

System.out.printf("Dividing/Breaking - into smaller chunk -  startIndex: %d - endIndex: %d = midIndex:%d\n", startIndex, endIndex, mid);

partitioning(arrSRC, startIndex, mid);
partitioning(arrSRC, mid, endIndex);

doMerge(arrSRC, startIndex, mid, endIndex);

}

/**
* do the actual merge/build task.
*
* @param arrSrc
* @param startIndex
* @param mid
* @param endIndex
*/
private void doMerge(int[] arrSrc, int startIndex, int mid, int endIndex) {

//tricky partitioning in MERGE SORT since we need a semi-sorted array which was made in previous recursive function call.
System.out.println("Begin Conquering/ building array again...");

arrayCopy(arrSrc, tempArr, startIndex, endIndex);

int leftIndex = startIndex;
int rightIndex = mid;
int index = startIndex;

while (leftIndex < mid && rightIndex < endIndex) {
if (tempArr[leftIndex] <= tempArr[rightIndex]) {

arrSrc[index] = tempArr[leftIndex];
leftIndex++;

} else {
arrSrc[index] = tempArr[rightIndex];
rightIndex++;
}
index++;
}

while (leftIndex < mid) {
arrSrc[index] = tempArr[leftIndex];
leftIndex++;
index++;
}
while (rightIndex < endIndex) {
arrSrc[index] = tempArr[rightIndex];
rightIndex++;
index++;
}

System.out.print("Final Result ... \n\t ");
showContent(arrSrc, startIndex, endIndex);
System.out.println("");

}

Orders:

in the worst case scenario O(N x LogN), since it’s breaking the target into a smaller chunk. so it’s good for large unsorted data sets.

when to use?

when you want to do the sort in a multi-thread environment so every thread can do one part of sorting and then one manager thread can stick the parts together.

how to implement?


package com.navid.ds.practice.sorting.divideconqure;

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

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

public MergeSort() {

tempArr = new int[myArray.length];

}

/**
* breaking the array into smaller pieces, RECURSIVE happened here.
*
* @param arrSRC
* @param startIndex
* @param endIndex
*/
public void partitioning(int[] arrSRC, int startIndex, int endIndex) {

System.out.println("Begin Dividing/Breaking by this array...");
showContent(arrSRC, startIndex, endIndex);

if (endIndex - 1 == startIndex) {
System.out.println("Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.");
return;
}

System.out.println("Dividing/Breaking - into smaller chunk - Finding Mid Index.");
int mid = (startIndex + endIndex) / 2;

System.out.printf("Dividing/Breaking - into smaller chunk -  startIndex: %d - endIndex: %d = midIndex:%d\n", startIndex, endIndex, mid);

partitioning(arrSRC, startIndex, mid);
partitioning(arrSRC, mid, endIndex);

doMerge(arrSRC, startIndex, mid, endIndex);

}

/**
* do the actual merge/build task.
*
* @param arrSrc
* @param startIndex
* @param mid
* @param endIndex
*/
private void doMerge(int[] arrSrc, int startIndex, int mid, int endIndex) {

//tricky partitioning in MERGE SORT since we need a semi-sorted array which was made in previous recursive function call.
System.out.println("Begin Conquering/ building array again...");

arrayCopy(arrSrc, tempArr, startIndex, endIndex);

int leftIndex = startIndex;
int rightIndex = mid;
int index = startIndex;

while (leftIndex < mid && rightIndex < endIndex) {
if (tempArr[leftIndex] <= tempArr[rightIndex]) {

arrSrc[index] = tempArr[leftIndex];
leftIndex++;

} else {
arrSrc[index] = tempArr[rightIndex];
rightIndex++;
}
index++;
}

while (leftIndex < mid) {
arrSrc[index] = tempArr[leftIndex];
leftIndex++;
index++;
}
while (rightIndex < endIndex) {
arrSrc[index] = tempArr[rightIndex];
rightIndex++;
index++;
}

System.out.print("Final Result ... \n\t ");
showContent(arrSrc, startIndex, endIndex);
System.out.println("");

}

/**
* This array Copy method is just an effort to expose the
*
* @param arrSrc
* @param arrDest
* @param lowerIndex
* @param higherIndex
*/
public void arrayCopy(int[] arrSrc, int[] arrDest, int lowerIndex, int higherIndex) {

for (int i = lowerIndex; i < higherIndex; i++) {
arrDest[i] = arrSrc[i];
}

}

public void showContent(int[] arr, int start, int end) {

System.out.print("[ ");
for (int i = start; i < end; i++) {
System.out.printf("%d, ", arr[i]);

}
System.out.println(" ]");
}

public static void main(String[] args) {

MergeSort ms = new MergeSort();

ms.partitioning(myArray, 0, myArray.length);

}

}

 

 

output

run:
Begin Dividing/Breaking by this array...
[ 10, 2, 5, 20, 90, 12, 31, 5,  ]
Dividing/Breaking - into smaller chunk - startIndex: 0 - endIndex: 8 = midIndex:4
Begin Dividing/Breaking by this array...
[ 10, 2, 5, 20,  ]
Dividing/Breaking - into smaller chunk - startIndex: 0 - endIndex: 4 = midIndex:2
Begin Dividing/Breaking by this array...
[ 10, 2,  ]
Dividing/Breaking - into smaller chunk - startIndex: 0 - endIndex: 2 = midIndex:1
Begin Dividing/Breaking by this array...
[ 10,  ]
Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.
Begin Dividing/Breaking by this array...
[ 2,  ]
Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.
Begin Conquering/ building array again...
Final Result ... 
     [ 2, 10,  ]

Begin Dividing/Breaking by this array...
[ 5, 20,  ]
Dividing/Breaking - into smaller chunk - startIndex: 2 - endIndex: 4 = midIndex:3
Begin Dividing/Breaking by this array...
[ 5,  ]
Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.
Begin Dividing/Breaking by this array...
[ 20,  ]
Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.
Begin Conquering/ building array again...
Final Result ... 
     [ 5, 20,  ]

Begin Conquering/ building array again...
Final Result ... 
     [ 2, 5, 10, 20,  ]

Begin Dividing/Breaking by this array...
[ 90, 12, 31, 5,  ]
Dividing/Breaking - into smaller chunk - startIndex: 4 - endIndex: 8 = midIndex:6
Begin Dividing/Breaking by this array...
[ 90, 12,  ]
Dividing/Breaking - into smaller chunk - startIndex: 4 - endIndex: 6 = midIndex:5
Begin Dividing/Breaking by this array...
[ 90,  ]
Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.
Begin Dividing/Breaking by this array...
[ 12,  ]
Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.
Begin Conquering/ building array again...
Final Result ... 
     [ 12, 90,  ]

Begin Dividing/Breaking by this array...
[ 31, 5,  ]
Dividing/Breaking - into smaller chunk - startIndex: 6 - endIndex: 8 = midIndex:7
Begin Dividing/Breaking by this array...
[ 31,  ]
Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.
Begin Dividing/Breaking by this array...
[ 5,  ]
Dividing/Breaking - into smaller chunk - found only one item in array, so it's counted as SORTED.
Begin Conquering/ building array again...
Final Result ... 
     [ 5, 31,  ]

Begin Conquering/ building array again...
Final Result ... 
     [ 5, 12, 31, 90,  ]

Begin Conquering/ building array again...
Final Result ... 
     [ 2, 5, 5, 10, 12, 20, 31, 90,  ]

BUILD SUCCESSFUL (total time: 0 seconds)

 

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)

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.