Sorting Algorithms
Bubble Sort:
Works by repeatedly swapping the adjacent elements if they are in the wrong order.
Not suitable for large data sets.
In this algorithm,
traverse from left and compare adjacent elements and the higher one is placed at right side.
In this way, the largest element is moved to the rightmost end at first.
This process is then continued to find the second largest and place it and so on until the data is sorted.
Worst-case Time Complexity: In the worst-case scenario, where the input array is in reverse order, bubble sort makes the maximum number of comparisons and swaps. The time complexity is O(n^2), where 'n' is the number of elements in the array. This is because for 'n' elements, there can be at most (n-1) passes, and in each pass, we have to compare and potentially swap every element.
(N-1) + (N-2) + (N-3) + . . . 2 + 1
= (N-1)*(N-1+1)/2 { by using sum of N natural Number formula }
= (N * (N-1)) / 2d a stable sorting algorithm, which means that it preserves the relative order of elements with equal key values in the sorted output.
Best-case Time Complexity: In the best-case scenario, where the input array is already sorted, bubble sort still needs to make passes to check that no swaps are needed, but it doesn't actually perform any swaps. The time complexity is still O(n^2) in the best case because, in each pass, we have to make (n-1) comparisons. 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.
Average-case Time Complexity: In the average case, bubble sort performs approximately (n^2)/2 comparisons and swaps. This is because on average, we can expect that about half of the elements are already in their correct positions, reducing the number of necessary swaps. Therefore, the average time complexity is also O(n^2).
often used to introduce the concept of a sorting algorithm. In computer graphics, it is popular for its capability to detect a tiny error (like a swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n).
Example: often used to introduce the concept of a sorting algorithm. In computer graphics, it is popular for its capability to detect a tiny error (like a swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n). eg: It is used in a polygon filling algorithm
Bubble sort using recursion:
a stable sorting algorithm, which means that it preserves the relative order of elements with equal key values in the sorted output.
Selection Sort:
The algorithm repeatedly selects the smallest (or largest) element from the unsorted portion of the list and swaps it with the first element of the unsorted part. This process is repeated for the remaining unsorted portion until the entire list is sorted.
Works well with small datasets.
not work well on large datasets.
not stable.
Selection sort can be made Stable if instead of swapping, the minimum element is placed in its position without swapping i.e. by placing the number in its position by pushing every element one step forward(shift all elements to left by 1). like insertion sort.
in-place algo (no extra space req)
for i in range(n - 1): min_index = i for j in range(i + 1, n): if arr[j] < arr[min_index]: min_index = j if min_index != i: arr[i], arr[min_index] = arr[min_index], arr[i]
Worst-Case Time Complexity (O(n^2)): The worst-case scenario occurs when the input array is in reverse order. In this case, selection sort makes the maximum number of comparisons and swaps. For an array of 'n' elements, it performs roughly n * (n - 1) / 2 comparisons and n swaps. Therefore, the worst-case time complexity is O(n^2), where 'n' is the number of elements in the array.
One loop to select an element of Array one by one = O(N)
Another loop to compare that element with every other Array element = O(N)
Therefore overall complexity = O(N) * O(N) = O(N*N) = O(N2)
Best-Case Time Complexity (O(n^2)): The best-case scenario occurs when the input array is already sorted. Even in the best-case scenario, selection sort needs to make the same number of comparisons as in the worst case (n * (n - 1) / 2 comparisons). While it doesn't perform swaps when elements are already in the correct order, the time complexity remains O(n^2).
Average-Case Time Complexity (O(n^2)): In the average case, selection sort also performs roughly n * (n - 1) / 2 comparisons and n swaps. This is because the number of comparisons and swaps doesn't change significantly from the worst case. Therefore, the average-case time complexity is O(n^2).
Insertion Sort:
Insertion sort is a simple and efficient sorting algorithm used to sort a list or array of elements. It works by dividing the input array into a sorted and an unsorted region. Initially, the sorted region contains only the first element of the array, and the unsorted region contains the rest of the elements. The algorithm iterates through the unsorted region, one element at a time, and places each element in its correct position within the sorted region.
Here's a step-by-step explanation of how the insertion sort algorithm works:
Start with the second element in the array (or list) since a single element can be considered a sorted region of size 1.
Compare the second element with the first element (the one in the sorted region). If the second element is smaller, swap them so that the smaller element is in the first position of the sorted region.
Move to the third element and compare it with the elements in the sorted region from right to left, moving elements to the right as long as they are greater than the current element.
Continue this process, comparing each unsorted element with the elements in the sorted region and inserting it in its correct position.
Repeat steps 2-4 until all elements are sorted. At each step, the sorted region grows, and the unsorted region shrinks until all elements are in their correct positions.
Insertion sort is an "in-place" sorting algorithm, which means it doesn't require additional memory for sorting. It has a time complexity of O(n^2) in the worst and average cases, where 'n' is the number of elements in the array. In the best case, when the input is already sorted, the time complexity is O(n).
During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array.
Despite its simplicity and relatively high time complexity, insertion sort can be quite efficient for small lists or nearly sorted data.
QUICK SORT:
The key process in quickSort is a partition(). The target of partitions is to place the pivot (any element can be chosen to be a pivot) at its correct position in the sorted array and put all smaller elements to the left of the pivot, and all greater elements to the right of the pivot.
Partition is done recursively on each side of the pivot after the pivot is placed in its correct position and this finally sorts the array.
Partition Algorithm:
The logic is simple, we start from the leftmost element and keep track of the index of smaller (or equal) elements as i. While traversing, if we find a smaller element, we swap the current element with arr[i]. Otherwise, we ignore the current element.
- Best Case: Ω (N log (N))
The best-case scenario for quicksort occur when the pivot chosen at the each step divides the array into roughly equal halves.
In this case, the algorithm will make balanced partitions, leading to efficient Sorting. - Average Case: θ ( N log (N))
Quicksort’s average-case performance is usually very good in practice, making it one of the fastest sorting Algorithm. - Worst Case: O(N2)
The worst-case Scenario for Quicksort occur when the pivot at each step consistently results in highly unbalanced partitions. When the array is already sorted and the pivot is always chosen as the smallest or largest element. To mitigate the worst-case Scenario, various techniques are used such as choosing a good pivot (e.g., median of three) and using Randomized algorithm (Randomized Quicksort ) to shuffle the element before sorting. - Auxiliary Space: O(1), if we don’t consider the recursive stack space. If we consider the recursive stack space then, in the worst case quicksort could make O(N).
Advantages of Quick Sort:
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 of Quick Sort:
time complexity at worst case
less efficient on small datasets
stable
Merge Sort:
Merge sort is defined as a sorting algorithm that works by dividing an array into smaller subarrays, sorting each subarray, and then merging the sorted subarrays back together to form the final sorted array.
Merge sort is a recursive algorithm that continuously splits the array in half until it cannot be further divided i.e., the array has only one element left (an array with one element is always sorted). Then the sorted subarrays are merged into one sorted array.
advs:
stable
easily parallelized to take advantage of multiple processors or threads.
worst-case time complexity of O(N logN), which means it performs well even on large datasets.
Drawbacks of Merge Sort:
Space complexity: Merge sort requires additional memory to store the merged sub-arrays during the sorting process.
Not in-place: Merge sort is not an in-place sorting algorithm, which means it requires additional memory to store the sorted data. This can be a disadvantage in applications where memory usage is a concern.
Not always optimal for small datasets: For small datasets, Merge sort has a higher time complexity than some other sorting algorithms, such as insertion sort. This can result in slower performance for very small datasets.
Comments
Post a Comment