SORTING ALGORITHM
A Sorting Algorithm is used to rearrange a given array or list of elements according
to a comparison operator on the elements.
Sorts are most commonly in numerical or a form of alphabetical (called
lexicographical) order, and can be in ascending (A-Z, 0-9) or descending (Z-A, 9-0)
order
Most Common Sorting Algorithm
• Selection Sort -Heap Sort
• Bubble Sort -Counting Sort
• Insertion Sort -Radix Sort
• Merge Sort -Bucket Sort
• Quick Sort
SELECTION SORT:
Selection sort is a simple and efficient sorting algorithm that works by repeatedly
selecting the smallest (or largest) element from the unsorted portion of the list and
moving it to the sorted portion of the list.
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.
Complexity Analysis of Selection Sort:
o Time Complexity: The time complexity of Selection Sort is O(N2 ) as
there are two nested loops: 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 )
o Auxiliary Space: O(1) as the only extra memory used is for temporary
variables while swapping two values in Array. The selection sort never makes
more than O(N) swaps and can be useful when memory writing is costly.
ADVANTAGES:
o Simple and easy to understand
o Works well with small datasets
DISADVANTAGES:
o Does not work well on large datasets.
BUBBLE SORT ALGORITHM:
Bubble Sort is the simplest sorting algorithm that works by repeatedly
swapping the adjacent elements if they are in the wrong order. This algorithm
is not suitable for large data sets as its average and worst-case time
complexity is quite high.
Where is the Bubble sort algorithm used?
o Due to its simplicity, bubble sort is often used to introduce the concept of a
sorting algorithm.
o 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).
ADVANTAGES:
o Bubble sort is easy to understand and implement.
o It does not require any additional memory space.
o It’s adaptability to different types of data.
DISADVANTAGES:
o Bubble sort has a time complexity of O(n^2) which makes it very slow for
large data sets.
o It is not efficient for large data sets, because it requires multiple passes
through the data.
INSERTION SORT:
Insertion sort is a simple sorting algorithm that works similar to the way you
sort playing cards in your hands.
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.
Characteristics of Insertion Sort:
o This algorithm is one of the simplest algorithm with simple implementation
o Basically, Insertion sort is efficient for small data values
o Insertion sort is adaptive in nature, i.e. it is appropriate for data sets which
are already partially sorted.
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.
IMPORTANCE OF MERGE SORT:
o One of the main advantages of merge sort is that it has a time
complexity of O(n log n), which means it can sort large arrays relatively
quickly
o Merge sort is a popular choice for sorting large datasets because it is
relatively efficient and easy to implement. It is often used in conjunction
with other algorithms, such as quicksort, to improve the overall
performance of a sorting routine..
APPLICATION OF MERGE SORT:
SORTING LARGE DATA SETS:
Merge sort is particularly well-suited for sorting large datasets due to its
guaranteed worst-case time complexity of O(n log n). This makes it a popular
choice for sorting algorithms used in databases and other data-intensive
applications.
EXTERNAL SORTING:
Merge sort is commonly used in external sorting, where the data to be
sorted is too large to fit into memory. Merge sort can be adapted to work with
external storage devices like hard drives or tape drives, making it useful for
applications like sorting large files or processing data streams.
PARALLEL PROCESSING:
Merge sort is a naturally parallelizable algorithm, which means it can be
easily adapted to work with multiple processors or threads. This makes it useful
for applications that require high-performance computing, such as scientific
simulations or financial modeling.
STABLE SORTING:
Merge sort is a stable sorting algorithm, which means it maintains the
relative order of equal elements in the input array. This makes it useful in
applications where preserving the original order of equal elements is important,
such as in databases or financial systems.
CUSTOM SORTING:
Merge sort can be adapted to handle different input distributions, such
as partially sorted, nearly sorted, or completely unsorted data. This makes it
useful in a variety of real-world applications, where data can have complex and
varied distributions.
INVERSION COUNT PROBLEM:
