1 Overview In class, we have seen sorting algorithms that work by comparing, and

Question

1 Overview In class, we have seen sorting algorithms that work by comparing, and if necessary, swapping, adjacent elements. Now, we will improve upon this idea by swapping elements that are further apart. This document explains how to do this by means of an example It will be your job to implement the algorithm being explained and provide Java code that can be used for sorting. This homework is just as much about understanding an algorithm as it is about the final implementation in Java. Therefore: It is EXTREMELY important that you read the whole document before coding. The idea is to avoid large shifts (as may happen in insertion sort). The idea is to create "virtual sublists" and sort these one by one. These virtual lists are created based on the gap between elements. The final algorithm uses a sequence of gaps, starting with a large value, and getting recursively smaller. The gap values are given by gk gk-1 gi, where gi 1, and (1) Notice how each gap value depends on the previous one, as shown in the recursive definition of equation (1). The gap values start at gk Ln/2J, where n is the length of the array. 2 Algorithm Consider the simple array of integers, C35, 33, 42, 10, 14, 19, 27, 44], with the gap value set to be 4. We identify "virtual" sublists of numbers located with a gap of 4 positions, shown in Fig. 1. This yields four sublists of length 2 eac [35,14], [33, 19], [42,27], [10,44]. Then we compare values in each sublist, and whenever necessary, swap them in the original array. Once done, the new array will be [14, 19, 27, 10, 35, 33, 42, 44] Next, based on equation (1), we set the gap value to be L4/2 2. This generates two sublists of length 4 each: C14,27, 35,42] and [19, 10,33,44]. Just like before, we compare and if necessary, swap values. This step is shown in Fig. 2 By virtual, I mean that you just think of these as lists, but not actually create new list or array objects

Explanation / Answer

// tester class
import java.util.*;

public class Tester {
   public static void main(String args[]){
       //Sorter<Integer> insertionsorter = new InsertionSorter<Integer>();
       Sorter<Integer> treatmentsorter = new MergeSorter<Integer>();
      
       List<Integer> li = new ArrayList<Integer>();
       li.add(2);
       li.add(5);
       li.add(-2);
       li.add(26);
       li.add(23);
       li.add(21);
       // insertionsorter.sort(li, Order.ASCENDING);
       treatmentsorter.sort(li, Order.DESCENDING);
       for(int i = 0; i < li.size(); i++){
           System.out.println(li.get(i));
       }
   }
}

// sorter interface

import java.util.List;

// enumeration for order in which sort
enum Order {
   ASCENDING, DESCENDING
}

public interface Sorter<E extends Comparable<E>> {
   void sort(List<E> eList, Order order);
}

// insertion sort class

import java.util.*;

public class InsertionSorter<E extends Comparable<E>> implements Sorter<E> {
  
   public void sort(List<E> eList, Order order){
       int n = eList.size();
       // debug code
       // System.out.println(order == Order.ASCENDING);
       int s = 1;
       if(order == Order.DESCENDING)
           s = -1;
      
       for(int i = 0; i < n; i++){
           E x = eList.get(i);
           int j = i - 1;
           while(j >= 0 && eList.get(j).compareTo(x)*s > 0){
               eList.set(j+1, eList.get(j));
               j--;
           }
           eList.set(j+1, x);
       }
      
      
   }
}

// merge sort classs

import java.util.*;

public class MergeSorter <E extends Comparable<E>> implements Sorter<E>{
  
   public void merge(List<E> eList, int p, int q, int r, int s){
       int n1 = q - p + 1;
       int n2 = r - q;
       List<E> L = new ArrayList<E>();
       List<E> R = new ArrayList<E>();
       for(int i = 0; i < n1; i++){
           L.add(eList.get(p+i));
       }
       for(int j = 0; j < n2; j++){
           R.add(eList.get(q+j+1));
       }
      
       int i = 0, j = 0, k = p;
       while(i < n1 && j < n2){
           if(L.get(i).compareTo(R.get(j))*s <= 0){
               eList.set(k, L.get(i));
               i++;
           }else{
               eList.set(k, R.get(j));
               j++;
           }
           k++;
       }
      
       while(i < n1){
           eList.set(k, L.get(i));
           i++;
           k++;
       }
      
       while(j < n2){
           eList.set(k, R.get(j));
           j++;
           k++;
       }  
      
   }
  
   public void mergeSort(List<E> eList, int p, int r, int s){
       if(p < r){
           int q = (p + r)/2;
           mergeSort(eList, p, q, s);
           mergeSort(eList, q+1, r, s);
           merge(eList, p, q, r, s);
       }
   }
  
   public void sort(List<E> eList, Order order){
       int p = 0;
       int r = eList.size()-1;
       int s = 1;
       if(order == Order.DESCENDING)
           s = -1;
       mergeSort(eList, p, r, s);
   }
}

// gap sorter class

import java.util.List;

public class GapSorter <E extends Comparable<E>> implements Sorter<E>{
  
   public void sort(List<E> eList, Order order){
       int gap = eList.size()/2;
       int s = 1;
       if(order == Order.DESCENDING)
           s = -1;
      
       while(gap > 0){
           for(int i = gap; i < eList.size(); i++){
               int j = i;
               E k = eList.get(i);
               while(j >= gap && s*eList.get(i).compareTo(eList.get(j - gap)) < 0){
                   eList.set(j, eList.get(j-gap));
               }
               eList.set(j, k);
           }
           gap = gap/2;
       }
      
   }
}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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