Divide and Conquer
Assalamualaikum warahmatullah wabarakatuh( traditional Islamic greeting in Arabic "Assalamu alaikum": "Peace be upon you." "Wa rahmatullahi": "And the mercy of Allah." "Wa barakatuh": "And His blessings.") I’m Faraz Alam, and I’m documenting my journey through the world of software technology. Despite earning a master’s degree in Computer Applications and having access to opportunities provided by my tier-3 college, I struggled to take full advantage of them due to poor management and a less productive environment. This led to joblessness, primarily due to a lack of upskilling. Now, I am dedicated to enhancing my skills and knowledge with the aim of securing a valuable job offer from leading product-based companies, including those in the FAANG group (Facebook, Amazon, Apple, Netflix, Google) and other prominent tech giants. This documentation is not for self-promotion; rather, it is for anyone who is waiting for an opportunity but feels they lack the tools and skills required to overcome challenges. It’s a testament to the effort and responsibility needed to navigate the journey towards success when you take charge of your own path. Date: 31 July 2024, 07:25 AM This page will be updated regularly to reflect new achievements and milestones as I continue to build my career.
Level:- 1
Write a program to implement merge sort.
public class Merge { public static void MergeSort(int arr[], int si, int ei) { if (si >= ei) { return; } int mid = si + (ei - si) / 2; MergeSort(arr, si, mid);//left part MergeSort(arr, mid + 1, ei);//right part merge(arr, si, mid, ei); } public static void merge(int arr[], int si, int mid, int ei) { //left(0,3)=4, right(4,6)=3-> 6-0+1, as array is zero based int temp[] = new int[ei - si + 1]; int i = si;//left part int j = mid + 1;//right part int k = 0;//temp arr while (i <= mid && j <= ei) { if (arr[i] < arr[j]) { temp[k] = arr[i]; i++; } else { temp[k] = arr[j]; j++; } k++; } //if something left in left part while (i <= mid) { temp[k++] = arr[i++]; } //right part while (j <= ei) { temp[k++] = arr[j++]; } //copy temp to original array for (k = 0, i=si; k < temp.length; k++, i++) { arr[i] = temp[k]; } } public static void printArray(int arr[]) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } public static void main(String[] args) { int arr[] = { 6, 3, 9, 5, 2, 8 }; MergeSort(arr, 0, arr.length - 1); printArray(arr); } }
Write a program to implement Quick Sort.
public class Quick { public static void quickSort(int arr[], int si, int ei) { if (si >= ei) { return; } //last is pivot int pidx=partition(arr, si, ei); quickSort(arr,si,pidx-1);//left quickSort(arr,pidx+1,ei);//right } public static int partition(int arr[], int si, int ei) { int pivot = arr[ei]; int i = si - 1; for (int j = si; j <ei; j++) { if (arr[j] <= pivot) { i++; int temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } } i++; int temp = pivot; arr[ei] = arr[i];//pivot=arr[i] arr[i] = temp; return i; } public static void print(int arr[]) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } public static void main(String[] args) { int arr[] = { 6, 3, 8, 9, 2, 5 }; quickSort(arr, 0, arr.length - 1); print(arr); } }
