Always messes with different sorting algorithms?? So, here I am again with my tutorial Blog.
So, without wasting much of time, have a sip of coffee and let's get started! :)
[NOTE :After reading the Blog, you may have a look at my github repository for better understanding :
https://github.com/PawandeepKaur2405/Sorting_Algorithms]
Basic Define:
Arranging elements in a particular order is called Sorting.
This blog will cover :
- Bubble Sort
- Insertion Sort
- Selection Sort
- Merge Sort
- Wave Sort
- Counting Sort
- DNF Sort / 0,1,2 Sort
- Quick Sort
Sorting Algorithms
1. Bubble Sort
It is the simplest sorting Algorithm.
In this, consecutive elements are compared using loop and if first element is greater than the next element(in case of Ascending order), it is swapped.
Example:
First Pass:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
Second Pass:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
TIME COMPLEXITY : O(n^2)
SPACE COMPLEXITY : O(1)
(So, completed Bubble sort? Pretty good huh?😜)
2. Insertion Sort
Key Point : In this sorting technique, insert an element from unsorted array to it's correct position in sorted array.
Example:
12, 11, 13, 5, 6
Let us loop for i = 1 (second element of the array) to 4 (last element of the array)
i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6
i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 6
i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6
i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position.
5, 6, 11, 12, 13
TIME COMPLEXITY : O(n^2)
SPACE COMPLEXITY : O(1)
Let's head to the third type...
3. Selection Sort
Key Point : Find minimum element in unsorted array and swap it with element at beginning.(pick and exchange sort)
Example:
arr[] = 64 25 12 22 11
Find the minimum element in arr[0...4] and place it at beginning
11 25 12 22 64
Find the minimum element in arr[1...4] and place it at beginning of arr[1...4]
11 12 25 22 64
Find the minimum element in arr[2...4] and place it at beginning of arr[2...4]
11 12 22 25 64
Find the minimum element in arr[3...4] and place it at beginning of arr[3...4]
11 12 22 25 64
TIME COMPLEXITY : O(n^2)
SPACE COMPLEXITY : O(1)
4. Merge Sort
It works on Divide and Conquer technique.
APPROACH:
1. Divide the array into two equal arrays until only 2 elements are present in the array.(This makes the problem small and hence reduces the sorting time)
2. Call your merge_sort function recursively for both halves.
3. Merge both halves using merge function.
TIME COMPLEXITY : O(nlogn)
SPACE COMPLEXITY : O(n) (Because we made extra temp arrays)
I know this one is little complex, but believe me guys, once you understand thoroughly, you are surely gonna love it!!😄
DRAWBACKS :
1. Not efficient for short arrays.
2. Runs through the entire array even if the array is sorted.
3. Merge sort algorithm uses an addition space of O(n) for temporary arrays.
5. Wave Sort
The elements are sorted in the form of a wave rather than ascending or descending order.
arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= .........
APPROACH:
1. Iterate through elements by step of 2.
2. Check if element is smaller than the previous and next element, then it's ok, just continue.
3. Otherwise, swap the elements.
TIME COMPLEXITY : O(n)
Ahh.. this was something unique right?💖
6. Counting Sort
This is not a comparison based sorting technique.
APPROACH:
1. First find count of each distinct element of array.
2. Calculate position of each element.
3. Form a new sorted array based on these positions.
TIME COMPLEXITY : O(max(N,Ai))
N -> size of the array
Ai -> max element of array
7. DNF Sort (Dutch National Flag Sort / 0,1,2 Sort)
This sorting technique is used to sort members in an array only when there are 3 distinct elements.
Application : Seggregate 0s and 1s in an array.
TIME COMPLEXITY : O(n)
SPACE COMPLEXITY : O(1)
8. Quick Sort
It is divide and conquer Algorithm.
APPROACH :
1. Pick a pivot element from array.
2. Partition around pivot element.
3. Arrange smaller elements before the pivot element and larger elements after the pivot element.
[NOTE: We can pick first, last, median or any random element as pivot. But it should remain same for entire Array]
TIME COMPLEXITY :
for Average Case : O(nlogn)
for Worst : O(n^2)
Hurray!! We have together completed major sorting algorithms..c'mon give a pat to yourself, you surely deserve it!😉
Hope you all loved it!💗
For more details visit :
for DNF Sort :
https://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/
for Wave Sort :
https://www.geeksforgeeks.org/sort-array-wave-form-2/
for rest :
https://www.geeksforgeeks.org/sorting-algorithms/
