What is Sorting?
Sorting in general means to arrange things in proper order. Sorting is the fundamental operation in computer science. Sorting refers to the operation of arranging data in some given order like increasing or decreasing. The output will be given by reordering the input.
Various sorting algorithms can be used for sorting. And, we can use any algorithm based on our requirements and properties data which will be sorted.
Selection of best algorithm for a specific problem depends upon problem definition. Comparisons of sorting algorithms are dependent on different scenario. Before discussing some sorting algorithms we will discuss some terms related to sorting-
Time Complexity & Space Complexity in Sorting
An analysis of the time required to solve a problem of a particular size involves the time complexity of the algorithm. An analysis of the computer memory required involves the space complexity of the algorithm.
There are different types of Time Complexities like-
1. Constant time – O (1) when it is not dependent on the input size n. Irrespective of the input size n, the runtime will always be the same.
2. Linear time – O (n)when the running time increases linearly with the length of the input.
3. Logarithmic time – O (log n)when it reduces the size of the input data in each step. This indicates that the number of operations is not the same as the input size. found in binary trees or binary search functions.
4. Quadratic time – O (n^2)An algorithm is said to have a non – linear time complexity where the running time increases non-linearly (n^2) with the length of the input.
We can also see other time complexities like...5. Cubic time – O (n^3) but the earlier ones are most discussed.
Space Complexity
Space complexity deals with finding out how much (extra)space would be required by the algorithm with change in the input size. For e.g. it considers criteria of a data structure used in an algorithm as Array or Linked List.
Let’s Discuss about some common sorting algorithms
1. Bubble Sort
Bubble sort is a simple and the slowest sorting algorithm which works by comparing each element in the list with its neighboring elements and swapping them if they are in undesirable order. It has a worst-case and average-case complexity of O(n^2 ), where n is the number of elements to be sorted.
Bubble sort is mostly used in computer graphics when it comes to detecting a very small error (like swap of just two elements) in almost sorted arrays. It works okay with larger datasets where the items are almost sorted because it takes only one iteration to detect whether the list is sorted or not.
2. Quick Sort
Quicksort is the fastest general purpose internal sorting algorithm on the average time complexity of O(n log n). it does not require any additional memory space for sorting an array. It is widely used in most real time applications with large data sets. Quick sort uses divide and conquer approach for solving problems. selecting the leftmost or rightmost element as a pivot causes the worst case running time of O(n^2).
It is quite complicated to quick sort an array of smaller size. Quick sort might be space expensive for large data sets because it uses O(log n) auxiliary space for recursive function calls.
3. Heap Sort
Heap Sort is based on heap data structure and in-place sorting algorithm. Unlike merge & quick sort, heap does not work recursively. Heap sort works by building a heap from the input array and then removing the maximum element from the heap and placing it at the end of the final sorted array. The worst case, average case running time complexity of heap sort is O(n log n). Heap sort need only a constant amount of additional memory space for arrays at all.
Optimized performance, efficiency, and accuracy are a few of the best qualities of this algorithm. HeapSort is not used much in practice but can be useful in real-time (or time-bound where QuickSort doesn’t fit) embedded systems where less space is available (MergeSort doesn’t fit).
4. Merge Sort
Merge sort uses divide and conquer approach for solving a given problem. It works by splitting the unsorted array into n sub-array recursively until each sub-array has 1 element. an array with one element is considered to be sorted. Consequently, it merges each sub-array to generate a final sorted array. The worst-case and average-case running time complexity of merge sort is O(n log n).
It is not recommended for smaller arrays for the reason that it works recursively and it requires O(n) auxiliary space for sorting. Databases use external merge sort to sort sets of data that are too large to be loaded entirely into memory.
5. Selection Sort
Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end.
Initially, the sorted part is empty and the unsorted part is the entire list. The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. it has O(n^2) time complexity.
The main advantage of the selection sort is that it performs well on a small list. Since it is an in-place sorting algorithm, no additional temporary storage is required.
6. Insertion Sort
In Insertion sort, 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. It has an average time complexity of O(n^2) and space complexity of O(1). Insertion sort is quite similar to swapping cards while playing.
Image Source
Conclusion:
When a new sorting algorithm is created, its credibility is based on how quickly it sorts the data. Their performance is determined by the type of data provided as input and the algorithm's implementation.
All sorting algorithms are problem-specific means they work well on some specific problem and don't work well for all the problems.
Some sorting algorithms apply to fewer elements, some sorting algorithms suitable for floating-point numbers, some are fit specific ranges, some sorting algorithms are used for a large number of data, some are used if the list has repeated values. We sort data either in numerical order or lexicographical, sorting numerical value either in increasing order or decreasing order and alphabetical value like addressee key.
Every sorting algorithm has its advantages and disadvantages, we can not term it as any particular sorting algorithm is best or worst. So we will say that every coder should understand the sorting algorithms and use them according to the need of the problem.
THANK YOU!...
Authors:
Pratik Patil
Omkar Patil
Tanishk Patil
Tanmay Pol
