DSA Blog-1

DSA Blog-1

Welcome to the 1st blog of DSA blog series. Happy learning!

ยท

5 min read

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.

ย