Program 1
Objective: Write a program to sort a given set of n integer elements using Merge Sort iterative sorting algorithms.
Code :
import [Link];
public class IterativeMergeSort {
// Merge two sorted subarrays arr[l..m] and arr[m+1..r]
public static void merge(int[] arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1)
arr[k++] = L[i++];
while (j < n2)
arr[k++] = R[j++];
}
// Iterative Merge Sort
public static void mergeSort(int[] arr) {
int n = [Link];
for (int currSize = 1; currSize <= n - 1; currSize = 2 * currSize) {
for (int leftStart = 0; leftStart < n - 1; leftStart += 2 * currSize) {
int mid = [Link](leftStart + currSize - 1, n - 1);
int rightEnd = [Link](leftStart + 2 * currSize - 1, n - 1);
merge(arr, leftStart, mid, rightEnd);
}
}
}
public static void main(String[] args) {
[Link]("YASH RAJ (24SCSE2140017)");
Scanner sc = new Scanner([Link]);
[Link]("Enter number of elements: ");
int n = [Link]();
int[] arr = new int[n];
[Link]("Enter " + n + " elements:");
for (int i = 0; i < n; i++) {
arr[i] = [Link]();
}
mergeSort(arr);
[Link]("Sorted array:");
for (int num : arr) {
[Link](num + " ");
}
[Link]();
}
}
Output:
Program 2
Objective: Write a program to sort a given set of n integer elements using Insertion Sort iterative sorting
algorithms.
Code:
public class InsertionSort {
public static void display(int arr[]){
for(int a : arr){
[Link](a + " ");
}
}
public static void main(String [] args){
[Link]("YASH RAJ (24SCSE2140017)");
int []arr={9,1,8,2,4,3};
int n = [Link];
for(int i = 1;i<n;i++){
int curr = arr[i];
int j = i-1;
while(j>=0 && curr<arr[j]){
arr[j+1]=arr[j];
j--;
}
arr[j+1] = curr;
}
display(arr);
}
}
Output:
Program 3
Objective: Write a program to sort a given set of n integer elements using Bubble Sort iterative sorting algorithms.
Code:
public class BubbleSort{
public static void display(int arr[]){
for(int var : arr){
[Link](var + " ");
}
}
public static void main(String [] args){
[Link]("YASH RAJ (24SCSE2140017)");
int [] arr = {999,0,44,9,22,11};
int n = [Link];
for(int i=0;i<n-1;i++){
for(int j=0;j<n-1-i;j++){
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
display(arr);
}
}
Output:
Program 4
Objective: Write a program to sort given set of numbers in ascending/descending order using Quick sort.
Code: Sort in Ascending Order
public class QuickSort {
public 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++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
i++;
int temp = arr[i];
arr[i] = arr[high];
arr[high] = temp;
return i;
}
public static void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotidx = partition(arr, low, high);
quickSort(arr, low, pivotidx - 1);
quickSort(arr, pivotidx + 1, high);
}
}
public static void display(int [] arr){
for(int var:arr){
[Link](var + " ");
}
}
public static void main(String[] args) {
[Link]("YASH RAJ (24SCSE2140017)");
int arr[] = { 33,0,9,1,7,2};
int n = [Link];
quickSort(arr, 0, n-1);
display(arr);
}
}
Output:
Sort in Descending Order
public class QuickSort {
public 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++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
i++;
int temp = arr[i];
arr[i] = arr[high];
arr[high] = temp;
return i;
}
public static void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotidx = partition(arr, low, high);
quickSort(arr, low, pivotidx - 1);
quickSort(arr, pivotidx + 1, high);
}
}
public static void display(int [] arr){
for(int var:arr){
[Link](var + " ");
}
}
public static void main(String[] args) {
[Link]("YASH RAJ (24SCSE2140017)");
int arr[] = { 6, 8, 2, 5, 7 };
int n = [Link];
quickSort(arr, 0, n-1);
display(arr);
}
}
Output:
Program 5
Objective: To sort a given set of n integer elements using Heap Sort sorting algorithms and compute their time
complexity for worst case, average case and best case.
Code:
import [Link];
public class HeapSort {
static void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
static void heapSort(int arr[]) {
int n = [Link];
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
public static void main(String[] args) {
[Link]("YASH RAJ (24SCSE2140017)");
int[] arr = {9,7,5,3,11};
heapSort(arr);
for (int num : arr)
[Link](num + " ");
}
}
Output: