Overview
If you don't know how to sort an array, simply take a pen and paper and just follow whatever I say. I guarantee you're gonna master it if you practice what I tell you to do.
Contents
Bubble sort
Selection sort
Insertion sort
Cycle sort
Sorting
Bubble sort
a.k.a. Sinking sort and Exchange sort.
a.k.a. Inplace sort because we don't have to create a new extra array.
Step 1 - In this sorting algorithm, in every step, we compare adjacent elements, starting from the index 0 and 1.
Step 2 - If the second element is smaller than the first element, swap them.
Step 3 - Do this process and you will observe after the first pass, the largest element is at the last index. Hence, the last index is sorted.
Step 4 - Do the process again (second pass) starting from index 0 and 1. You will observe that the second largest element will be at the second last index.
Step 5 - This way doing it, again and again, will lead to sorting the entire array.
Now take a pen and paper and sort {3, 5, 1, 4, 2} on your own.
Things to notice:
Take 2 elements, compare them, run 2 for loops, easy as fuck.
The reason for making boolean swapped is for reducing the time complexity.
If array is sorted {1, 2, 3, 4, 5} then no swap will occur and it will keep on checking the elements after i=0 has already ran. It will check for i=1,2,3,4 which will lead to a lot of time consumption. So, in this case where swapping will not occur we will simply break the loop.
Best case time complexity = O(n).
{1, 2, 3, 4, 5}
Worst case time complexity = O(n^2).
{5, 4, 3, 2, 1}
Space complexity = O(1) as no extra space is required.
Selection Sort
Step 1 - Select the largest element in your array.
Step 2 - Put it at its correct index i.e. the last index.
Step 3 - The outcome is the same as the bubble sort as the largest element is at the last index after each successive pass.
Step 4 - Select the second largest element in your array.
Step 5 - Put it at its correct index i.e. the second last index.
Step 6 - Do it all over and your array will be sorted.
not stable, works well for small arrays.
Now take a pen and paper and sort {4, 5, 1, 2, 3} on your own.
Things to notice:
We ran a for loop and swapped the last element with the element present at the maximum index.
int last = arr.length() - 1 because after every pass the last element will be sorted so we don't have to check again, although it doesn't make a difference if we do but it gives a positive impact anyways lol.
To find the index of largest element we make a function and pass and array, start, and end. So initialize your start element as the maximum element and simply run a loop to check if it is greater than the next elements and if the elements at the further index are greater then just update the maximum element.
Best case and worst case time complexity = O(n^2).
Space complexity = O(1) as no extra space is required.
Insertion Sort
Sort in parts. First, sort till index 1, then 2, then 3, then 4.
Step 1 - Start indexing with i as 0 and j as 1.
Step 2 - If (i > j), swap. Now 1st pass is done and the first 2 elements are sorted.
Step 3 - Increase both the pointers and compare j with its LHS i.e. the first 2 sorted elements (3 and 5).
Step 4 - Swap 4 as it is less than 5. The first 3 elements are sorted.
Step 5 - Now increase the j pointer and compare 1 with its LHS what do you see 5 is greater than 1, swap. Keep on swapping until 1 reaches its correct index i.e. 0.
Step 6 - Now do the same with 2 and your array is sorted.
don't forget to dry-run this using your pen and paper.
Things to notice:
Here, i will only go till i=0,1,2,3 and not 4 i.e. arr.length() - 1 because we have to compare j with the previous element and if the value of i is 4 then it will lead to an indexOutOfBoundsException.
Since we have to compare j with its LHS which is sorted its value will start from j=i+1.
Best case time complexity = O(n).
{1, 2, 3, 4, 5}
Worst case time complexity = O(n^2).
{5, 4, 3, 2, 1}
Space complexity = O(1) as no extra space is required.
Cycle Sort
most important and easiest sorting algorithm apparently.
we're gonna be using it on most of our problems.
says whenever no. are between (0-n) or (1-n) use this to sort.
Step 1 - Start indexing from i=0 and put the element at its correct index.
Step 2 - If index 0 contains 1 i.e. value + 1 then move pointer to index 1 and check if the element is at the correct index.
Step 3 - Suppose arr[0] = x.
Step 4 - Swap it with the element at index x - 1.
Step 5 - In this case x=3 and we put it at its correct index x - 1 i.e. 2.
Step 6 - Continue and eventually you'll sort the array.
don't forget to dry run this using your pen and paper.
Things to notice:
If arr[i] is not present at arr[correct], swap. But there's one more condition which becomes the most important part.
So let's say the indexes are 0,1,2,3,4 and values are 1,2,3,4,5. Therefore one extra condition will be put in that is arr[i] < arr.length
Best case and worst case time complexity = O(n^2).
Space complexity = O(1) as no extra space is required.
_______________________________________
That's all folks.
Hope this was helpful.
_______________________________________
Merge sort and Quick sort will get covered after I have posted a blog on recursion so that things get easier. And heap sort will get covered on heaps.
_______________________________________
Connect with me on socials for upcoming updates on blogs.
Thank you.