Sorting
Bubble Sort
public class BubbleSort { public static void main(String[] args) { int arr[]={2,5,1,8,3,9,4}; BubbleSort obj=new BubbleSort(); //calling sort method obj.sort(arr); System.out.println("Sorted Array :"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]+" "); } } private void sort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } }
Insertion Sort:
public class InsertionSort { public static void main(String[] args) { int arr[] = { 2, 5, 1, 8, 3, 9, 4 }; InsertionSort obj = new InsertionSort(); // calling sort method obj.insertion_sort(arr); System.out.println("Sorted Array :"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } private void insertion_sort(int[] arr) { int key = 0; int j = 0; for (int i = 2; i < arr.length; i++) { key = arr[i]; j = i; while (j > 0&&key < arr[j - 1]) { arr[j] = arr[j-1]; j = j - 1; } arr[j] = key; } } }
Merge Sort :
public class MergeSort { public static void main(String[] args) { int arr[] = { 2, 5, 1, 8, 3, 9, 4 }; MergeSort obj = new MergeSort(); // calling sort method obj.mergeSort(arr, 0, arr.length - 1); System.out.println("Sorted Array :"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } private void mergeSort(int[] arr, int start, int end) { if (start < end) { int mid = (start + end) / 2; mergeSort(arr, start, mid); mergeSort(arr, mid + 1, end); merge(arr, start, mid, end);//Merge function call } } private static void merge(int[] arr, int start, int mid, int end) { int size = end - start + 1; int tempArray[] = new int[size]; int indexFirstArr = start;// Starting index of First sub array int indexSecondArr = mid + 1;// Starting index of second sub array int idx = 0; while (size-- > 0) { if (indexFirstArr <= mid && indexSecondArr <= end) { if (arr[indexFirstArr] < arr[indexSecondArr]) { tempArray[idx++] = arr[indexFirstArr++]; } else { tempArray[idx++] = arr[indexSecondArr++]; } } else if (indexFirstArr <= mid) { tempArray[idx++] = arr[indexFirstArr++]; } else if (indexSecondArr <= end) { tempArray[idx++] = arr[indexSecondArr++]; } } for (int i = 0; i < tempArray.length; i++) { arr[start++] = tempArray[i]; } } }
Quick Sort:
public class QuickSort { public static void main(String[] args) { int arr[] = { 2, 5, 1, 8, 3, 9, 4 }; QuickSort obj = new QuickSort(); // calling sort method obj.quick_sort(arr, 0, arr.length - 1); System.out.println("Sorted Array :"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } private void quick_sort(int[] A, int start, int end) { if (start < end) { //partition function will do a partition of the array on the basis of the //Pivot element and will return the pivot index int pivotIndex = partition(A, start, end); //Then Smaller arrays to the left and right of the pivot will be //sorted recursively quick_sort(A, start, pivotIndex - 1); quick_sort(A, pivotIndex + 1, end); } } private static int partition(int A[], int start, int end) { //As a result of this function call //All the smaller elements will be moved to the left of the pivot element //And all the greater elements will be moved to the right side of the element //Pivot element will move to the correct position int i = start + 1; int pivotKey = A[start]; // considering the first element of the array as pivot element. for (int j = start + 1; j <= end; j++) { if (A[j] < pivotKey) { int temp = A[i]; A[i] = A[j]; A[j] = temp; i += 1; } } //Finally place the pivot element at its correct position int temp = A[start]; A[start] = A[i - 1]; A[i - 1] = temp; return i - 1; // return the position of the pivot } }
Selection Sort:
public class SelectionSort { public static void main(String[] args) { int arr[]={2,5,1,8,3,9,4}; SelectionSort obj=new SelectionSort(); //calling sort method obj.sort(arr); System.out.println("Sorted Array :"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]+" "); } } private void sort(int arr[]) { int minimum; int n = arr.length; for (int i = 0; i < n; i++) { minimum = i; for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minimum]) { minimum = j; } } // placing the minimum element on its proper position. swap(arr, minimum, i); } } private void swap(int[] a, int minimum, int i) { int temp = a[minimum]; a[minimum] = a[i]; a[i] = temp; } }