SORTING
1. Bubble Sort:
S.
Selection Sort Bubble Sort
No.
Selection sorting is a sorting
Bubble sorting is a sorting algorithm
algorithm where we select the
1. where we check two elements and
minimum element from the array and
swap them at their correct positions.
put that at its correct position.
Its Time complexity in the Best case Its Time complexity in the Best case
2.
is O(N^2) is O(N)
Selection sort performs minimum Bubble sort performs maximum
3.
number of swaps to sort the array number of swaps to sort the array
Its Time complexity in the worst case Its Time complexity in Worst case is
4.
is O(N^2) O(N^2)
This sorting algorithm uses the This sorting algorithm uses
5.
selection method exchanging method
It is not an efficient sorting
6. It is an efficient sorting technique.
technique.
7. Is is not a stable algorithm It is a stable algorithm
8. This method is faster. This method is slower.
Quick Sort:-
i) As name suggest quick sort is fastest internal sorting algorithm .This sort is
also known as Partition Exchange Sort
ii)Quick Sort is a Sorting algorithm which is unstable sort.
iii)In Quick sort we split the array into two sub-array and the splitting is based
on the Pivot element.
iv) All elements that are less than the pivot element should be in left sub-array
and all the elements that are greater than pivot elements should be in right sub-
array.
v)Recursively sort two sub-array and then combine all sorted elements in a
group to form a list of sorted elements.
Eg.20,10,5,4,1,45,36,30
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.
It is Cache Friendly as we work on the same array to sort and do not copy
data to any auxiliary array.
Fastest general purpose algorithm for large data when stability is not
required.
Disadvantages of Quick Sort
It has a worst-case time complexity of O(n2), which occurs when the
pivot is chosen poorly.
It is not a good choice for small data sets.
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 are swapping elements according to the
pivot's position (without considering their original positions).
Merge Sort:-
i)Merge Sort is a sorting algorithm which works on Divide And Conquer
approch.
ii)It works b y recurceively dividing the input array into a smaller sub-array and
sorting those sub-array then merging back together to obtain sorted array .
Algorithm:-
Step1:- Start
Step2:-Take a Input of N elements of unsorted data list.
Step3:-The Given List of element is divided arround its centre.
Step4:- Take a two sorted array a[] and b[] as a input and third array c[] as a
output with hree pointer i,j,k respectively.
Step5:- Smaller element a[] and b[] copy to array c[] and appropriate pointer
will be increment.
Step6:- When either of the element array a[] and b[] exhausted the remainder of
other array copy to array c[].
Step7:- Display Sorted list of element as an output .
Step8:- Stop.
E.g -55,85,45,11,34,05,89,99
Advantages
Stability : Merge sort is a stable sorting algorithm, which means it maintains
the relative order of equal elements in the input array.
Simple to implement: The divide-and-conquer approach is
straightforward.
Naturally Parallel : We independently merge subarrays that makes it
suitable for parallel processing.
Disadvantages
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.
Merge Sort is Slower than QuickSort in general as QuickSort is more
cache friendly because it works in-place.