Tech Master Tutorials
Email Facebook Google LinkedIn Pinterest Twitter
Home Java Java 8 Java Interview Questions Java Programming

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;
			}
		}