Sorting is the operation performed to arrange the records of a table or list in some order according to some specific ordering criterion. Sorting is performed according to some key value of each record.
The records are either sorted either numerically or alphanumerically. The records are then arranged in ascending or descending order depending on the numerical value of the key. Here is an example, where the sorting of a list of marks obtained by a student in any subject of a class.
Sorting Algorithm Complexity
The efficiency of a sorting algorithm is determined by the time complexity and spatial complexity of the algorithm.
Time complexity:
Time complexity refers to the time it takes an algorithm to complete execution given the size of the inputs. It can be presented in various formats.
· Big O Notation (O)
· Omega notation (Ω)
· Theta notation (Θ)
Space complexity:
Space complexity refers to the total amount of memory an algorithm uses to complete its execution. Includes both auxiliary memory and input.
Auxiliary storage is extra space that the algorithm occupies next to the input data. Auxiliary memory is usually considered when calculating the space complexity of an algorithm.
Let's see a complexity analysis of different sorting algorithms.
Stability of the Sorting Algorithm
A sorting algorithm is considered stable if two or more items with the same value maintain the same relative positions even after sorting.
For example, there are two items with the same value 3. An unstable sorting algorithm allows two possibilities where the two positions of 3 may or may not be maintained.
However, after a stable sorting algorithm, there is always one possibility where the positions are maintained as in the original array.
Types of sorting algorithms
There are various sorting algorithms that can be used to complete this operation. And, we can use any algorithm based on the requirement such as, Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quicksort, Counting Sort, Radix Sort, Heap Sort and more.
Let’s discuss some of the basics sorting techniques in programming.
Bubble Sort
Bubble sort is the simplest sorting algorithm that works by repeatedly swapping adjacent items if they are out of order. This algorithm is not suitable for large data sets due to its very high average and worst-case time complexity.
Algorithm for Bubble Sort:
bubble_sort(A):
n = length(A)
for i from 0 to n-1:
for j from 0 to n-2:
if A[j] > A[j+1]:
swap A[j] and A[j+1]
return A
What is the Boundary Case for Bubble sort?
Bubble sort takes minimum time (Order of n) when elements are already sorted. Hence it is best to check if the array is already sorted or not beforehand, to avoid O(N2) time complexity.
Does sorting happen in place in Bubble sort?
Yes, Bubble sort performs the swapping of adjacent pairs without the use of any major data structure. Hence Bubble sort algorithm is an in-place algorithm.
Is the Bubble sort algorithm stable?
Yes, the bubble sort algorithm is stable.
Complexities
Time Complexities
Worst Case Complexity: O(n2) - If we want to sort in ascending order and the array is in descending order then the worst case occurs.
Best Case Complexity: O(n) - If the array is already sorted, then there is no need for sorting.
Average Case Complexity: O(n2) - It occurs when the elements of the array are in jumbled order (neither ascending nor descending).
Space Complexity
Space complexity is O(1) because an extra variable is used for swapping.
In the optimized bubble sort algorithm, two extra variables are used. Hence, the space complexity will be O(2).
Advantages:
· Bubble sort is easy to understand and implement.
· It does not require any additional memory space.
· It’s adaptability to different types of data.
· It is a stable sorting algorithm, meaning that elements with the same key value maintain their relative order in the sorted output.
Disadvantages
· Bubble sort has a time complexity of O(n^2) which makes it very slow for large data sets.
· It is not efficient for large data sets, because it requires multiple passes through the data.
Applications
Bubble sort is used if, complexity does not matter and short and simple code is preferred.
Selection Sort
Selection sort is a sorting algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list.
Algorithm for Selection Sort:
selection_sort(A):
n = length(A)
for i from 0 to n-1:
min_index = i
for j from i+1 to n-1:
if A[j] < A[min_index]:
min_index = j
swap A[i] and A[min_index]
return A
Is Selection Sort Algorithm stable?
Stability: The default implementation is not stable. However, it can be made stable. Please see the stable selection sort for details.
Is Selection Sort Algorithm in place?
Yes, it does not require extra space.
Complexities
Time Complexities
Worst Case Complexity: O(n2) - If we want to sort in ascending order and the array is in descending order then, the worst case occurs.
Best Case Complexity: O(n2) - It occurs when the array is already sorted
Average Case Complexity: O(n2) - It occurs when the elements of the array are in jumbled order (neither ascending nor descending).
Space Complexity:
Space complexity is O(1) because an extra variable temp is used.
Applications
The selection sort is used when
· A small list is to be sorted
· Cost of swapping does not matter
· Checking of all the elements is compulsory
· Cost of writing to memory matters like in flash memory (number of writes/swaps is O(n) as compared to O(n2) of bubble sort)
Merge Sort
What is Merge Sort? Merge sort is like the quick sort algorithm because it uses a divide-and-conquer method to sort items. This is one of the most popular and efficient sorting algorithms. Splits the given list into two equal halves, calls the two halves, then joins the two sorted halves. To do a merge, we need to define a merge() function.
The sub-list is halved repeatedly until the list cannot be split any further. Then combine the pairs of one-item lists into two-item lists and sort them. Sorted pairs of two items are merged with lists of four items until we get a sorted list.
Algorithms
merge_sort(A):
n = length(A)
if n == 1:
return A
mid = n/2
left = merge_sort(A[0:mid])
right = merge_sort(A[mid:n])
return merge(left, right)
merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i = i+1
else:
result.append(right[j])
j = j+1
result += left[i:]
result += right[j:]
return result
How can merge sort be made more efficient?
Since the number of operations required to sort an array of maximum size is 43, for small array sizes where the size of the remaining array is 43 or less, merge sort can be made more efficient by replacing the recursive calls with insertion sort. can be efficient. Insertion sort compared to the number of operations required for merge sort.
Complexities
Time Complexity
Best Case Complexity: O(n*log n)
Worst Case Complexity: O(n*log n)
Average Case Complexity: O(n*log n)
Space Complexity
The space complexity of the merge sort is O(n).
Advantage
· Stability
· Guaranteed worst–case problem
· Parallelizable
· Memory efficient
· Versatility
· Adaptability
Disadvantage
· Space Complexity
· Recursive algorithms
· Not in-place
· Not always optimal for small datasets
Applications
· Inversion count problem
· External sorting
· E-commerce applications
· Sorting large datasets
· External sorting
· Parallel processing
Quick Sort
Quicksort is a sorting algorithm based on the divide and conquer approach where an array is divided into subarrays by selecting a pivot element (element selected from the array).
While dividing the array, the pivot element should be positioned in such a way that elements less than the pivot are kept on the left side and elements greater than the pivot are on the right side of the pivot.
The left and right subarrays are also divided using the same approach. This process continues until each subarray contains a single element.
At this point, elements are already sorted. Finally, elements are combined to form a sorted array.
Choosing the pivot
Picking a good pivot is necessary for the fast implementation of quicksort. However, it is typical to determine a good pivot. Some of the ways of choosing a pivot are as follows -
Pivot can be random, i.e. select the random pivot from the given array.
Pivot can either be the rightmost element or the leftmost element of the given array.
Select median as the pivot element.
Algorithms
quick_sort(A):
n = length(A)
if n <= 1:
return A
pivot = A[n/2]
left = [x for x in A if x < pivot]
middle = [x for x in A if x == pivot]
right = [x for x in A if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
How to pick any element as a pivot?
With one minor change to the above code, we can pick any element as a pivot. For example, to make the first element a pivot, we can simply swap the first and last elements and then use the same code. The same thing can be done to pick any random element as a pivot.
What is 3-Way Quicksort?
In the simple Quicksort algorithm, we select an element as a pivot, partition the array around the pivot and recur for subarrays on the left and right of the pivot.
Consider an array that has many redundant elements. For example, {1, 4, 2, 4, 2, 4, 1, 2, 4, 1, 2, 2, 2, 2, 4, 1, 4, 4, 4}. If 4 is picked as the pivot in Simple Quicksort, we fix only one 4 and recursively process the remaining occurrences. In 3 Way Quicksort, an array arr[l..r] is divided in 3 parts:
arr[l..i] elements less than pivot.
arr[i+1..j-1] elements equal to pivot.
arr[j..r] elements greater than pivot.
Advantages
· It is a divide-and-conquer algorithm that makes it easier to solve problems.
· It is efficient on large data sets.
· It has a low overhead, as it only requires a small amount of memory to function.
Disadvantages
· It has a worst-case time complexity of O(n^2), which occurs when the pivot is chosen poorly.
· It is not a good choice for small data sets.
· It can be sensitive to the choice of the pivot.
· It is not cache-efficient.
· It is not a stable sort, meaning that if two elements have the same key, their relative order will not be preserved in the sorted output in case of quick sort, because here we swap elements according to the pivot’s position (without considering their original positions).
Complexities
Time Complexities
Worst Case Complexity [Big-O]: O(n2)
It occurs when the pivot element picked is either the greatest or the smallest element.
This condition leads to the case in which the pivot element lies at the extreme end of the sorted array. One sub-array is always empty and another sub-array contains n - 1 elements. Thus, quicksort is called only on this sub-array.
However, the quicksort algorithm has better performance for scattered pivots.
Best Case Complexity [Big-omega]: O(n*log n)
It occurs when the pivot element is always the middle element or near the middle element.
Average Case Complexity [Big-theta]: O(n*log n)
It occurs when the above conditions do not occur.
Space Complexity
The space complexity for quicksort is O(log n).
Applications
The Quicksort algorithm is used when the programming language is good for recursion
time complexity matters, space complexity matters, etc.
Insertion Sort
Insertion Sort is a simple sorting algorithm that works like sorting a hand of playing cards. The array is split virtually into sorted and unsorted parts. The values from the unsorted part are taken and placed in the correct position in the sorted part.
Algorithms
insertion_sort(A):
n = length(A)
for i from 1 to n-1:
key = A[i]
j = i-1
while j >= 0 and A[j] > key:
A[j+1] = A[j]
j = j-1
A[j+1] = key
return A
Features of insertion sort:
This algorithm is one of the simplest and easiest to implement.
Basically, insertion sort is efficient for small data values
Insertion sort is adaptive in nature i.e., Suitable for records that are already partially sorted.
Complexities
Time Complexities
Worst Case Complexity: O(n2) - Suppose, an array is in ascending order, and you want to sort it in descending order. In this case, worst-case complexity occurs.
Each element must be compared with each of the other elements so, for every nth element, (n-1) number of comparisons are made.
Thus, the total number of comparisons = n*(n-1) ~ n2
Best Case Complexity: O(n) - When the array is already sorted, the outer loop runs for n number of times whereas the inner loop does not run at all. So, there is only 'n' number of comparisons. Thus, complexity is linear.
Average Case Complexity: O(n2) - It occurs when the elements of an array are in jumbled order (neither ascending nor descending).
Space Complexity
Space complexity is O(1) - because an extra variable key is used.
Applications
The insertion sort is used when the array is having a small number of elements, there are only a few elements left to be sorted, etc.
Conclusion
In summary, sorting algorithms are essential tools in computer science that can efficiently organize data collections. The choice of which algorithm to use depends on various factors such as the size of the dataset, the required time complexity, and available resources. Bubble sort, selection sort, and insertion sort are simple algorithms, but their worst-case time complexity is O(n^2), making them inefficient on large datasets. Merge sort and quicksort are more efficient algorithms with the worst-case time complexity of O(n log n), so they are best suited for large datasets. Heap reordering is also an efficient algorithm, but requires additional memory for the heap binary data structures. Therefore, it is important to choose the most appropriate algorithm based on the specific needs of the problem at hand.