The Sorting Algorithm!~Part 1
Sorting is any process which involves arranging of items(data) systematically holding two common yet distinct meanings to it :
ordering: arranging the items in a sequence ordered by some given criterion
categorizing: grouping the items which holds similar or alike properties.
The importance of sorting lies in the fact that the data searching can be optimized to an extreme high level.
Hello Comrades,
A very common thing that comes to a developers’ mind is why study sorting when languages like C, C++, Python, Java already has built-in sorting algorithms written ….. To bring it to your notice, Lets us understand how are these Sorting algorithms made : The Python and Java sorting functions are based on Tim-Sort [hybrid of merge sort and insertion sort], where as the C++ Sorting function is based on Intro-Sort [hybrid of quick sort , Insertion sort and heap sort]. C uses sorting function based on Quick-Sort.
To bring a clarity of how these sorting algorithms are implemented, today we will be understanding the use of sorting and most of the types of sorting algorithm that can help us solve a problem with efficiency. The main advantage of sorting is “time complexity”. What is a time complexity? It is the computational complexity that typically describes the amount of computer time it will take to run an algorithm.[ we can discuss this in detail in some upcoming posts]. Although there are no.of sorting algorithms, best algorithm is which which can solve a problem in minimum time and space complexity!
I will be releasing a series of articles on these mentioned sorting algorithms:
Some sorting algorithms are as mentioned :
- Bubble Sorting
- Insertion Sorting
- Selection Sorting
- Quick Sorting
- Heap Sorting
- Counting Sorting
- Bucket Sorting
- Radix Sorting
- Shell Sorting
- Comb Sorting
- Cycle Sorting
- Bitonic Sorting
- Tree Sorting
- Stooge Sorting
*Bubble Sorting
The bubble sorting, sometimes referred as sinking sorting is a comparison-based and the simplest sorting algorithm that repeatedly steps through a list of data, compares adjacent element and swaps them , if not in correct order.
Working : It sorts a given set of “n” elements provided in a form of an array with “n” no.of elements. Now assume if an array is to be sorted in an ascending order, so here the sorting algorithm will start by comparing the first element of the array to the second element, if the first element happens to be greater than the second element, it will swap the elements and further will move ahead to compare the second and third elements and so on, until the elements are sorted.Hence if we have “n” elements, we will be performing the sorting “n-1” times.
Code Snippet:
class BubbleSorting{static void bubbleSort(int arr[], int n). // parameters as input array and size of the array{int i, j, temp;boolean swapped; // using for optimization.. so that we don't swap the already swapped elements in the arrayfor (i = 0; i < n - 1; i++)// for the iteration of the complete array elements{swapped = false;for (j = 0; j < n - i - 1; j++)//for the adjacent element in the array{if (arr[j] > arr[j + 1]){temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = true;}}if (swapped == false)break;}}static void printArray(int arr[], int size){int i;for (i = 0; i < size; i++)System.out.print(arr[i] + " ");System.out.println();}public static void main(String args[]){int arr[] = { 5,1,4,2,8 };int n = arr.length;bubbleSort(arr, n);System.out.println("Sorted array: ");printArray(arr, n);}}O/P: Sorted array:1 2 4 5 8
When to use Bubble Sorting:
The idea of almost all languages providing us with the inbuilt sorting algorithms doesn’t let us take a decision on how we want to use sorting into our codes.The Bubble sort works well when it comes to handling any large datasets which are partially in sorted forms. Taking a day to day example of an organisation with employees of different departments and different roles when asked to be sorted, we already have a pre-sorted dataset based on departments or roles with us. So sorting of such datasets can be done using Bubble sorting.
*Insertion Sorting
This sorting is more or less like how any individual intuitively sorts things manually. It works similar to how we sort cards in our hands. Assuming that the first card is always sorted and then we move ahead with selecting an unsorted card and if the card holds a value greater than the card in our hand we place it on right otherwise to the left of the series of cards.
Working:
Insertion sorting places an unsorted element at its suitable place with every iteration it makes.To sort an array of size “n” in an ascending order, the algorithm will compare the current element (key element) to its predecessor. If the key element is smaller than the predecessor, it compares it to the elements before it. Moving the greater elements one position up to make space for the swapped elements. To explain it even better; the first element in the array is assumed to be sorted, so we take the second element and store it separately in key. Now we will compare this key with the first element. if the first element is greater than the key, the key gets placed in front of the first element. Now we have first two elements as sorted, taking the third element and comparing it with the elements on the left of it.Place it just behind the element smaller than it, and if there are no elements smaller than it, then place it at the beginning of the array.
Code Snippet:
class InsertionSorting{public void sort(int arr[]){int n = arr.length;for (int i = 1; i < n; ++i){int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key){arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}}static void printArray(int arr[]){int n = arr.length;for (int i = 0; i < n; ++i)System.out.print(arr[i] + " ");System.out.println();}public static void main(String args[]){int arr[] = { 12, 11, 13, 5, 6 };InsertionSorting is= new InsertionSorting();is.sort(arr);printArray(arr);}}O/P: 5 6 11 12 13
When to use Insertion Sorting:
Insertion sorting is generally the fastest solution for sorting smaller units of elements.Insertion sorting takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.
*Selection Sorting
This algorithm selects a smallest element from an unsorted list of elements in each iteration and places the element at the very beginning of the unsorted list.
Working:
Setting the first element as the minimum element, comparing the second element of the array with this minimum element . If the second element happens to be smaller than the minimum element, the algorithm will assign/ select the second element as the minimum element now. Hence forth, comparing the third element to the (new) minimum element now and again checking if the third element is smaller than the minimum element, if yes, algorithm again will assign the third element as minimum element, else do nothing and shall compare the fourth element to the minimum element. After each iteration that takes place in the algorithm, the minimum element will be placed at the very beginning of the array.
Code Snippet:
class SelectionSort{void sort(int arr[]){int n = arr.length;for (int i = 0; i < n-1; i++){int min_idx = i;for (int j = i+1; j < n; j++)if (arr[j] < arr[min_idx])min_idx = j;int temp = arr[min_idx];arr[min_idx] = arr[i];arr[i] = temp;}}void printArray(int arr[]){int n = arr.length;for (int i=0; i<n; ++i)System.out.print(arr[i]+" ");System.out.println();}public static void main(String args[]){SelectionSort ob = new SelectionSort();int arr[] = {64,25,12,22,11};ob.sort(arr);System.out.println("Sorted array");ob.printArray(arr);}}O/P: Sorted array:
11 12 22 25 64
When to use Selection Sorting:
Selection algorithm is good at checking if everything is already sorted. It is recommended to be used when we have memory space limitations to be taken care of.
Hope this article helps you in a little better understanding of the sorting algorithms and their use cases.
Until next time…
Peace Out!
