Implement 4 sorting algorithms in a Java \" Sort \" class. ( insertion sort, sel

Question

Implement 4 sorting algorithms in a Java "Sort" class. ( insertion sort, selection sort and quicksort, and mergesort)

count the number of comparisons made.

Make sure each sort is producing sorted data and a correct metric count. Pause each iterative sort after one repetition of the outer loop and pause Quicksort after each Partition is complete.

Decide on a window size to display your sorting data. The window size must be N X N and its side length constrains the size of the array of data to be sorted. The example app uses a 500 X 500 window thus the array size is also 500.

Explanation / Answer

public class MyInsertionSort {     public static void main(String[] args) {                  int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };         insertionSort(input);     }          private static void printNumbers(int[] input) {                  for (int i = 0; i < input.length; i++) {             System.out.print(input[i] + ", ");         }         System.out.println(" ");     }     public static void insertionSort(int array[]) {         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 ) ) {                 array [i+1] = array [i];                 i--;             }             array[i+1] = key;             printNumbers(array);         }     } }


public class MySelectionSort {     public static int[] doSelectionSort(int[] arr){                  for (int i = 0; i < arr.length - 1; i++)         {             int index = i;             for (int j = i + 1; j < arr.length; j++)                 if (arr[j] < arr[index])                     index = j;                   int smallerNumber = arr[index];             arr[index] = arr[i];             arr[i] = smallerNumber;         }         return arr;     }          public static void main(String a[]){                  int[] arr1 = {10,34,2,56,7,67,88,42};         int[] arr2 = doSelectionSort(arr1);         for(int i:arr2){             System.out.print(i);             System.out.print(", ");         }     } }




public class Quicksort  {   private int[] numbers;   private int number;    public void sort(int[] values) {     // check for empty or null array     if (values ==null || values.length==0){       return;     }     this.numbers = values;     number = values.length;     quicksort(0, number - 1);   }    private void quicksort(int low, int high) {     int i = low, j = high;     // Get the pivot element from the middle of the list     int pivot = numbers[low + (high-low)/2];      // Divide into two lists     while (i <= j) {       // If the current value from the left list is smaller then the pivot       // element then get the next element from the left list       while (numbers[i] < pivot) {         i++;       }       // If the current value from the right list is larger then the pivot       // element then get the next element from the right list       while (numbers[j] > pivot) {         j--;       }        // If we have found a values in the left list which is larger then       // the pivot element and if we have found a value in the right list       // which is smaller then the pivot element then we exchange the       // values.       // As we are done we can increase i and j       if (i <= j) {         exchange(i, j);         i++;         j--;       }     }     // Recursion     if (low < j)       quicksort(low, j);     if (i < high)       quicksort(i, high);   }    private void exchange(int i, int j) {     int temp = numbers[i];     numbers[i] = numbers[j];     numbers[j] = temp;   } } 

public class Mergesort {   private int[] numbers;   private int[] helper;    private int number;    public void sort(int[] values) {     this.numbers = values;     number = values.length;     this.helper = new int[number];     mergesort(0, number - 1);   }    private void mergesort(int low, int high) {     // check if low is smaller then high, if not then the array is sorted     if (low < high) {       // Get the index of the element which is in the middle       int middle = low + (high - low) / 2;       // Sort the left side of the array       mergesort(low, middle);       // Sort the right side of the array       mergesort(middle + 1, high);       // Combine them both       merge(low, middle, high);     }   }    private void merge(int low, int middle, int high) {      // Copy both parts into the helper array     for (int i = low; i <= high; i++) {       helper[i] = numbers[i];     }      int i = low;     int j = middle + 1;     int k = low;     // Copy the smallest values from either the left or the right side back     // to the original array     while (i <= middle && j <= high) {       if (helper[i] <= helper[j]) {         numbers[k] = helper[i];         i++;       } else {         numbers[k] = helper[j];         j++;       }       k++;     }     // Copy the rest of the left side of the array into the target array     while (i <= middle) {       numbers[k] = helper[i];       k++;       i++;     }    } } 

public class MyInsertionSort {     public static void main(String[] args) {                  int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };         insertionSort(input);     }          private static void printNumbers(int[] input) {                  for (int i = 0; i < input.length; i++) {             System.out.print(input[i] + ", ");         }         System.out.println(" ");     }     public static void insertionSort(int array[]) {         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 ) ) {                 array [i+1] = array [i];                 i--;             }             array[i+1] = key;             printNumbers(array);         }     } }


public class MySelectionSort {     public static int[] doSelectionSort(int[] arr){                  for (int i = 0; i < arr.length - 1; i++)         {             int index = i;             for (int j = i + 1; j < arr.length; j++)                 if (arr[j] < arr[index])                     index = j;                   int smallerNumber = arr[index];             arr[index] = arr[i];             arr[i] = smallerNumber;         }         return arr;     }          public static void main(String a[]){                  int[] arr1 = {10,34,2,56,7,67,88,42};         int[] arr2 = doSelectionSort(arr1);         for(int i:arr2){             System.out.print(i);             System.out.print(", ");         }     } }




public class Quicksort  {   private int[] numbers;   private int number;    public void sort(int[] values) {     // check for empty or null array     if (values ==null || values.length==0){       return;     }     this.numbers = values;     number = values.length;     quicksort(0, number - 1);   }    private void quicksort(int low, int high) {     int i = low, j = high;     // Get the pivot element from the middle of the list     int pivot = numbers[low + (high-low)/2];      // Divide into two lists     while (i <= j) {       // If the current value from the left list is smaller then the pivot       // element then get the next element from the left list       while (numbers[i] < pivot) {         i++;       }       // If the current value from the right list is larger then the pivot       // element then get the next element from the right list       while (numbers[j] > pivot) {         j--;       }        // If we have found a values in the left list which is larger then       // the pivot element and if we have found a value in the right list       // which is smaller then the pivot element then we exchange the       // values.       // As we are done we can increase i and j       if (i <= j) {         exchange(i, j);         i++;         j--;       }     }     // Recursion     if (low < j)       quicksort(low, j);     if (i < high)       quicksort(i, high);   }    private void exchange(int i, int j) {     int temp = numbers[i];     numbers[i] = numbers[j];     numbers[j] = temp;   } } 

public class Mergesort {   private int[] numbers;   private int[] helper;    private int number;    public void sort(int[] values) {     this.numbers = values;     number = values.length;     this.helper = new int[number];     mergesort(0, number - 1);   }    private void mergesort(int low, int high) {     // check if low is smaller then high, if not then the array is sorted     if (low < high) {       // Get the index of the element which is in the middle       int middle = low + (high - low) / 2;       // Sort the left side of the array       mergesort(low, middle);       // Sort the right side of the array       mergesort(middle + 1, high);       // Combine them both       merge(low, middle, high);     }   }    private void merge(int low, int middle, int high) {      // Copy both parts into the helper array     for (int i = low; i <= high; i++) {       helper[i] = numbers[i];     }      int i = low;     int j = middle + 1;     int k = low;     // Copy the smallest values from either the left or the right side back     // to the original array     while (i <= middle && j <= high) {       if (helper[i] <= helper[j]) {         numbers[k] = helper[i];         i++;       } else {         numbers[k] = helper[j];         j++;       }       k++;     }     // Copy the rest of the left side of the array into the target array     while (i <= middle) {       numbers[k] = helper[i];       k++;       i++;     }    } } 

public class MySelectionSort {     public static int[] doSelectionSort(int[] arr){                  for (int i = 0; i < arr.length - 1; i++)         {             int index = i;             for (int j = i + 1; j < arr.length; j++)                 if (arr[j] < arr[index])                     index = j;                   int smallerNumber = arr[index];             arr[index] = arr[i];             arr[i] = smallerNumber;         }         return arr;     }          public static void main(String a[]){                  int[] arr1 = {10,34,2,56,7,67,88,42};         int[] arr2 = doSelectionSort(arr1);         for(int i:arr2){             System.out.print(i);             System.out.print(", ");         }     } }




public class Quicksort  {   private int[] numbers;   private int number;    public void sort(int[] values) {     // check for empty or null array     if (values ==null || values.length==0){       return;     }     this.numbers = values;     number = values.length;     quicksort(0, number - 1);   }    private void quicksort(int low, int high) {     int i = low, j = high;     // Get the pivot element from the middle of the list     int pivot = numbers[low + (high-low)/2];      // Divide into two lists     while (i <= j) {       // If the current value from the left list is smaller then the pivot       // element then get the next element from the left list       while (numbers[i] < pivot) {         i++;       }       // If the current value from the right list is larger then the pivot       // element then get the next element from the right list       while (numbers[j] > pivot) {         j--;       }        // If we have found a values in the left list which is larger then       // the pivot element and if we have found a value in the right list       // which is smaller then the pivot element then we exchange the       // values.       // As we are done we can increase i and j       if (i <= j) {         exchange(i, j);         i++;         j--;       }     }     // Recursion     if (low < j)       quicksort(low, j);     if (i < high)       quicksort(i, high);   }    private void exchange(int i, int j) {     int temp = numbers[i];     numbers[i] = numbers[j];     numbers[j] = temp;   } } 

public class Mergesort {   private int[] numbers;   private int[] helper;    private int number;    public void sort(int[] values) {     this.numbers = values;     number = values.length;     this.helper = new int[number];     mergesort(0, number - 1);   }    private void mergesort(int low, int high) {     // check if low is smaller then high, if not then the array is sorted     if (low < high) {       // Get the index of the element which is in the middle       int middle = low + (high - low) / 2;       // Sort the left side of the array       mergesort(low, middle);       // Sort the right side of the array       mergesort(middle + 1, high);       // Combine them both       merge(low, middle, high);     }   }    private void merge(int low, int middle, int high) {      // Copy both parts into the helper array     for (int i = low; i <= high; i++) {       helper[i] = numbers[i];     }      int i = low;     int j = middle + 1;     int k = low;     // Copy the smallest values from either the left or the right side back     // to the original array     while (i <= middle && j <= high) {       if (helper[i] <= helper[j]) {         numbers[k] = helper[i];         i++;       } else {         numbers[k] = helper[j];         j++;       }       k++;     }     // Copy the rest of the left side of the array into the target array     while (i <= middle) {       numbers[k] = helper[i];       k++;       i++;     }    } } 

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.