Session 17: Sorting

Original Session

Date: 14 Dec 2024

Topic: Sorting

1. Concept: Bubble Sort - Largest element to the right, keep moving large value between adjacent indexes to the right till end of array, keep reducing end of array by one. Since each iteration will have largest element in the end.
   
   

2. Concept: Selection Sort - Smallest element to the left. Mark small number with minPointer and replace left value with minPointer, keep moving left by 1, since left most value will have smallest numer.

Programs

1. Bubble Sort

       void bubleSort(int[] arr) {
    
           int n = arr.length;
           int temp = 0;
           for (int i=0; i<n; i++) {
            
               for (int j=0; j<n-i-1; j++) {
                
                    if (arr[j] > arr[j+1]) {
                        temp = arr[j+1];
                        arr[j+1] = arr[j];
                        arr[j] = temp;
                    }
                }
           }
       }

2. Selection Sort

   void selectionSort(int[] arr) {
        // mark the min element using minPointer, then replace it with left pointer.
        int n = arr.length;
        int temp = 0;
        int minPointer = 0;
        for (int i=0; i<n; i++) {
        
            minPointer = i;
            for (int j=i; j<n; j++) {
                
                if (arr[minPointer] > arr[j]) {
                    minPointer = j;
                }
            }
            
            temp = arr[i];
            arr[i] = arr[minPointer];
            arr[minPointer] = temp;
        }
   }

3. Find second smallest with Selection Sort

   int kthSmallestUsingSelection(int[] arr, int k) {
    
        int n = arr.length;
        if (k > n) {
           return -1;
        }
        // mark the min element using minPointer, then replace it with left pointer.
        int temp = 0;
        int minPointer = 0;
        for (int i=0; i<k; i++) {
        
            minPointer = i;
            for (int j=i; j<n; j++) {
            
                if (arr[minPointer] > arr[j]) {
                   minPointer = j;
                }
            }
            
            temp = arr[i];
            arr[i] = arr[minPointer];
            arr[minPointer] = temp;
        }
        return arr[k-1];
    }

4. Insertion Sort

       void insertionSort(int[] arr) {
           
           int n = arr.length;
           
           for (int i=1; i<n; i++) {
               
               int key = arr[i];
               int correctIndex = i-1;
               
               while (correctIndex >= 0 && arr[correctIndex] > key) {
                   
                   arr[correctIndex+1] = arr[correctIndex];
                   correctIndex--;
               }
               arr[correctIndex+1] = key;
           }
       }

5. Count Sort

   void countSort(int[] arr) {
           
           int n = arr.length;
           int sizeOfCountArr = 0;
           
           for (int value: arr) {
               
               if (sizeOfCountArr < value) {
                   sizeOfCountArr = value;
               }
           }
           sizeOfCountArr ++;
           
           int[] countArr = new int[sizeOfCountArr];
           for (int value: arr) {
               
               countArr[value] ++;
           }
           
           int index = 0, indexCountArr=0;
           while (index < n && indexCountArr < sizeOfCountArr) {
               
               int value = countArr[indexCountArr];
               if (value == 0) {
                   indexCountArr++;
                   continue;
               }
               
               
               for (int i = index; i < index + value; i++) {
                   arr[i] = indexCountArr;
               }
               index+=value;
               indexCountArr++;
           }
           
       }

6. Merge Two Sorted Array

   int[] merge(int[] arr1, int[] arr2) {
   
   	    int[] newArr = new int[arr1.length + arr2.length];
   	    
   	    int left = 0, right = 0, index = 0;
   	    
   	    while (left < arr1.length && right < arr2.length) {
   	        
   	        if (arr1[left] < arr2[right]) {
   	            newArr[index] = arr1[left];
   	            left ++;
   	        } else {
   	            newArr[index] = arr2[right];
   	            right ++;
   	        }
   	        index ++;
   	    }
   	    
   	    while (left < arr1.length) {
   	            
               newArr[index] = arr1[left];
               index ++;
               left ++;
           }
   	    
   	    if (right < arr2.length) {
   	        
   	        newArr[index] = arr2[right];
   	        right ++;
   	    }
   	    
   	    return newArr;
       }

7. Merge Sort

   To be Done

8. Quick Sort

   At 3:10 in video
   https://platform.bosscoderacademy.com/course/wqLtH3fgbDYn365HceNU?tab=0