Explanation:
- Initialization: The constructor initializes a HashMap<Integer, Integer> to store the elements of the array. It also creates a keys array to keep track of the indices of the array elements.
- Sorting: The mergeSort method divides the keys array into subarrays and sorts them using the HashMap values for comparisons. The merge method merges the subarrays by comparing the values in the HashMap using the indices stored in the keys array.
- Printing: The printArray method prints the sorted values by retrieving them from the HashMap using the sorted keys.
import java.util.HashMap;
public class MergeSort {
private HashMap<Integer, Integer> map; // HashMap to store array elements
private int[] keys; // Array to keep track of the keys (indices)
// Constructor to initialize the HashMap and keys array
public MergeSort(int[] array) {
map = new HashMap<>();
keys = new int[array.length];
for (int i = 0; i < array.length; i++) {
map.put(i, array[i]);
keys[i] = i;
}
}
// Method to start the sorting process
public void sort() {
mergeSort(0, keys.length - 1);
}
// Recursive method to divide the array into smaller parts and merge them
private void mergeSort(int left, int right) {
if (left < right) {
int middle = (left + right) / 2; // Find the middle index
mergeSort(left, middle); // Sort the left subarray
mergeSort(middle + 1, right); // Sort the right subarray
merge(left, middle, right); // Merge the sorted subarrays
}
}
// Method to merge two sorted subarrays into a single sorted array
private void merge(int left, int middle, int right) {
int n1 = middle - left + 1; // Length of the left subarray
int n2 = right - middle; // Length of the right subarray
// Create temporary arrays to hold the left and right subarrays
int[] L = new int[n1];
int[] R = new int[n2];
// Copy data to temporary arrays
for (int i = 0; i < n1; ++i) {
L[i] = keys[left + i];
}
for (int j = 0; j < n2; ++j) {
R[j] = keys[middle + 1 + j];
}
// Merge the temporary arrays back into the original keys array
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (map.get(L[i]) <= map.get(R[j])) {
keys[k] = L[i];
i++;
} else {
keys[k] = R[j];
j++;
}
k++;
}
// Copy remaining elements of L[] if any
while (i < n1) {
keys[k] = L[i];
i++;
k++;
}
// Copy remaining elements of R[] if any
while (j < n2) {
keys[k] = R[j];
j++;
k++;
}
}
// Method to print the array
public void printArray() {
for (int key : keys) {
System.out.print(map.get(key) + " ");
}
System.out.println();
}
// Main method to demonstrate the usage of the MergeSort class
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
MergeSort sorter = new MergeSort(arr);
sorter.sort();
System.out.println("Sorted array:");
sorter.printArray();
}
}
MergeSort.main(null);
Sorted array:
5 6 7 11 12 13
Constructor:
public BubbleSort(List
import java.util.ArrayList;
import java.util.List;
public class BubbleSort {
private List<Integer> list; // ArrayList to be sorted
// Constructor to initialize the ArrayList
public BubbleSort(List<Integer> list) {
this.list = list;
}
// Method to start the sorting process
public void sort() {
bubbleSort();
}
// Method to perform bubble sort
private void bubbleSort() {
int n = list.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (list.get(j) > list.get(j + 1)) {
// Swap list[j] and list[j+1]
int temp = list.get(j);
list.set(j, list.get(j + 1));
list.set(j + 1, temp);
}
}
}
}
// Method to print the list
public void printList() {
for (int i : list) {
System.out.print(i + " ");
}
System.out.println();
}
// Main method to demonstrate the usage of the BubbleSort class
public static void main(String[] args) {
List<Integer> arr = new ArrayList<>();
arr.add(12);
arr.add(11);
arr.add(13);
arr.add(5);
arr.add(6);
arr.add(7);
BubbleSort sorter = new BubbleSort(arr);
sorter.sort();
System.out.println("Sorted list:");
sorter.printList();
}
}
BubbleSort.main(null);
Sorted list:
5 6 7 11 12 13
This code implements the Insertion Sort algorithm using the InsertionSort class. The sort method starts the sorting process, and insertionSort method performs the actual sorting. The printArray method is used to print the sorted array. Finally, the main method is used to demonstrate the usage of the InsertionSort class.
import java.util.LinkedList;
public class InsertionSort {
private LinkedList<Integer> list; // Linked list to be sorted
// Constructor to initialize the linked list
public InsertionSort(LinkedList<Integer> list) {
this.list = list;
}
// Method to start the sorting process
public void sort() {
insertionSort();
}
// Method to perform insertion sort on the linked list
private void insertionSort() {
if (list.size() < 2) {
return;
}
for (int i = 1; i < list.size(); i++) {
int key = list.get(i);
int j = i - 1;
// Shift elements of list[0..i-1], that are greater than key,
// to one position ahead of their current position
while (j >= 0 && list.get(j) > key) {
list.set(j + 1, list.get(j));
j--;
}
list.set(j + 1, key);
}
}
// Method to print the linked list
public void printList() {
for (int i : list) {
System.out.print(i + " ");
}
System.out.println();
}
// Main method to demonstrate the usage of the InsertionSort class
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(12);
list.add(11);
list.add(13);
list.add(5);
list.add(6);
list.add(7);
InsertionSort sorter = new InsertionSort(list);
sorter.sort();
System.out.println("Sorted list:");
sorter.printList();
}
}
InsertionSort.main(null);
Sorted list:
5 6 7 11 12 13
This code implements the Quick Sort algorithm similarly to how the Merge Sort algorithm was implemented. The QuickSort class contains the sort method to start the sorting process, quickSort method for recursive sorting, partition method for selecting pivot and rearranging the array, and printArray method for printing the sorted array. Finally, the main method is used to demonstrate the usage of the QuickSort class.
import java.util.LinkedList;
public class QuickSort {
private LinkedList<Integer> list; // LinkedList to be sorted
// Constructor to initialize the list
public QuickSort(LinkedList<Integer> list) {
this.list = list;
}
// Method to start the sorting process
public void sort() {
quickSort(0, list.size() - 1);
}
// Recursive method to divide the list into smaller parts and sort them
private void quickSort(int low, int high) {
if (low < high) {
// pi is partitioning index, list[pi] is now at right place
int pi = partition(low, high);
// Recursively sort elements before partition and after partition
quickSort(low, pi - 1);
quickSort(pi + 1, high);
}
}
// Partitioning method to select a pivot and rearrange the list
private int partition(int low, int high) {
int pivot = list.get(high); // Pivot (Element to be placed at right position)
int i = low - 1; // Index of smaller element
for (int j = low; j < high; j++) {
// If current element is smaller than the pivot
if (list.get(j) < pivot) {
i++;
// Swap list[i] and list[j]
swap(i, j);
}
}
// Swap list[i + 1] and pivot
swap(i + 1, high);
return i + 1;
}
// Method to swap two elements in the list
private void swap(int i, int j) {
int temp = list.get(i);
list.set(i, list.get(j));
list.set(j, temp);
}
// Method to print the list
public void printList() {
for (int i : list) {
System.out.print(i + " ");
}
System.out.println();
}
// Main method to demonstrate the usage of the QuickSort class
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(12);
list.add(11);
list.add(13);
list.add(5);
list.add(6);
list.add(7);
QuickSort sorter = new QuickSort(list);
sorter.sort();
System.out.println("Sorted list:");
sorter.printList();
}
}
QuickSort.main(null);
Sorted list:
5 6 7 11 12 13