Day 1- Start of 180 Day Challenge

This challenge is all about my daily learnings, including a story which I will update on my blog for the next 180 days in a continuity. I have given this challenge to myself to boost my morale and to adopt a habit of daily learning.

What I learned today:- Today I finished course of Data Structures and Algorithms in Java. It was a basic course, having all the details of basic data structures. So I am going to explain all that in my blog.

Arrays — Contiguous blocks in memory, every element occupies same amount of memory. Way to retrieve memory address

Lets say start address of Array is 12, element size is 4 bytes. Address of array[0] = 12, array[1] = 12 + (1*4) = 16, arrray[2] = 12+(2*4)=20, array[3] = 12 + (3*4) = 24 ……. and so on

Bubble Sort: One by one we compare 0th index of the array and change its position if lesser than ith index, till we reach the end of the array. When reach at the end, one pass is completed and we start again till the whole array becomes sorted. This is an in-place sort, i.e. it doesn't require extra space but it’s time complexity is worst i.e. O(n*n)

Stable sort vs Unstable sort: lets say if there are duplicate values in the array and one is at index 5 and the other is at index 7, after the sorting is done the value which was at index 7 comes to index 2 and the value which was at index 5 comes to index 3, the order is not maintained and it comes under unstable sort. If the order is maintained i.e. index 5 was placed at index 2 and index 7 was placed at index 3 after sorting, then it is stable sort, where we do care about the positions of the values weather it came earlier or not.

Insertion Sort: Insertion sort works similarly as we sort cards in our hand in a card game. We assume that the first card is already sorted then, we select an unsorted card. If the unsorted card is greater than the card in hand, it is placed on the right otherwise, to the left. In the same way, other unsorted cards are taken and put at their right place.

Shell Sort: It is variation of insertion sort, in insertion sort we compare values with gap 1, that is with the next index, in shell sort we take bigger gap, it can be 1,2,3 etc… This actually reduces the time complexity and save time to compare each and every value. Both insertion sort and shell sort are in-place algo and stable sort.

Recursion: Recursion refers to a function calling to itself, till the condition is met. Recursion store all the calls on call stack, till it get any return value and from that value it solve other functions in the stack.

Merge sort: It is kind of divide and conquer algorithm and recursively solved. It is divided into two phase splitting in merging. splitting leads to faster sorting during merging phase. basically we first sort the split array then we create a new array and merge all the values from right to left in sorted manner.

Counting Sort: This sort is used when we are aware of the range of the elements in the array, let’s say an array is have numbers between 1 to 10, the numbers can be repetitive and the array length is can any. We have to take a temp array of length 10, now we have to count frequency of the elements and update the count in temp array to there specific position, once we have added frequency of all elements, we will start with replace it to the actual value. This is not an in-place algorithm as it takes extra space to sort.

Radix Sort: It is used when all the elements in the array have same radix, by radix it means, if array contain 4digit integer, then all the values needs to be the same. And in this we start to sort from right most position of element, we first sort based on right most position of all elements. if its 4 digit number, we will compare it based on 1’s position and once it is sorted according to it, now we are going compare it based on 10’s position and so on, after comparing the 1000’s position, you will get a sorted array.