sorts.notes

-----------------------------------------------------------
    Introduction to Sorting Algorithms
-----------------------------------------------------------

Sorting: Arranging the elements in a collection in an order of some property

Classification:
	1. Time Complexity
	2. Space Complexity
	3. Stability
		-> preserve related order of elements

Internal vs External Sort:
	ram		 disk

Recursive or Not-Recursive:

Selection Sort:

Linear scan for the lowest, then add to a new array which is sorted, or swapp with the curr at currenct pass
Time Complexity -> n^2
Space Complexity -> n or if you make swaps, which gives n^2  

always n squared since need to find min in each iteration anyway

Bubble Sort:

Bubble up the current largest element

always n^2

Insertion Sort:

essentional, you bubble downwards using a while loop

bestcase -> n

fastest since in best case it's n, however, still n^2 in worst case(reverse sored array)

Merge Sort:
  

Quick Sort:



[java]{
	public class Main {
	    public static void main(String[] args) {
	        int[] arr = {1,2,5,3,2,5,6,5,5,3,1,8,9};
	        selectionSort(arr);
	        for(int curr : arr){
	            System.out.print(curr);
	        }
	    }
	    
	    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 placeHolder = arr[j];
	                    arr[j] = arr[j+1];
	                    arr[j+1] = placeHolder;
	                }
	            }
	        }
	    }
	    
	     public static void selectionSort(int[] arr){
		        for(int i = 0; i<arr.length-1; i++){
		            
		            int min = i;
		            
		            for(int j = i; j<arr.length; j++){
		                if(arr[j] < arr[min]){
		                    min = j;
		                }
		            }
		            
		            int holderCurr = arr[i];
		            arr[i] = arr[min];
		            arr[min] = holderCurr;
		        }
		}

		public static void insertionSort(int[] arr){
	        for(int i = 1; i<arr.length-1; i++){
	            int value = arr[i];
	            int j = i;
	            while(j > 0 && arr[j-1] > value){
	                int placeholder = arr[j];
	                arr[j] = arr[j-1] ;
	                arr[j-1] = placeholder;
	                j--;
	            }
	        }
	    }
    	
    	public static void merge(int[] arr, int l, int r, int m){
        
	        int leftPointer = 0;
	        int rightPointer = 0;
	        int k = l;
	        
	        int[] left = new int[m-l+1];
	        int[] right = new int[r-m];
	        
	        for(int i = 0; i < left.length; i++){
	            left[i] = arr[l+i];
	        }
	        
	        for(int i = 0; i< right.length; i++){
	            right[i] = arr[m+1+i];
	        }
	        
	        while( k < r+1 ){
	           if(leftPointer == left.length && rightPointer <= right.length){
	                 arr[k] = right[rightPointer];
	                 rightPointer++;
	            }
	            else if(rightPointer == right.length && leftPointer < left.length){
	                arr[k] = left[leftPointer];
	                leftPointer++;
	            }
	            else if(left[leftPointer] < right[rightPointer]){
	                arr[k] = left[leftPointer];
	                leftPointer++;
	            } else {
	                arr[k] = right[rightPointer];
	                rightPointer++;
	            } 
	            k++;
	        }
	        
	        
	    }
	    
	    public static void mergeSort(int[] arr, int l, int r){
	        if(l<r){
	            int mid = (l+r)/2;
	            mergeSort(arr, l, mid);
	            mergeSort(arr, mid+1, r);
	            merge(arr, l, r, mid);
	        }
	    }
	    
	}
}[java]