- Notifications
You must be signed in to change notification settings - Fork1
sb255/Algorithms
Folders and files
| Name | Name | Last commit message | Last commit date | |
|---|---|---|---|---|
Repository files navigation
- Big O Concept
- Searching Algorithms
- Sorting Algorithms
- Recursion
- BitWise Operation
- Dynamic Programming
data-type varName[size];
OR
data-type[size] varName;
int[] array = new int[size];
OR
int[] array = {0,1,2,3,4,5,6,7,8,9};
arr.length -> for calculating the length of all types of array (int[], String[], char[])
arr.size() -> for calculating the size of an object array(Ex. List array as it stores only objects)
.length -> It is used for calculating the length of all types of array (int[], String[], char[])
.length() -> It is used for calculating the length of a String
Run-time: Time taken or the Iteration made by function/algorithm to process the input. If the number of Iteration are equal to the given input x, then the run time will be O(x).
O(n):When run-time is proportional to the input size n. In an average case of a linear search algorithm, we have to check each value in an array, the run time in that case is proportional to the size of the array.O(1):When run-time is constant and independent of the input size.O(log(n)):When run-time increases exponentially with the size of input. In case of binary search, the worst case is O(log(n)).
intlinearSearch(int[]arr,intsearchElement){intarray[] =arr;intsElement =searchElement;for(inti=0;i<array.length;i++){if(array[i]==sElement)returni; }return -1; }
/*--We are assuming that the array is sorted and the array has more than one element--*/intbinarySearch(int[]array,intsearchElement,intstartingIndex,intendingIndex){intmiddleIndex = (startingIndex +endingIndex)/2;if(searchElement==array[middleIndex]){returnmiddleIndex; }elseif(searchElement<array[middleIndex]){returnbinarySearch(array,searchElement,startingIndex,middleIndex-1); }elseif(searchElement>array[middleIndex])returnbinarySearch(array,searchElement,middleIndex+1,endingIndex);elsereturn -1; }
| Search Algorithm | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) |
| Binary Search | O(1) | O(logn) | O(logn) |
| Search Algorithm | Space Complexity |
|---|---|
| Linear Search | O(1) |
| Binary Search | O(1) |
Bubble Sort:SWAPS the first two elements of the array and then swaps the adjacent elements, and keeps on SWAPPING until the array is sorted!
Merge Sort:First DIVIDES the array into two halves, SORT each of them and then MERGE them together!
Quick Sort:In quick sort, we create a partition known as PIVOT, and then divide the array on the basis of elements less than the PIVOT and the elements larger than the PIVOT element!
Selection Sort:Performs a LINEAR SCAN, find the smallest element and place it to 0th Index, and then keeps on doing the process until the array is sorted!
Insertion Sort:In Insertion sort, we COMPARE a element with the elements COMING BEFORE IT in the array, Ex: Element at INDEX=3, will be compared with the elements positioned at INDEX=0,1,2 respectively and then the element is placed at the correct position!
int[]generalSort(int[]arr){int[]ar = {2,3,4,1,8,9,5,6,7};intbuk =0;for(inti=0;i<ar.length;i++){for(intj=i+1;j<ar.length;j++){if(ar[i]>ar[j]) {buk =ar[i];ar[i] =ar[j];ar[j] =buk; } } }returnar; }
/*--In built methods for sorting Arrays and Lists--*/Arrays.sort(stringArray);Collections.sort(list);
| Sorting Algorithm | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(n^2) |
| Merge Sort | O(nlog(n)) | O(nlog(n)) | O(nlog(n)) |
| Quick Sort | O(nlog(n)) | O(nlog(n)) | O(n^2) |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) |
| Insertion Sort | O(n) | O(n^2) | O(n^2) |
| Sorting Algorithm | Space Complexity(Worst) |
|---|---|
| Bubble Sort | O(1) |
| Merge Sort | O(n) |
| Quick Sort | O(1) |
| Selection Sort | O(1) |
| Insertion Sort | O(1) |
/*--Printing the elements of a SinglyLinkedList in reverse order using recursion--*/staticvoidprintInReverse(Nodehead) {if(head ==null){ }else{printInReverse(head.next);System.out.println(head.data); } }//--Recursion Stack: [printInReverse1(printInReverse2(printInReverse3(...)))]//--Calling Order(LIFO): ..., printInReverse3, printInReverse2, printInReverse1
AND | &: It returns true if both the operands are true.OR | |: It returns true if at-least one of the operands is true.XOR | ^: It returns true if exactly one of the operands is true.