## Data Sorting

Data Sorting is an operation involving systematic arrangement of data in an ordered sequence.

Sorting involves two operations:

1. ordering: arranging items in a sequence ordered by some criterion;
2. categorizing: grouping items with similar properties.

Sorting is a very common operation in many applications.

#### Why Sort Data?

By default most data are shuffled state, this is the opposite of sorted state. Shuffled data are random data.

Sorting is important because of these reasons:

1. Sorting makes up lookup or searching data efficient.
2. Sorting allows for efficient merging of sequences of data.
3. Through sorting we can process data in an order we want.

#### Which are the Sorting Algorithms?

Computer Scientists have come up with efficient algorithms to sort data with less computational resources and time.

Some of these algorithms include:

1. Bubble/Shell sort : Exchange two adjacent elements if they are out of order. Repeat until array is sorted.
2. Insertion sort : Scan successive elements for an out-of-order item, then insert the item in the proper place.
3. Selection sort : Find the smallest element in the array, and put it in the proper place. Swap it with the value in the first position. Repeat until array is sorted.
4. Quick sort : Partition the array into two segments. In the first segment, all elements are less than or equal to the pivot value. In the second segment, all elements are greater than or equal to the pivot value. Finally, sort the two segments recursively. Merge sort : Divide the list of elements in two parts, sort the two parts individually and then merge it.

#### Sorting Algorithm Examples

Let's start by creating this interface;

``````interface MaxValue<T> {
T getMaxObject();
}``````
##### (a). Insertion Sort Example
``````import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
* Generic insertion sort algorithm
* @author Solange U. Gasengayire
* @since 23/10/2017
*/
public class InsertionSort<T extends Comparable<T>> {

/**
* Sort an array of elements of type T in place
* @param data an array of n elements
*/
public void sort(T[] data) {
final int n = data.length;

// We consider the first element data[0] to be sorted.
// So we start with the second element --> thus j = 1
for (int j = 1; j < n; j++) {
T current = data[j];
int k = j;

// let's find the correct index k for current:
while (k > 0 && data[k-1].compareTo(current) > 0) {
data[k] = data[k-1];
k--;
}

// At this point, we've reached the proper place for current
data[k] = current;
}
}

/**
* Sort a list of elements of type T in place
* @param data an ArrayList of size n
*/
public void sort(ArrayList<T> data) {
final int n = data.size();

for (int j = 1; j < n; j++) {
T current = data.get(j);
int k = j;

// let's find the correct index k for current:
while (k > 0 && data.get(k-1).compareTo(current) > 0) {
data.set(k, data.get(k-1));
k--;
}

// At this point, we've reached the proper place for current
data.set(k, current);
}

}

/**
* Return a new list of sorted elements of type T
* IE: the sorting isn't done in place
* @param elements a list of size n
* @return a new list of sorted elements
*/
public List<T> sort(final List<T> elements) {

// Using a LinkedList is very efficient in adding elements in the middle
// (compared to an ArrayList) since it's done by simply rearranging
// pointers of the nodes in the list.
final List<T> sortedList = new LinkedList<>();

originalList: for (T element : elements) {
for (int i = 0; i < sortedList.size(); i++) {
if (element.compareTo(sortedList.get(i)) < 0) {
continue originalList;
}
}
}

return sortedList;
}

/**
* Tester method
*/
public static void main(String... args) {

// Example 1 : sorting an ArrayList of integers
InsertionSort<Integer> sortIntegers = new InsertionSort<>();
ArrayList<Integer> elements = new ArrayList<>(
Arrays.asList(98, 56, 42, 78, 36, 4, 12, 2)
);
sortIntegers.sort(elements);
elements.forEach(element -> System.out.print(element + " "));

// Example 2 : sorting an array of strings
InsertionSort<String> sortStrings = new InsertionSort<>();
String[] data = {"echo", "foxtrot", "charlie", "alpha", "bravo", "delta"};
sortStrings.sort(data);
System.out.println("\n" + Arrays.toString(data));

// Example 3 : sorting an empty array
InsertionSort<Character> sortChars = new InsertionSort<>();
Character[] chars = new Character[0];
sortChars.sort(chars);
System.out.println(Arrays.toString(chars));

// Example 4 : sorting an already sorted ArrayList of Integers
ArrayList<Integer> sorted = new ArrayList<>(
Arrays.asList(2, 4, 12, 36, 42, 56, 78, 98)
);
sortIntegers.sort(sorted);
elements.forEach(element -> System.out.print(element + " "));
System.out.println();

// Example 5 : sorting a list that is sorted in reverse order
final List<String> words = Arrays.asList(
"foxtrot", "echo", "delta", "charlie", "bravo", "alpha");
List<String> result = sortStrings.sort(words);
result.forEach(element -> System.out.print(element + " "));
System.out.println();
}

}``````
``````import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.print("Enter number of elements : ");
int n = s.nextInt();
int arr[] = new int[n];
System.out.println("Enter Arra to be sorted : ");
for (int i = 0; i < n; i++)
arr[i] = s.nextInt();
for (int i : arr)
System.out.print(i + " ");
}

private static void radixSort(int[] arr, int length) {
int max = getMax(arr, length);

for (int exp = 1; max / exp > 0; exp *= 10)
sort(arr, length, exp);
}

private static void sort(int[] arr, int length, int exp) {
List<Queue<Integer>> q = new ArrayList<Queue<Integer>>();
for (int i = 0; i < 10; i++)

for (int i = 0; i <= length; i++) {
}

int i = 0, k = 0;
while (i < 10) {
while (!q.get(i).isEmpty()) {
arr[k++] = q.get(i).remove();
}
i++;
}
}

private static int getMax(int[] arr, int length) {
int mx = arr[0];
for (int i = 1; i < length; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
}``````
##### (d) CountingSort
``````// Java implementation of Counting Sort
class CountingSort {

private void sort(char arr[]) {
int n = arr.length;

// The output character array that will have sorted arr
char output[] = new char[n];

// Create a count array to store count of inidividul
// characters and initialize count array as 0
int count[] = new int[256];
for (int i = 0; i < 256; ++i)
count[i] = 0;

// store count of each character
for (char anArr1 : arr) ++count[anArr1];

// Change count[i] so that count[i] now contains actual
// position of this character in output array
for (int i = 1; i <= 255; ++i)
count[i] += count[i - 1];

// Build the output character array
for (char anArr : arr) {
output[count[anArr] - 1] = anArr;
--count[anArr];
}

// Copy the output array to arr, so that arr now
// contains sorted characters
System.arraycopy(output, 0, arr, 0, n);
}

// Driver method
public static void main(String args[]) {
CountingSort ob = new CountingSort();
char arr[] = {'g', 'e', 'e', 'k', 's', 'f', 'o',
'r', 'g', 'e', 'e', 'k', 's'
};

ob.sort(arr);

System.out.print("Sorted character array is ");
for (char anArr : arr) System.out.print(anArr);
}
}``````
##### (b) MergeSort
``````import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;

/**
*
* java class used for sorting any type of list
*/
public class MergeSort<T extends MaxValue<T> & Comparable<T>> {

public void sort(List<T> arrayList) {
mergeSortSplit(arrayList, 0, arrayList.size() - 1);
}

private void mergeSortSplit(List<T> listToSort, int start, int end) {
if (start < end) {
int middle = (start + end) / 2;
mergeSortSplit(listToSort, start, middle);
mergeSortSplit(listToSort, middle + 1, end);
merge(listToSort, start, middle, end);
}
}

private void merge(ArrayList<T> listToSort, int start, int middle, int end) {
ArrayList<T> A = new ArrayList<T>(listToSort.subList(start, middle + 1));
ArrayList<T> B = new ArrayList<T>(listToSort.subList(middle + 1, end + 1));

int i = 0;
int j = 0;

for (int k = start; k <= end; k++) {
if (A.get(i).compareTo(B.get(j)) <= 0) {
listToSort.set(k, A.get(i));
i++;
} else {
listToSort.set(k, B.get(j));
j++;
}
}
}

public void sort(T[] array) {
mergeSortSplitArray(array, 0, array.length - 1);
}

private void mergeSortSplitArray(T[] listToSort, int start, int end) {
if (start < end) {
int middle = (start + end) / 2;
mergeSortSplitArray(listToSort, start, middle);
mergeSortSplitArray(listToSort, middle + 1, end);
mergeArray(listToSort, start, middle, end);
}
}

private void mergeArray(T[] listToSort, int start, int middle, int end) {
T[] A = (T[]) Array.newInstance(listToSort[0].getClass(), middle - start + 2);
T[] B = (T[]) Array.newInstance(listToSort[0].getClass(), end - middle + 1);
cloneArray(listToSort, A, start);
cloneArray(listToSort, B, middle + 1);

int i = 0;
int j = 0;

for (int k = start; k <= end; k++) {
if (A[i].compareTo(B[j]) <= 0) {
listToSort[k] = A[i];
i++;
} else {
listToSort[k] = B[j];
j++;
}
}
}

private void cloneArray(T[] listIn, T[] cloneInto, int start) {
for (int i = start; i < start + cloneInto.length - 1; i++) {
cloneInto[i - start] = listIn[i];
}

cloneInto[cloneInto.length - 1] = listIn[0].getMaxObject();
}
}``````
##### (e) Selection Sort
``````/ Java implementation of Counting Sort
class CountingSort {

private void sort(char arr[]) {
int n = arr.length;

// The output character array that will have sorted arr
char output[] = new char[n];

// Create a count array to store count of inidividul
// characters and initialize count array as 0
int count[] = new int[256];
for (int i = 0; i < 256; ++i)
count[i] = 0;

// store count of each character
for (char anArr1 : arr) ++count[anArr1];

// Change count[i] so that count[i] now contains actual
// position of this character in output array
for (int i = 1; i <= 255; ++i)
count[i] += count[i - 1];

// Build the output character array
for (char anArr : arr) {
output[count[anArr] - 1] = anArr;
--count[anArr];
}

// Copy the output array to arr, so that arr now
// contains sorted characters
System.arraycopy(output, 0, arr, 0, n);
}

// Driver method
public static void main(String args[]) {
CountingSort ob = new CountingSort();
char arr[] = {'g', 'e', 'e', 'k', 's', 'f', 'o',
'r', 'g', 'e', 'e', 'k', 's'
};

ob.sort(arr);

System.out.print("Sorted character array is ");
for (char anArr : arr) System.out.print(anArr);
}
}``````
##### (f) Heap Sort
``````// Java program for implementation of Heap Sort
public class HeapSort {

private void sort(int arr[]) {
int n = arr.length;

// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;

// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}

// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
private void heapify(int arr[], int n, int i) {
int largest = i;  // Initialize largest as root
int l = 2 * i + 1;  // left = 2*i + 1
int r = 2 * i + 2;  // right = 2*i + 2

// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;

// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;

// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;

// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}

/* A utility function to print array of size n */
private static void printArray(int arr[]) {
for (int anArr : arr) System.out.print(anArr + " ");
System.out.println();
}

// Driver program
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};

HeapSort ob = new HeapSort();
ob.sort(arr);

System.out.println("Sorted array is");
printArray(arr);
}
}``````
##### (g) Quick Sort
``````import java.util.ArrayList;
import java.util.Collections;

public class QuickSort<T extends Comparable<T>>
{
private int partition(ArrayList<T> arrayList, int start, int end) {
T pivot = arrayList.get(start);
boolean done = false;
int original = start;
start += 1;
while(!done) {
// Iterate until "start" points to a value that is bigger than the pivot
while (arrayList.get(start).compareTo( pivot) < 0 && start < end) {
start += 1;
}
// Iterate until "end" points to a value that is smaller than the pivot
while (arrayList.get(end).compareTo(pivot) >= 0 && start < end) {
end -= 1;
}
// Swap them
if (start < end) {
Collections.swap(arrayList, start, end);
start+=1;
} else {
done = true;
}

}

// The Loop will always end with start=end. We must check if that position is smaller or bigger than the pivot
if (arrayList.get(start).compareTo( pivot) > 0) {
start -= 1;
}
// Put pivot in the middle
Collections.swap(arrayList, original, start);
return start;
}

private int partition(T[] arrayList, int start, int end) {
T pivot = arrayList[start];
boolean done = false;
int original = start;
start += 1;
while(!done) {
// Iterate until "start" points to a value that is bigger than the pivot
while (arrayList[start].compareTo( pivot) < 0 && start < end) {
start += 1;
}
// Iterate until "end" points to a value that is smaller than the pivot
while (arrayList[end].compareTo(pivot) >= 0 && start < end) {
end -= 1;
}
// Swap them
if (start < end) {
T temp = arrayList[start];
arrayList[start] = arrayList[end];
arrayList[end] = temp;
start+=1;
} else {
done = true;
}

}

// The Loop will always end with start=end. We must check if that position is smaller or bigger than the pivot
if (arrayList[start].compareTo( pivot) > 0) {
start -= 1;
}
// Put pivot in the middle
arrayList[original] = arrayList[start];
arrayList[start] = pivot;
return start;

}

public void sort(ArrayList<T> arrayList) {
sort(arrayList, 0, arrayList.size()-1);
}

public void sort(ArrayList<T> arrayList, int start, int end) {
if (start < end) {
int split = partition(arrayList, start, end);
sort(arrayList, start, split-1);
sort(arrayList, split+1, end);
}
}

public void sort(T[] array) {
sort(array, 0, array.length-1);
}

public void sort(T[] arrayList, int start, int end) {
if (start < end) {
int split = partition(arrayList, start, end);
sort(arrayList, start, split-1);
sort(arrayList, split+1, end);
}
}
}``````
##### (h) Random Sort
``````import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class RandomSort {

public static final int listCount = 5;

public static void main(String[] args) {
//creates Arraylist with n random Elements from 0 to 100
System.out.print("unsorted list: ");
List<Integer> intList = new ArrayList<Integer>(0);
for (int i = 0; i < listCount; i++) {
System.out.print(intList.get(i) + " ");
}
System.out.println();

sort(intList);
System.out.print("\nsorted List: ");
for (int i = 0; i < intList.size(); i++) {
System.out.print(intList.get(i) + " ");
}
System.out.println();
}

private static List<Integer> sort(List<Integer> list) {
List<Integer> temp = list;
int count = 1;

while (!checkSorted(temp)) {
System.out.print(count + " - ");
count++;
Collections.shuffle(temp);
for (int i = 0; i < list.size(); i++) {
System.out.print(temp.get(i) + " ");
}
System.out.println();
}
return temp;
}

private static boolean checkSorted(List<Integer> list) {
boolean sorted = true;
for (int i = 1; i < list.size(); i++) {
if (list.get(i - 1).compareTo(list.get(i)) > 0) sorted = false;
}
return sorted;
}
}``````
##### (i) Bubble Sort

First Let's have this helper class

``````import java.util.ArrayList;

public abstract class SortAlgorithm<T extends Comparable<T>> {
abstract public void sort(ArrayList<T> arrayList);

abstract public void sort(T[] array);

// ------------

protected final void swap(T[] array, int i, int j) {
T tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}

protected final void swap(ArrayList<T> array, int i, int j) {
T tmp = array.get(i);
array.set(i, array.get(j));
array.set(j, tmp);
}
}``````

then:

``````import java.util.List;

public class BubbleSort<T extends Comparable<T>> extends SortAlgorithm<T> {

@Override
public void sort(List<T> arrayList) {
boolean f;
for (int i = 0; i < arrayList.size(); i++) {
f = false;
for (int j = 0; j < arrayList.size() - i - 1; j++) {
if (arrayList.get(j).compareTo(arrayList.get(j + 1)) > 0) {
swap(arrayList, j, j + 1);
f = true;
}
if (!f)
break;
}
}
}

@Override
public void sort(T[] array) {
final int length = array.length;
boolean f = false;
for (int i = 0; i < length; i++) {
f = false;
for (int j = 0; j < length - i - 1; j++) {
if (array[j].compareTo(array[j + 1]) > 0) {
swap(array, j, j + 1);
f = true;
}
if (!f)
break;
}
}
}
}``````

#### How do You Feel after reading this?

According to scientists, we humans have 8 primary innate emotions: joy, acceptance, fear, surprise, sadness, disgust, anger, and anticipation. Feel free to tell us how you feel about this article using these emotes or via the comment section. This feedback helps us gauge our progress.

#### Help me Grow.

I set myself some growth ambitions I desire to achieve by this year's end regarding this website and my youtube channel. Am halfway. Help me reach them by: