implement and observe behavior of four sorts: Insertion Sort, Merge Sort, Heap S
ID: 3805261 • Letter: I
Question
implement and observe behavior of four sorts: Insertion Sort, Merge Sort, Heap Sort, and Quick Sort
Write a Java code that implements the textbook algorithms. As part of your code, you will include counters that iterate whenever a specific line of the algorithm is executed. Some lines in an algorithm may have a higher cost than other lines. For example, the function call in line 5 in the Merge Sort algorithm is executed only 7 times for an array with 8 elements, but the body of the Merge function which is being called has many lines, some of which are executed more than once. So the cost of line 5 in the Merge sort Algorithm is higher than the other 4 lines. We can use the cost of the highest-cost line as an indicator of the cost of the algorithm as a whole
Num8.txt file has
2
8
3
1
7
6
5
4
Explanation / Answer
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author Surya
*/
public class SortTesting {
//count variables
//global variable declaraionts..
static int quickCount=0;
static int heapCount=0;
static int mergeCount=0;
static int insertCount=0;
static int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<=high-1; j++)
{
// If current element is smaller than or
// equal to pivot
quickCount=quickCount+1;//incrementing global variable for quick sort
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] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
/* The main function that implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
static void Quicksort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
Quicksort(arr, low, pi-1);
Quicksort(arr, pi+1, high);
}
}
public static void Heapsort(int arr[])
{
int n = arr.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
static void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapCount =heapCount+1;//incrementing global count for heap sort...
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
public static void Insertionsort(int array[])//insertion sort....
{ int n = array.length;
for (int j = 1; j < n; j++)
{ int key = array[j];
int i = j-1;
while ( (i > -1) && ( array [i] > key ) )
{
insertCount=insertCount+1;//incrementing global count for quick sort
array [i+1] = array [i];
i--;
}
array[i+1] = key;
}
}
static void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];
/*Copy data to temp arrays*/
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];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
mergeCount=mergeCount+1;//incrementing global count for mergesort
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of L[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using
// merge()
static void Mergesort(int arr[], int l, int r)
{
if (l < r)
{
// Find the middle point
int m = (l+r)/2;
// Sort first and second halves
Mergesort(arr, l, m);
Mergesort(arr , m+1, r);
// Merge the sorted halves
merge(arr, l, m, r);
}
}
public static void main(String argv[]) throws FileNotFoundException
{
//reading file ...
Scanner scanner = new Scanner(new File("C:/Users/Surya/Desktop/Num8.txt"));//given correct path
int [] insertion = new int [8];//CREATing array with length 8//for insertion sort
int [] merge = new int [8];//CREATing array with length 8//for merge sort
int [] quick = new int [8];//CREATing array with length 8//for quick sort
int [] heap = new int [8];//CREATing array with length 8//for heap sort..
int i = 0;
while(scanner.hasNextInt())
{
merge[i]=heap[i]=quick[i]=insertion[i] = scanner.nextInt();//assigning values to arrays..
i++;
}
//calling sorting functions..
Insertionsort(insertion);//
Mergesort(merge,0,7);
Heapsort(heap);
Quicksort(quick,0,7);
//printing output..
System.out.println(" Insertion sort | Merge sort | Heap sort | Quick sort ");
System.out.println(" count "+insertCount+" "+mergeCount+" "+heapCount+" "+quickCount+" " );
i=0;
while(i<8)
{
System.out.println(" "+insertion[i]+" "+merge[i]+" "+heap[i]+" "+quick[i]+" " );
i++;
}
}
}
output:-
run:
Insertion sort | Merge sort | Heap sort | Quick sort
count 14 16 11 16
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
5 5 5 5
6 6 6 6
7 7 7 7
8 8 8 8
BUILD SUCCESSFUL (total time: 0 seconds)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.