Campus Zone

  Quick sort   : In quick sort, we will consider a pivot element and divide the array so that all the lesser element will be in left side of pivot element while all the greater element will be in right side.    This process we will continue recursively until array is fully sorted.      Time complexity will beO(nlogn) but in worst case when elements are in sorted order time complexity will become O(n^2) as in each call only one element will be consider as sorted and for rest again we need to follow same process.      space complexity will be O(1). class QuickSort { public static void sort ( int [] array) { int n = array. length ; shuffle (array) ; sort (array , 0 , n - 1 ) ; } private static void sort ( int [] array , int lo , int hi) { if (hi <= lo) return; int j = partition (array , lo , hi) ; sort (array , lo , j - 1 ) ; sort (array , j + 1 , hi) ; } ...

  Merge sort   : In merge sort we will divide the array from middle recursively  until we have only one element in sub-array. After that we will merge sub-array in ascending order.     Time complexity for merge sort will be O(nlogn) as we are splitting the array from middle so each time it's getting half so for that  it will be log(n) and while merging we are traversing the whole array so for that it will be O(n).      So after combining both  time complexity will be O(n)+O(logn)= O(nlogn)      space complexity will be O(n) as we need a extra same size array to hold the unsorted array. class MergeSort { public static void sort ( int [] array) { int [] aux = new int [array. length ] ; sort (array , aux , 0 , array. length - 1 ) ; } private static void sort ( int [] array , int [] aux , int lo , int hi) { if (hi <= lo) return; int mid = (lo + hi) / 2 ; sort (arra...

  Insertion sort  :  In insertion sort, Same process like selection sort , we will divide the array in sorted and unsorted array and we will select element from unsorted array and will insert it into sorted array at its proper position.    Time Complexity for Insertion sort also is O(n^2).    space complexity for bubble sort will be O(1). class InsertionSort { public static void sort ( int [] array) { int n = array. length ; for ( int i = 1 ; i < n ; i++) { for ( int j = i ; j > 0 && array[j] < array[j - 1 ] ; j--) { swap (array , j , j - 1 ) ; } } } private static void swap ( int [] A , int i , int j) { int temp = A[i] ; A[i] = A[j] ; A[j] = temp ; } private static void print ( int [] A) { System. out .print( "[" ) ; for ( int i = 0 ; i < A. length ; i++) { System. out .print(A[i]) ; ...

  Selection sort  : In selection sort we will divide the Array in 2 parts , sorted and unsorted and select the min element from unsorted and will copy to sorted array.      Time Complexity for selection sort also is O(n^2).      space complexity for bubble sort will be O(1). class SelectionSort { public static void sort ( int [] array) { int n = array. length ; for ( int i = 0 ; i < n - 1 ; i++) { int min = i ; for ( int j = i + 1 ; j < n ; j++) { if (array[j] < array[min]) { min = j ; } } swap (array , i , min) ; } } private static void swap ( int [] array , int i , int j) { int temp = array[i] ; array[i] = array[j] ; array[j] = temp ; } private static void print ( int [] array) { System. out .print( "[" ) ; for ( int i = 0 ; i < array. lengt...

  Single Linked List :  In Single link list each node will have 2 parts , first part will have Data while next part will have a pointer which will keep the address of its next node, while node itself will not be aware of anything apart from its next node address. Below is sample program without Tail. In this program appending an element to link list will have time complexity as O(n) as we need to travers till end of the link list to find out the last element in link list. But if we will use Tail node along with Head then time complexity for adding an element will be O(n) but still insertion of a node after a specific node will be O(n). Sample program without Tail node. import java.io.IOException ; import java.util.Scanner ; class Node { Node next = null; int data ; public Node ( int val) { data = val ; } } class LinkList { Node head = null; public void append ( int val) { if ( head == null ) { head = new Node(val) ; ...

Bubble sort  : In bubble sort ,we will select the 1st element and compare with all the remaining element, same process we will continue for all the elements as we are traveling the whole Array 2 times except the element which we have selected to compare with other elements but still it will be consider as n time.    So time complexity for bubble sort will be O(n^2).         space complexity for bubble sort will be O(1). // Bubble Sort class BubbleSort { public static void sort ( int [] array) { int n = array. length ; while ( true ) { boolean swapped = false; for ( int i = 0 ; i < n - 1 ; i++) { if (array[i + 1 ] < array[i]) { swap (array , i , i + 1 ) ; swapped = true; } } if (!swapped) break; } } private static void swap ( int [] array , int i , int j) { int temp = array[i] ;...

Bubble sort : In bubble sort ,we will select the 1st element and compare with all the remaining element, same process we will continue for all the elements as we are traveling the whole Array 2 times except the element which we have selected to compare with other elements but still it will be consider as n time.    So time complexity for bubble sort will be O(n^2).         space complexity for bubble sort will be O(1). Selection sort : In selection sort we will divide the Array in 2 parts , sorted and unsorted and select the min element from unsorted and will copy to sorted array.      Time Complexity for selection sort also is O(n^2).      space complexity for bubble sort will be O(1). Insertion sort :  In insertion sort, Same process like selection sort , we will divide the array in sorted and unsorted array and we will select element from unsorted array and will insert it into sorted array at its proper...