Sorting Algorithm
INTRODUCTION
A Sorting Algorithm is a method of re arranging a large array into a specific systematic order, such as alphabetical, shortest-to-longest, ascending-to-descending value. It takes lists of items as input and perform some operations on those lists with set of rules to obtain the expected ordered arrays as output.
In this blog, we will be discussing about sorting algorithm and their working applications in detail.
We will also discuss the following topics:
· What is sorting algorithm?
· Why is sorting algorithm used?
· Working of sorting algorithm.
· Types of sorting algorithm.
· Time complexities of each sorting algorithm.
What is sorting algorithm?
Sorting of algorithm is the process of placing elements from a collection in some specific order. a list of words or array can be sorted alphabetically or by the length. On sorting he algorithm it gives a clear output.
Why is sorting algorithm used?
A Sorting algorithm will arrange the items in a list into a certain order, such as alphabetical or numerical order so that we can analyze it more efficiently. Sorting a list of items take a long time, especially in a large list. A computer program can be created to do this, making sorting a list of data make much easier.
Efficient sorting is important for optimising the efficiency of search and merge algorithms that require input data. Sorting helps for producing human-readable output.
Working of sorting algorithm.
Sorting algorithm will arrange the given array according to a comparison operator the comparison operator will decide the new order of elements in the respective data structure, like
ALGORITHM on sorting this word we get the output as AGHILMORT.
In this it is done through alphabetical order.
Types of sorting algorithm.
There are different types of sorting algorithms:
Ø Bubble sort
Ø Insertion sort
Ø Selection sort
Ø Quick sort
Ø Merge sort
Ø Heap sort
These are the main sorting algorithms we use for sorting. Every sorting algorithms have different time complexities and working nature.
# Bubble sort
Bubble sort is the simplest algorithm. Bubble sort works by repeatedly swapping the adjacent elements when they are in wrong order.
Bubble sort start with the first element (index=0), compare the current element with the next in array, if it is greater than the next element of the array will get swapped.in case if the current element is less than the next element then move to the next element.
The main advantage of the bubble sort is simplicity of the algorithm.
But highly inefficient for large data sets
The time complexity of bubble sort is O(n2) and its space complexity is O(1).
>> Insertion sort
Insertion sort is the mechanism where the sorted array is built having one item at a time. The array elements are compared with each other sequentially and arranged simultaneously in some specific order. The analogy can be understood from the style we arrange a deck of cards.
Insertion sort has fast best case running time, and best to use if the input is already mostly sorted
The time complexity of insertion sort is O(n2) but its best time complexity is O(n), and its space complexity is O(1).
>> Selection sort
Selection sort algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, like the sorted part at the left end and the unsorted part at the right end. This sorting algorithm sorts an array repeatedly finding the minimum element from part and place in the beginning.
Sorting algorithm is useful when memory space is limited. And it is good in checking if everything is already sorted.
The time complexity of selection sort is O(n2) irrespective of worst, average, best time complexity. Space complexity is O(1).
>> Quick sort
Quick sort is one of the highly efficient sorting algorithm and regarded as one of the best sorting algorithm. Because it sorts in one place, no additional storage is required.
Quick sort partitions array and calls itself recursively twice to sort the two resulting subarrays. Which is also known as divide-and-conquer algorithm.
It selects the ‘pivot’ element from an array and partitioning the other elements into two sub arrays, according to whether they are less than or greater than pivot.
Quick sort is most efficient in case of smaller array size or datasets and even works faster.
The time complexity of quick sort is:
Best time complexity is — n*log(n).
Average time complexity is — n*log(n)
Worst time complexity is — n².
>> Merge sort
Merge sort is a stable sort, extremely versatile.
The merge sort also uses divide and conquer approach.it repeatedly break down the list into several sub-lists until each sub-list consists of a single element and merge those sub-lists in a manner that results into a sorted array or list.
Steps followed by merge sort:
Step 1 (Divide):
Dividing the array of size n into two sub arrays of equal size (n/2 each) two halves.
Step 2 (Conquer):
Sort the divided sub arrays recursively by calling merge sort function.
Step 3 (Combine):
Merge the two sorted sub arrays to make the single sorted array.
v Recursive Call: Merge Sort (arr[], left, right)
v Compute the middle element to divide the array into two sub arrays. (mid = left + right/2)
v Sort recursively by calling Merge Sort (arr, left, mid), Merge Sort (arr, mid+1, right) for left and right sub arrays, respectively.
v Then Merge the Sorted arrays by calling merge function.
v Base case: if l==r returns -1, this is the case of single element
the recurrence relation for this merge Sort is, T(n) = 2T(n/2) + O(n).
merge sort more efficient and works faster than quick sort in case of larger array datasets.
But merge sort requires additional memory space of o(n).
The time complexity of merge sort:
Worst complexity: n*log(n)
Average complexity: n*log(n)
Best complexity: n*log(n)
Space complexity: n
The worst best average time complexity of merge sort is O (n log(n)) because the merge sort always divides the array into two halves and takes linear time to merge two halves.
>> Heap sort
The heap sort algorithm involves preparing the list by first turning it into a max heap. Then The algorithm repeatedly swaps the first value of the list with the last value, decreasing the range of values considered in the heap operation by one, and sifting the new first value into its position in the heap.
The time complexity of heap sort:
Heap sort also have the same time complexities as merge sort irrespective of worst, average, best that is n*log(n) but it’s time complexity is 1.
So, these are the main sorting algorithms we use for sorting algorithms. Each sorting algorithm has different working methods and time complexities.