Session 22: Sorting Revision

Original Session

Date: 26 Dec 2024

Topic: Sorting Revision

Concept: Insertion sort based on “Creating Gap”

Programs

1. Bubble Sort
   1. GFG here

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

2. Selection Sort
   1. GFG here

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

3. Insertion Sort
   1. GFG here

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

4. Merge Sort
   1. leetcode here

   public int[] sortArray(int[] nums) {
           
           mergeSort(nums, 0, nums.length-1);
           return nums;
       }
   
       void mergeSort(int[] nums, int low, int high) {
   
           if (low >= high) {
               return;
           }
   
           int mid = low + (high-low)/2;
   
           mergeSort(nums, low, mid);
           mergeSort(nums, mid+1, high);
   
           merge(nums, low, mid, high);
       }
   
       void merge(int[] nums, int low, int mid, int high) {
   
               int[] tempA = new int[high-low+1];
               int i=low, j=mid+1, index=0;
   
               while (i<=mid && j<=high) {
   
                   if (nums[i] <= nums[j]) {
                       tempA[index]=nums[i];
                       i++;
                   } else {
                       tempA[index]=nums[j];
                       j++;
                   }
                   index++;
               }
   
               while (i<=mid) {
   
                   tempA[index]=nums[i];
                   index++;
                   i++;
               }
   
               while (j<=high) {
   
                   tempA[index]=nums[j];
                   index++;
                   j++;
               }
   
               for (int k=low; k<=high; k++) {
                   nums[k] = tempA[k-low];
               }
       }

5. Quick Sort
   1. GFG here

   static void quickSort(int arr[], int low, int high) {
           
           if (low >= high) {
               return;
           }
           
           int p = partition(arr, low, high);
           quickSort(arr, low, p-1);
           quickSort(arr, p+1, high);
           
           
       }
   
       static int partition(int arr[], int low, int high) {
           // your code here
           int pivot = arr[low];
           int i = low+1;
           int j = high;
           
           while (i<=j) {
               
               while (i<=j && arr[i]<pivot) {
                   i++;
               }
               
               while (i<=j && arr[j]>pivot) {
                   j--;
               }
               if (i<=j) {
                   
                   int temp = arr[i];
                   arr[i] = arr[j];
                   arr[j] = temp;
                   
                   i++;
                   j--;
               }
               
           }
           
           int temp = arr[low];
           arr[low] = arr[j];
           arr[j] = temp;
           return j;
       }