Sorting And Searching

Introduction

Common Data structures

• Array
• Linked List
• Stack
• Queue
• HashTable
• Tree
• Heap
• Graph

Space Complexity : Unit space required to store the data.

Time Complexity: Unit time required to complete any algorithm.

• Factorial of a number. = O(n)
• Print a 2D matrix = O(n*2)
• Print number to binary = O(logn)
• Print table of given number = O(1)
• Linear Search = O(n)

for(int i=0; i<arr.length; i++) {
	if(key == arr[i])
	return i;
}
Here since finding an element depends of length of array hence O(n) is timecomplexity

• Binary Search = O(logn)

//using Loop
	public static int binarySearch(int[] arr, int key) {
		int left = 0, right = arr.length-1, mid;
		while(left <= right) {	
			mid = (left + right) / 2;
			if(key == arr[mid])
				return mid;
			if(key < arr[mid])
				right = mid - 1;
			else //(key > arr[mid])
				left = mid + 1;
		}
		return -1;
	}

//using Recursion
	public static int binarySearch(int[] arr, int left, int right, int key) {
		if (left > right)
			return -1;
		int index, mid = (left + right) / 2;
		if (key == arr[mid])
			return mid;
		if (key < arr[mid])
			index = binarySearch(arr, left, mid - 1, key);
		else
			index = binarySearch(arr, mid + 1, right, key);
		return index;
	}

Here finding an element depends on 
1 = n/2^k
n = 2^k
k = logn
Hence number of iteration required for finding an element is Logn

• Selection Sort = O(n*2)

		for(int i=0; i<arr.length-1; i++) {
			for(int j=i+1; j<arr.length; j++) {
				if(arr[i] < arr[j]) {
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
		}
Time Complexity 
T > n(n - 1)/ 2 = N Factorial
t = n*2

• Bubble Sort = O(n * 2)

	public static void bubbleSort(int[] arr) {
		for(int i=0; i<arr.length-1; i++) {
			for(int j=0; j<arr.length-1; j++) {
				if(arr[j] > arr[j+1]) {
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
	
TimeComplexity for multiple loops are always n*2

• Insertion Sort = O(n * 2)

	public static void insertionSort(int[] arr) {
		for(int i=1; i<arr.length; i++) {
			int j, temp = arr[i];
			for(j=i-1; j >= 0 && arr[j] > temp; j--)
				arr[j+1] = arr[j];
			arr[j+1] = temp;
		}
	}
	

Merge Sort