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.LinkedList;
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) {
                    sortedList.add(i, element);
                    continue originalList;
                }
            }
            sortedList.add(sortedList.size(), element);
        }

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

}
(c) RadixSort
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class RadixSort {

    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();
        radixSort(arr, arr.length - 1);
        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++)
            q.add(i, new LinkedList<>());

        for (int i = 0; i <= length; i++) {
            q.get((arr[i] / exp) % 10).add(arr[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));
        A.add(A.get(0).getMaxObject());
        B.add(B.get(0).getMaxObject());

        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++) {
            intList.add((int) (Math.random() * 100));
            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:




Recommendations


What do You Think

Dear readers drop us your comments below. We are building a community of students and learners. Start by dropping us your suggestions below. What tutorials do you want us to do for example? Where can we improve? What are some awesome resources out there? Do you have any code you want to share with us?
By the way that example or snippet you have lying in your computer can really help beginner programmers. We can share it here with other students.

Previous Post Next Post