Sorting Algorithms
In this blog we will look at the concept of sorting and 6 sorting Algorithms .
Let me share with you something about myself:
I am a CS Undergrad. I love😍 to learn and explore technology. I am interested in full stack web development and Machine learning. I am very much interested in data structure and algorithms.
Sorting is a process of arranging list of numbers in either ascending or descending order. Sorting can be divided into two categories.
i. Internal Sorting
ii. External Sorting
Internal sorting takes place in the main memory of the computer. Internal sorting can take advantage of random access nature of the main memory.
External sorting is carried on secondary storage. If the input data is such that it cannot be adjusted in the memory entirely at once, it needs to be stored in a hard disk, floppy disk, or any other storage device.
SORTING TECHNIQUES can be compared on basis of following factors:
· Number of Comparisons: Total number of comparison while performing sorting. Total time taken by sorting algorithm depends on comparisons. So number of comparison decides the complexity of any sorting technique.
· Number of swaps: To arrange numbers in proper order swapping of numbers is done. It is a common process done in almost all sorting algorithms.
· Adaptive: If all numbers are already sorted then it must take minimum time as it does not have to rearrange the elements.
· Stable: If after sorting , identical numbers appear in same sequence as in the original unsorted list.
· Memory requirement: The amount of memory required for performing the algorithm
Now let’s look at commonly used algorithms
1. Bubble Sort
2. Insertion Sort
3. Selection sort
4. Merge Sort
5. Quick Sort
6. Shell Sort
BUBBLE SORT :
Bubble sort is one of the simplest and the most popular sorting method. The basic idea behind bubble sort is as a bubble rises up in water. i.e. smallest element goes in beginning
The worst complexity is O(n²) where n is number of elements. This algorithm takes (n-1) passes where n is number of elements. It is also adaptive, when elements are already sorted then it takes minimum time i.e. O(n). It is also stable .
Now lets see the example 😀
INSERTION SORT
The insertion sort is based on the principle of inserting elements at its correct place in a previously sorted list . The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
The worst complexity is O(n²) where n is number of elements. This algorithm takes (n-1) passes where n is number of elements. It is also adaptive, when elements are already sorted then it takes minimum time i.e. O(n). It is also stable .
Now lets see the example 😀
SELECTION SORT
Selection sort is very simple sorting algorithm. The list is divided into two parts sorted and unsorted .Initially sorted part is empty and unsorted part contains entire list. Then minimum element is swapped with leftmost element. This process continues moving unsorted array boundary by one element to the right.
The worst complexity is O(n²) where n is number of elements. This algorithm takes (n-1) passes where n is number of elements. It is not adaptive because when elements are already sorted then it does not take minimum time i.e. O(n²). It is also not stable.
Now let’s the example 😀
MERGE SORT
Merge sort is the algorithm which follows divide and conquer approach. Consider an array A of n number of elements. The algorithm processes the elements in 3 steps.
1. If A Contains 0 or 1 elements then it is already sorted, otherwise, Divide A into two sub-array of equal number of elements.
2. Conquer means sort the two sub-arrays recursively using the merge sort.
3. Combine the sub-arrays to form a single final sorted array maintaining the ordering of the array.
The time complexity is O(n log n) where n is number of elements. It is stable.
Now let’s see the example 😀
QUICK SORT
Quick sort works on the principle of divide and conquer approach in which array is split into subarrays. Then the subarrays are recursively called to sort the elements.
There are 3 steps for sorting in Quick sort
1. Pivot element is selected .Any number from array is selected as pivot element.(Mostly leftmost or rightmost element.)
2. The elements smaller than the pivot element are added in the left part and elements greater than pivot element are added on the right part. Then pivot is at its final position.
3. Then all the steps are applied recursively to the left part and right part of the array.
This algorithm is also known as Selection Exchange Sort or Partition Exchange Sort. The time complexity is O(n log n) where n is number of elements. It is not adaptive because when elements are already sorted then it does not take minimum time but it take for O(n²) for unsorted list . It is also not stable.
Now lets look at example 😀
Shell Sort
Shell sort is an algorithm that first sorts the elements far apart from each other and successively reduces the interval between the elements to be sorted. It is a generalized version of insertion sort.
The time complexity is O(n log2n) where n is number of elements. It is adaptive but not stable.
Now let’s see the example 😀
So we looked on the brief idea of sorting ,types of sorting , factors of sorting algorithm and 6 commonly used sorting algorithms with examples. I hope you got the basic idea of sorting techniques. Every algorithm has its own advantages and disadvantages . Sorting algorithm should not be judged on the basis of time complexity. The algorithms are used on the basis of the need as under right circumstance each algorithm works in more efficient way.
Do share the post if you like👍
Feel free to reach me out😀
References
