gideonaina/DS&Algo.md

1.1.1 [Sorting Algorithm Stability](#sortingAlgorithmStability)

1.1.2 [Groups of Sorting Algorithm by Time complexity](#groupsOfsortingAlgorithm)

- [Quadratic Time Complexity Sorting Algorithm](#quadraticSortingAlgorithm)
	
- [Log-Linear Time Complexity Sorting Algorithm](#linearLogsortingAlgorithm)
	
- [Hybrid Sorting Algorithm](#hybridsortingAlgorithm)

1.2 Search Algorithm

1.2.1 [BinarySearchAlgorithm](#binarySearchAlgorithm)

1.3 Special Algorithms

1.3.1 [Euclidean Algorithm](#euclideanAlgorithm)

PART 2 - Data Structures

2.1 Binary Tree

2.1.1 [x](#x)

2.2 Linked List

2.2.1 [x](#x)

PART 3 - Concepts

3.1 Dynamic Programming

3.1.1 [x](#x)

PART 4 - Quick Interview Review

4.1 Logarithm (Complexity Analysis)

4.2 Graph Traversal (BFS & DFS)

4.3 Binary Search

4.4 Sliding Door (Two Pointers)

4.5 Recursion

4.6 Inverting Binary Tree & Reverse Linked List

4.7 Suffix Trees (ex. Finding substring in a string)

4.8 Heaps (Binary, Min & Max Heap)

4.9 Dynamic Programming

4.10 Sorting Algorithm (Quick & Merge Sort)

PART 1 - Algorithms

Sorting Algorithm

There different types of Sorting algorithm and one alogirthm could be better optimized for certain situation than other. For context, such situation includes list with:

Random (values)
Few unique values
Values sorted in reverse.
Almost sorted values.

Sorting Algorithm Stability [3]

"A stable sorting algorithm is the one that sorts the identical elements in their same order as they appear in the input, whilst unstable sorting does not guarantee this order" [3] For example give the list of fruits below:

peach
straw
apple
spork

If we sort the list by just the first letter of each word then a stable-sort would produce:

apple
peach
straw
spork

Why is Stability Important

"Say you have a list with each item having information about destination of the flight and departure time. You first sort the list based on time. We then sort it based on destination. If the second sort is stable we now have all flights bound to same destination together and in increasing order of departure time. If it wasn't stable, they wouldn't be in increasing order of time." [3]

You can't stack unstable sorts in the same fashion.

Stable Sorting Algorithms

Insertion Sort
Merge Sort
Bubble Sort
Tim Sort
Counting Sort
Block Sort
Quadsort
Library Sort
Cocktail shaker Sort
Gnome Sort
Odd–even Sort

Unstable Sorting Algorithms

Heap sort
Selection sort
Shell sort
Quick sort
Introsort (subject to Quicksort)
Tree sort
Cycle sort
Smoothsort
Tournament sort(subject to Hesapsort)

Groups of Sorting Algorithm by Time complexity

O(n²) Time Complexity Sorting Algorithm

Bubble Sort
Selection Sort
Insertion sort

Bubble Sort [4]

It is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order. See visual demostration in this Youtube Video. Its called "Bubble" because the largest value usually "bubbles" (move gradually till it gets to the top) to the end.

1. Where it does best?

In a small list.
Where a list is almost sorted.

2. Complexity (Time & Space)

Worst Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.
Auxiliary Space: O(1)

3. Code

Expand Here to See Code

//Editor - https://www.onlinegdb.com/edit/BJCPhqRRD
public class Main 
{ 
  // An optimized version of Bubble Sort 
  static void bubbleSort(int arr[], int n) 
  { 
  	int i, j, temp; 
  	
  	//Tracks when the inner loop does not swapp any element in the list
  	boolean swapped; 
  	
  	//Iterate up to i < n - 1: because there is nothing to compare the last value to.
  	for (i = 0; i < n - 1; i++) {
  	    
  		swapped = false; 
  		
  		/* Iterate up to j < n - i - 1: because last value in the list is usually the largest (bubbles),
  		* j < n - i -1 == j < n - 1 - i
  		* n - 1 : 	O index iteration for the array
  		* n - 1  - i:	because last value in the list is usually the largest (bubbles), no need to check
  		* it in next iteration.
  		*/
  		for (j = 0; j < n - i - 1; j++){ 
  		    
  			if (arr[j] > arr[j + 1]){ 
  			
  				// swap arr[j] and arr[j+1] 
  				temp = arr[j]; 
  				arr[j] = arr[j + 1]; 
  				arr[j + 1] = temp; 
  				swapped = true; 
  			} 
  		} 

  		/* If no two elements were 
  		* swapped by inner loop, then break
  		*/
  		System.out.printf("After %d pass => ", i);
  		printArray(arr);
  		System.out.println("");
  		if (swapped == false) 
  			break; 
  	} 
  } 

  // Function to print an array 
  static void printArray(int arr[]) 
  { 

  	for (int i = 0; i < arr.length; i++) 
  		System.out.print(arr[i] + " "); 
  } 

  // Driver program 
  public static void main(String args[]) 
  { 
// 		int arr[] = { 64, 34, 25, 12, 22, 11, 90 }; 
      int arr[] = { 5, 1, 4, 2, 9, 8}; 
      System.out.println("Raw array: "); 
  	printArray(arr); 
  	System.out.println("\n************************");
  	int n = arr.length; 
  	bubbleSort(arr, n); 
  	System.out.println("Sorted array: "); 
  	printArray(arr); 
  } 
}

Selection Sort 5

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. Watch visual of the Sorting Algorithm in this Youtube Video

Expand Here to See Code

	  static void selectionSort(int arr[]){
	        
        int n = arr.length; 
  
        // One by one move boundary of unsorted subarray 
        for (int i = 0; i < n-1; i++){
            
            // Find the minimum element in unsorted array 
            int min_idx = i; 
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[min_idx]) {
                    min_idx = j; 
                }
            }
            // Swap the found minimum element with the first 
            // element 
            int temp = arr[min_idx]; 
            arr[min_idx] = arr[i]; 
            arr[i] = temp; 
            
            System.out.printf("After %d pass => ", i);
			printArray(arr);
			System.out.println("************************");
        } 
    }

Insertion sort 6

"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" Youtube

O(NlogN) Time Complexity Sorting Algorithm

Hybrid Algorithm

Search Algorithm

Binary Search

Implements Binary Search Iteratively and Recursively.

Expand Here to See Code

public class MyClass {

//Main method to run both algorithm
    public static void main(String args[]) {

    int [] arr = new int [] {0, 1, 2, 3, 4, 5, 6, 7, 9, 10};

    //   System.out.println("Searched found at index " + bSearchI(arr, 6));
      System.out.println("\nSearched found at index " + bSearchR(arr, 6, 0, 10));
    }
    
    //Iterative Binary Search
    public static int bSearchI(int [] arr, int searchVal) {
    
    //Specify first, middle and last element index of the search boundry at the start of the search.
        int last = arr.length -1;
        int first = 0;
        int middle = 0;
        
        //Until first and last
        while(first <= last){
            middle = (last + first)/2;
            
            if(arr[middle] < searchVal){
                first = middle + 1;
                System.out.print("lesser - Starts@ %d  end@ %d" + arr[middle]);
            } else if (arr[middle] > searchVal){
                last = middle - 1;
                System.out.println("greater " + arr[middle]);
            } else {
                System.out.println("match " + arr[middle]);
                return middle;
            }
        }
        return -1;
    }
    
    //Recursive Binary Search.
    public static int bSearchR(int [] arr, int searchVal, int first, int last) {        
       if(first <= last) {
            
            int middle = (last + first)/2;
        
            if(arr[middle] == searchVal) {
                System.out.printf("\nmatched - Starts@ %d  middle %d", arr[first], arr[middle]);
                return middle;
            }
        
            if(arr[middle] < searchVal) {
                first = middle + 1;
                System.out.printf("\nlesser - Starts@ %d  middle %d end@ %d", arr[first], arr[middle], last);
                return bSearchR(arr, searchVal, first, last);
            } 
            
            if (arr[middle] > searchVal) {
                last = middle - 1;
                System.out.printf("\ngreater - Starts@ %d  middle %d end@ %d\n", arr[first], arr[middle], last);
                return bSearchR(arr, searchVal, first, last);
            } 
        }
        
        return -1;
    }
}

Special Algorithm

This Section is for specific named algorithm for performing certain basic task like testing Primality, GCD (Greatest Common Divisor), Square Root etc.

Euclidean Algorithm [7]

The Euclidean algorithm is basically a continual repetition of the division algorithm for integers. The point is to repeatedly divide the divisor by the remainder until the remainder is 0. The GCD is the last non-zero remainder in this algorithm. The example below demonstrates the algorithm to find the GCD of 102 and 38:

102%38 = 26
38%26 = 12
26%12=2
12%2=0

The GCD is 2 because it is the last non-zero remainder that appears before the algorithm terminates.

int  greatestCommonDivisor(int m, int n){

    if(n == 0) {
    	return m;
    }

    return greatestCommonDivisor(n, m % n);
}

NOTE: Switching m for n does not not matter. i.e it does not matter the greater of the two (m or n).

PART 2 - Data Structures

1. Binary Tree

Video to Watch: https://www.youtube.com/watch?v=09_LlHjoEiY

DFS BFS

PART 4 - Quick Interview Review

4.2 Graph Travesal

Depth First Traversals: The 3 travesal types arre name in reference to the position of the root.

(a) Inorder (Left, Root, Right) : 4 2 5 1 3 (Clockwise) - Root In between Left & Right

(b) Preorder (Root, Left, Right) : 1 2 4 5 3 - Root Pre (before) Left & Right

(c) Postorder (Left, Right, Root) : 4 5 2 3 1 (Anti Clockwise) - Root

Breadth-First or Level Order Traversal: 1 2 3 4 5

4.10. Sorting Algorithm 1. Quick Sort Best Case : N log N
Worst Case: N^2 When To Use: Often fastest in practice, can be in-place but not stable.

2. Mergesort
	Best Case : N log N    
	Worst Case: N log N
	When To Use: Stable but not in-place.

References

[1] https://www.youtube.com/watch?v=ZZuD6iUe3Pc

[2] https://www.youtube.com/watch?v=qk7b4-iyCJ4

[3] Stability in Sorting Algorithm - https://stackoverflow.com/questions/1517793/what-is-stability-in-sorting-algorithms-and-why-is-it-important

[4] Bubble Sort - https://www.geeksforgeeks.org/bubble-sort/

[5] Selection Sort - https://www.geeksforgeeks.org/selection-sort/

[6] Insertion Sort - https://www.geeksforgeeks.org/insertion-sort/

[7] Extended Euclidean Algorithm - https://brilliant.org/wiki/extended-euclidean-algorithm/

[8] Binary Tree Traversal - https://www.youtube.com/watch?v=BHB0B1jFKQc

[9] Binary Tree Types - https://www.upgrad.com/blog/5-types-of-binary-tree/

gideonaina/DS&Algo.md

Table of contents

PART 1 - Algorithms

PART 2 - Data Structures

PART 3 - Concepts

PART 4 - Quick Interview Review

PART 1 - Algorithms

Sorting Algorithm

Sorting Algorithm Stability [3]

Why is Stability Important

Groups of Sorting Algorithm by Time complexity

O(n2) Time Complexity Sorting Algorithm

Bubble Sort [4]

Selection Sort 5

Insertion sort 6

O(NlogN) Time Complexity Sorting Algorithm

Hybrid Algorithm

Search Algorithm

Binary Search

Special Algorithm

Euclidean Algorithm [7]

PART 2 - Data Structures

1. Binary Tree

PART 4 - Quick Interview Review

References

O(n²) Time Complexity Sorting Algorithm