Sorting is a technique for arranging a set of data in some order like ascending or descending. we have different types of methods to apply to sort in ascending or descending order. and these methods are divided into two categories.
Internal Sorting
If we have enough memory so that the data that we want to sort can be accommodated in the memory then internal sorting methods are used.
External Sorting
If we do not have enough memory so that the sorting data cannot be accommodated in the memory then external sorting methods are used. so to sort some of the data is kept in auxiliary memory like on the hard disk and then the external sorting method is used to sort the data.
Sorting techniques
- Selection sort
- Bubble sort
- Insertion sort
- Shell/Diminishing Increment sort
- Merge sort
- Radix/Bucket sort
- Quick/Partition exchange sort
- Heapsort
Selection sort
In the selection sort method, sorting is started from the first element and searches the entire list and finds the minimum value in the list, and then places it in the first position. again the search is start from second place and finds the minimum value and then places it in second place. this loop starts from the first element of the list and ends at the second last element of the list.
In terms of complexity, the selection sort has an O(N*N) best case, O(N*N) average case, and O(N*N) worst-case complexity.
Learn about
Bubble sort
In the bubble sorting technique the data file is passed sequentially several times. each pass consists of comparing each element in the file with its successor and interchanging the two elements if they are not in proper order.
In terms of complexity bubble sort has O(N) best case, O(N*N) average case, and O(N*N) worst-case complexity.
Learn about
Insertion sort
In the insertion sort technique, the sorts begin with a set of records by inserting records into an existing sorted file. in this technique, one temporary variable is required to hold the value during swapping the values. in the first pass 1 comparison is made, the second pass makes 2 comparisons and the last pass makes N-1 comparisons.
In terms of complexity, the Insertion sort has O(N) best case, O(N*N) average case, and O(N*N) worst-case complexity.
Learn about
Shell sort/Diminishing increment sort
Shell sort is also known as diminishing increment sort, as the name suggests sorting the separate subfiles of the original file. these sub-files contain every kth element of the original file.
In terms of complexity, Shell sort has O(N(log N))^2 best case, O(N(log N))^2 average case and O(N(log N))^2 worst-case complexity.
Learn about
Merge sort
As we know merging means combining two things to make one. so in the merge sorting divide and conquers method is used. first, the list of values is divided into the sub-lists so that each sub-list cannot be divided further. after that each sub-list is sorted and then again combined to make the full list. only we need is a temporary list of the same size as the list that we want to sort.
In terms of complexity, Merge sort has O(N log N) best case, O(N log N) average case and O(N log N) worst-case complexity.
Note – Merge sort is a type of external sorting.
Learn about
Radix sorting
Radix sort or bucket sort is used most where we want to sort the list of names in alphabetic order. in this technique, all the data are stored in a separate bucket and then each character is then arranged in the 26 classes, one for each letter of the alphabet. after that first class consists of names that begin with the A letter, second consists of those that start with the B letter and soon. this process is continued till the last length of the biggest number.
In terms of complexity, Radix sort has O(d *N) (where d is no. of digits) best case, O(d *N) (where d is no. of digits) average case, and O(d *N) (where d is no. of digits) worst-case complexity.
Learn about
Quicksort
The Quicksort technique is also used divide-and-conquer technique. in this technique, we first find the element that divides the array into two parts in such a way that the elements that are in the right subarray are greater than the dividing element, and the elements that are in the left subarray are less than the dividing element. then these two sub-arrays are sorted separately.
In terms of complexity, Quicksort has O(N log N ) best case, O(N log N ) average case and O(N*N) worst-case complexity.
Learn about
Heap sorting
In the heap sorting technique, we use a tree structure heap. heap is a type of binary tree. and then we construct a heap by adjusting the array elements and then repeatedly eliminate the root element of the heap by shifting it to the end of the array and then restoring the heap structure with the remaining elements.
In terms of complexity, Heap sort has O(N log N ) best case, O(N log N ) average case, and O(N log N ) worst-case complexity.
Learn about