Sorting Algorithms
Sorting Algorithms
For more sorting algorithms & information : https://en.wikipedia.org/wiki/Sorting_algorithm
A sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other algorithms (such as search and merge algorithms) which require input data to be in sorted lists; it is also often useful for canonicalizing data and for producing human-readable output. More formally, the output must satisfy two conditions: The output is in nondecreasing order (each element is no smaller than the previous element according to the desired total order); The output is a permutation (reordering) of the input. Further, the data is often taken to be in an array, which allows random access, rather than a list, which only allows sequential access, though often algorithms can be applied with suitable modification to either type of data.
Selection Sort Algorithm
- Divides Input List into Two "Sub" Arrays, One Sortet Part and One Unsorted Part
- Simplest & Easiest Sorting Algorithm
- Fundamental Sorting Algorithm
Selection sort is the most fundamental, simple and most importantly an in-place sorting algorithm.
This algorithm divides the input list into two sub arrays.
- A sub array of sorted elements which is empty at the beginning and keep on increasing with each item added to it.
- An unsorted sub array of remaining elements . This is equal to the input size in the beginning and its size reduces to zero as we reach the end of algorithm.
The basic idea is that in each iteration of this algorithm we pick an element (either largest or smallest, this depends on the sorting scenario) and appends it to the sorted element list, reducing the size of unsorted list by one.
Let’s understand it with an example
Yellow – Sorted part of the list
Red – Key selected from the unsorted list, which is the smallest element of unsorted subarray in this case
Blue – This element in unsorted subarray, which is compared with the selected key (in red).
Double headed Arrow – Show the elements swappedSelection Sort Algorithm -Animation
So in the above picture we can see that in each iteration we choose the smallest element from the unsorted sub array and swaps it with the first element of unsorted sub array due to which sorted sub array keeps on increasing in size until complete array is sorted.
VISUALISATIONS
PSEUDOCODE
repeat (numOfElements - 1) times
set the first unsorted element as the minimum
for each of the unsorted elements
if element < currentMinimum
set element as new minimum
swap minimum with first unsorted position
Java Implementation
public static int[] selectionSort(int[] arr) {
// Done in ascending order.
for (int i = 0; i < arr.length - 1; i++) {
int index = i; // "index" is set to "i" as "i" is the first element of the unsorted part of the array.
for (int j = i + 1; j < arr.length; j++) {
/* For-loop to find the position of the lowest number, will loop through the whole array
and set the "index" variable as the index (position) of the lowest number in the array. */
if (arr[j] < arr[index]) {
index = j; // Setting index variable to the "index" position of the lowest number in the array
}
}
/* Setting "smallerNumber" variable to the smallest number in the unsorted array,
determined by the index (position) of the lowest number in the array.*/
int smallerNumber = arr[index];
/* Setting the "index" variable to "i", which is the last element/item of the sorted part of the array
The "index" variable is set to "i", as it the index of the last element/item of the sorted part of the array,
from which every other item in the unsorted part of the array (from i to the end of the array) is checked against
*/
arr[index] = arr[i];
/* Setting the number just determined as the smallest element/item of the unsorted array (see above) to the last
element of the sorted array */
arr[i] = smallerNumber;
}
return arr;
}
Bubble Sort Algorithm
- Simplest to Implement
- Inefficient
- Slow
VISUALISATIONS
PSEUDOCODE
do
swapped = false
for i = 1 to indexOfLastUnsortedElement
if leftElement > rightElement
swap(leftElement, rightElement)
swapped = true
while swapped
Java Implementation
public int[] bubbleSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j]; // Adding current item in array to temporary variable.
array[j] = array[j + 1]; // Swapping current item in array with next item
array[j + 1] = temp; // Setting next item equal to previous item (stored in temp variable).
}
}
}
return array;
}
Quick Sort Algorithm
- Large amounts of code needed
- More efficient than Bubble Sort
VISUALISATIONS
PSEUDOCODE
for each (unsorted) partition
set first element as pivot
storeIndex = pivotIndex + 1
for i = pivotIndex + 1 to rightmostIndex
if element[i] < element[pivot]
swap(i, storeIndex); storeIndex++
swap(pivot, storeIndex - 1)
Java Implementation
public class MyQuickSort {
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) {
/**
* In each iteration, we will identify a number from left side which
* is greater then the pivot value, and also we will identify a
* number from right side which is less then the pivot value. Once
* the search is done, then we exchange both numbers.
*/
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[]) {
MyQuickSort sorter = new MyQuickSort();
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(" ");
}
}
}