# Selenium Automation | Java Sort Algorithms 21-25

As soon as you write Selenium Automation in your resume, interviewer is bound to give you a sheet of paper & ask write a Java program. Though Selenium doesnâ€™t require extensive Java knowledge but still there is a set of basic Java programs that you should be able to write on-the-spot. Continuing on our Java interview series for Selenium Automation, this article covers five of the common Java Sort programs frequently asked in the basic technical interview. The questions are easy, but donâ€™t forget to mark these java programs in your to do list before attending any entry-level technical interview for Selenium automation testing.

Flashback: **Selenium Automation | Java String Algorithms 16-20**

**Bubble Sort**

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order. Sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

```
package Java;
public class BubbleSort {
// Complexity = O(n2) | Best case = O(n)
static int temp;
public static void bubble_srt(int array[]) {
int n = array.length;
int k;
for (int m = n; m >= 0; m--) {
for (int i = 0; i < n - 1; i++) { k = i + 1; if (array[i] > array[k]) {
temp = array[i];
array[i] = array[k];
array[k] = temp;
}
}
printNumbers(array);
}
}
private static void printNumbers(int[] input) {
for (int i = 0; i < input.length; i++) {
System.out.print(input[i] + ", ");
}
System.out.println("\n");
}
public static void main(String[] args) {
int[] input = {4,2,9,6,23,12,34,0,1};
bubble_srt(input);
}
}
```

Bubble sort has worst-case and average complexity both Ðž(n2), where n is the number of items being sorted. There exist many sorting algorithms, such as merge sort with substantially better worst-case or average complexity of O(n log n). Even other Ðž(n2) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore, bubble sort is not a practical sorting algorithm when n is large.

**Insertion Sort**

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:

- Simple implementation: Jon Bentley shows a three-line C version, and a five-line optimized version.
- Efficient for (quite) small data sets, much like other quadratic sorting algorithms.
- More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort.
- Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(nk) when each element in the input is no more than k places away from its sorted position.
- Stable; i.e., does not change the relative order of elements with equal keys.
- In-place; i.e., only requires a constant amount O(1) of additional memory space.
- Online; i.e., can sort a list as it receives it.

The Logic: Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

```
package Java;
public class InsertionSort {
// Complexity | Best O(n) | Worst O(n2) | Average O(n2)
public static int[] IS(int[] input){
int temp;
for (int i = 1; i < input.length; i++) { for(int j = i ; j > 0 ; j--){
if(input[j] < input[j-1]){
temp = input[j];
input[j] = input[j-1];
input[j-1] = temp;
}
}
}
return input;
}
public static void main(String a[]){
int[] arr1 = {10,34,2,56,7,67,88,42};
int[] arr2 = IS(arr1);
for(int i:arr2){
System.out.print(i);
System.out.print(", ");
}
}
}
```

The best case input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., O(n)). During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array.

The simplest worst case input is an array sorted in reverse order. The set of all worst case inputs consists of all arrays where each element is the smallest or second-smallest of the elements before it. In these cases every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. This gives insertion sort a quadratic running time (i.e., O(n2)).

**Selection Sort**

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

```
package Java;
public class SelectionSort {
// Complexity = n(n-1)/2 | O(n2)
public static int[] SS(int[] a){
for (int i = 0; i < a.length - 1; i++){
int index = i;
for (int j = i + 1; j < a.length; j++)
if (a[j] < a[index])
index = j;
int temp = a[index];
a[index] = a[i];
a[i] = temp;
}
return a;
}
public static void main(String a[]){
int[] arr1 = {10,34,2,56,7,67,88,42};
int[] arr2 = SS(arr1);
for(int i:arr2){
System.out.print(i);
System.out.print(", ");
}
}
}
```

**Merge Sort**

Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.

```
package Java;
public class MergeSort {
private static int[] array;
private static int[] tempMergArr;
private static int length;
public static void sort(int inputArr[]) {
doMergeSort(0, length - 1);
}
private static void doMergeSort(int lowerIndex, int higherIndex) {
if (lowerIndex < higherIndex) {
int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
// Below step sorts the left side of the array
doMergeSort(lowerIndex, middle);
// Below step sorts the right side of the array
doMergeSort(middle + 1, higherIndex);
// Now merge both sides
mergeParts(lowerIndex, middle, higherIndex);
}
}
private static void mergeParts(int lowerIndex, int middle, int higherIndex) {
for (int i = lowerIndex; i <= higherIndex; i++) {
tempMergArr[i] = array[i];
}
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) {
if (tempMergArr[i] <= tempMergArr[j]) {
array[k] = tempMergArr[i];
i++;
} else {
array[k] = tempMergArr[j];
j++;
}
k++;
}
while (i <= middle) {
array[k] = tempMergArr[i];
k++;
i++;
}
}
public static void main(String a[]){
int[] inputArr = {45,23,11,89,77,98,4,28,65,43};
sort(inputArr);
for(int i:inputArr){
System.out.print(i);
System.out.print(" ");
}
}
}
```

**Quick Sort**

Quicksort is a comparison sort, meaning that it can sort items of any type for which a “less-than” relation (formally, a total order) is defined. In efficient implementations it is not a stable sort, meaning that the relative order of equal sort items is not preserved. Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting. It is very similar to selection sort, except that it does not always choose worst-case partition.

Mathematical analysis of quicksort shows that, on average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare.

```
package Java;
public class QuickSort {
private int array[];
private int length;
public void sort(int[] inputArr) {
if (inputArr == null || inputArr.length == 0) {
return;
}
this.array = inputArr;
length = inputArr.length;
quickSort(0, length - 1);
}
private void quickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number, I am taking pivot as middle index number
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two arrays
while (i <= j) {
while (array[i] < pivot) { i++; } while (array[j] > pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call quickSort() method recursively
if (lowerIndex < j)
quickSort(lowerIndex, j);
if (i < higherIndex)
quickSort(i, higherIndex);
}
private void exchangeNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String a[]){
QuickSort sorter = new QuickSort();
int[] input = {24,2,45,20,56,75,2,56,99,53,12};
sorter.sort(input);
for(int i:input){
System.out.print(i);
System.out.print(" ");
}
}
}
```

## Community Talks