Use the partition algorithm for the following array, [57, 45, 82, 87, 27, 72, 32

Question

Use the partition algorithm for the following array, [57, 45, 82, 87, 27, 72, 32, 57, 50, 33, 49, 8, 85, 71, 87, 38, 64, 27, 62, 19], choose element at index 0 as pivot element. Provide the partition results as well as the number of comparison and exchanges used. With the partition algorithm provided above, each call of SortUtilsisLessThan(...) s count as one comparison, and each of SortUtils.swa is count as one exchange. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 57 45 82 87 27 72 32 57 50 33 49 8 85 71 87 38 64 27 62 19 original Partition Result comparison exchange

Explanation / Answer

SortUtils.java

public class SortUtils {
  
   public static<T extends Comparable<T>> boolean isLessThan(T v, T w) {
       return v.compareTo(w) < 0;
   }

   public static<T> void swap(T[] a, int i, int j) {
       T t = a[i];
       a[i] = a[j];
       a[j] = t;
   }

}

MaxPQ.java

public class MaxPQ<Key extends Comparable<Key>> {
   private static int DEFAULT_CAPCITY=12;
   // heap-ordered complete binary tree
   // in pq[1..N] with pq[0] unused
   private Key[] pq;
   private int size = 0;
  
   public MaxPQ() {
       this(DEFAULT_CAPCITY+1);
   }

   @SuppressWarnings("unchecked")
   public MaxPQ(int maxN) {
       pq = (Key[]) new Comparable[maxN + 1];
       size = 0;
   }  
  
   public void insert(Key v) {
       // double size of array if necessary
        if (size == pq.length - 1) resize(2 * pq.length);
       pq[++size] = v;
       swim(size);
   }

   public boolean isEmpty() {
       return size == 0;
   }

   public int size() {
       return size;
   }
  
   public Key max() {
       if (size==0) {
           return null;
       } else {
           return pq[1];
       }
   }

   public Key delMax() {
       if (isEmpty()) return null;
      
       Key max = pq[1]; // Retrieve max key from top.
       swap(1, size--); // Exchange with last item.
       pq[size + 1] = null; // Avoid loitering.
       sink(1); // Restore heap property.
      
       if ((size > 0) && (size == (pq.length - 1) / 4)) resize(pq.length / 2);
       return max;
   }
  
   // bottom-up repheapify
   private void swim(int k) {
       while (k > 1 && SortUtils.isLessThan(pq[k/2], pq[k])) {
           SortUtils.swap(pq, k/2, k);
           k = k/2;
       }
   }

   // top-down repheapify
   private void sink(int k) {
       while (2*k <= size) {
           int j = 2*k;
           if (j < size && SortUtils.isLessThan(pq[j], pq[j + 1]))
               j++; // j is the index of the largest children
           if (!SortUtils.isLessThan(pq[k], pq[j]))
               break;
           SortUtils.swap(pq, k, j);
           k = j;
       }
   }
  
   @SuppressWarnings("unchecked")
   private void resize(int capacity) {
        assert capacity > size;
        Key[] temp = (Key[]) new Comparable[capacity];
        for (int i = 1; i <= size; i++) {
            temp[i] = pq[i];
        }
        pq = temp;
    }

   private void swap(int i, int j) {
       Key t = pq[i];
       pq[i] = pq[j];
       pq[j] = t;
   }

}

Sorting.java

import java.util.LinkedList;
import java.util.List;

/**
* Modified by firstname lastname
*
*/
public class Sorting {
  
   /**
   * @param list1 a list with elements in non-decreasing order, assume not null
   * @param list2 a list with elements in non-decreasing order, assume not null
   * @return a list that is the result of merging two inputs list in non-decreasing order
   */
   public static <T extends Comparable<T>> List<T> merge(List<T> list1, List<T> list2) {
       List<T> list = new LinkedList<T>();
       // provide implementation here
       return list;
   }
  
   /**
   * @param a String array where each element has one of the three values: "false", "maybe", or "true"
   * Give an O(N) algorithm to rearrange the elements so that all false elements precede maybe elements,
   * which in turn precede true elements. You may use only constant extra space.
   */
   public static void rearrange(String[] a) {
       throw new UnsupportedOperationException();
   }
  
   public static<T extends Comparable<T>> boolean isLessThan(T v, T w) {
       return v.compareTo(w) < 0;
   }  
  
   public static<T> void swap(T[] a, int i, int j) {
       T t = a[i];
       a[i] = a[j];
       a[j] = t;
   }  

}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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