Introduction
A sorting algorithm is a step-by-step method used to arrange a list of items in a specific order. One common sorting algorithm is the ‘Bubble Sort.’ In Bubble Sort, the algorithm compares adjacent elements in the list and swaps them if they are in the wrong order. This process is repeated until the entire list is sorted. It’s like ‘bubbling’ the largest element to the end of the list in each pass. Bubble Sort is simple but may not be the most efficient for large datasets. There are other sorting algorithms like ‘Insertion Sort’ and ‘Selection Sort’ that students can explore to understand different approaches to sorting.
Java program for bubble sort
Bubble Sort is a simple sorting algorithm that works by repeatedly stepping through the list of items to be sorted. It compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, indicating that the list is sorted. It gets its name because smaller elements ‘bubble’ to the top of the list, while larger elements ‘sink’ to the bottom. While Bubble Sort is easy to understand, it may not be the most efficient for large datasets compared to some other sorting algorithms.
import java.util.Scanner;
public class BubbleSort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of elements: ");
int n = scanner.nextInt();
int[] arr = new int[n];
System.out.println("Enter the elements:");
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
// Call the bubbleSort method
bubbleSort(arr);
System.out.println("Sorted array:");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
scanner.close();
}
// Bubble sort algorithm
static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}Java program for selection sort
Selection Sort is a straightforward sorting algorithm that works by dividing the list into two parts: a sorted and an unsorted portion. It repeatedly selects the smallest element from the unsorted part and swaps it with the first element of the unsorted part. This process continues until the entire list is sorted. Selection Sort is easy to understand, but it may not be the most efficient for large datasets. It’s like repeatedly finding the smallest card in a deck and placing it in the correct position until the entire deck is sorted.
import java.util.Scanner;
public class SelectionSort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of elements: ");
int n = scanner.nextInt();
int[] arr = new int[n];
System.out.println("Enter the elements:");
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
// Call the selectionSort method
selectionSort(arr);
System.out.println("Sorted array:");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
scanner.close();
}
// Selection sort algorithm
static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
// Find the index of the minimum element in the unsorted part
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}Java program for insertion sort
Insertion Sort is a simple sorting algorithm that builds the final sorted list one item at a time. It starts with the second element in the list and compares it with the elements before it, inserting it into the correct position. The process is repeated for each element, expanding the sorted portion of the list until all elements are in their proper places. Insertion Sort is intuitive and easy to implement, making it suitable for small datasets. It’s like sorting a deck of cards in your hand, where you pick one card at a time and insert it into its correct position.
import java.util.Scanner;
public class InsertionSort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of elements: ");
int n = scanner.nextInt();
int[] arr = new int[n];
System.out.println("Enter the elements:");
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
// Call the insertionSort method
insertionSort(arr);
System.out.println("Sorted array:");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
scanner.close();
}
// Insertion sort algorithm
static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1] that are greater than key to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
}Java program for quick sort
Quick Sort is an efficient sorting algorithm that uses a divide-and-conquer approach. It selects a ‘pivot’ element from the list and partitions the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The process is then applied recursively to the sub-arrays. Quick Sort is known for its speed and is widely used in practice. It’s like organizing a group of people by having a ‘pivot’ person and arranging others on either side based on whether they are taller or shorter than the pivot.
import java.util.Scanner;
public class QuickSort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of elements: ");
int n = scanner.nextInt();
int[] arr = new int[n];
System.out.println("Enter the elements:");
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
// Call the quickSort method
quickSort(arr, 0, n - 1);
System.out.println("Sorted array:");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
scanner.close();
}
// Quick sort algorithm
static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// Partition the array into two halves
int pi = partition(arr, low, high);
// Recursively sort each half
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Helper method to partition the array
static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap arr[i+1] and arr[high] (pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
}Java program for merge sort
Merge Sort is a divide-and-conquer algorithm used for sorting. It works by dividing the unsorted list into ‘halves’ until each sublist contains only one element. Then, it merges these smaller lists back together in a sorted manner. The merging process involves comparing elements from each sublist and arranging them in the correct order. Merge Sort is efficient for large datasets and guarantees a stable, consistent performance. It’s like organizing a deck of cards by repeatedly dividing it into smaller piles, sorting each pile, and then merging them back together in the correct order.
import java.util.Scanner;
public class MergeSort {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter the number of elements: ");
int n = scanner.nextInt();
int[] arr = new int[n];
System.out.println("Enter the elements:");
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
// Call the mergeSort method
mergeSort(arr, 0, n - 1);
System.out.println("Sorted array:");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
scanner.close();
}
// Merge sort algorithm
static void mergeSort(int[] arr, int left, int right) {
if (left < right) {
// Find the middle point
int mid = (left + right) / 2;
// Recursively sort the first and second halves
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
// Helper method to merge two subarrays of arr[]
static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
// Create temporary arrays
int[] leftArray = new int[n1];
int[] rightArray = new int[n2];
// Copy data to temporary arrays
for (int i = 0; i < n1; i++) {
leftArray[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
rightArray[j] = arr[mid + 1 + j];
}
// Merge the temporary arrays
// Initial indices of the subarrays
int i = 0, j = 0;
// Initial index of the merged subarray
int k = left;
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++;
} else {
arr[k] = rightArray[j];
j++;
}
k++;
}
// Copy remaining elements of leftArray[], if any
while (i < n1) {
arr[k] = leftArray[i];
i++;
k++;
}
// Copy remaining elements of rightArray[], if any
while (j < n2) {
arr[k] = rightArray[j];
j++;
k++;
}
}
}