Give a variation of Algorithm 19.2 (randomSort) that runs in O(n) time with prob

Question

Give a variation of Algorithm 19.2 (randomSort) that runs in O(n) time with probability of 1-1/n4

The pseudo code is required. Therefore, it is not programming language specific

Algorithm randomSort(X): Input: A list, X, of n elements Output: A permutation of X so that all permutations are equally likely Let K be the smallest power of 2 greater than or equal to n3 for each element, ri, in X do Choose a random value, ri, in the range 0,K-11 and associate it with zi Sort X using the ri values as keys via radix-sort if all the ri values are distinct then return X according to this sorted order else Call random Sort(X) Algorithm 19.2: A sorting-based algorithm for generating a random permutation.

Explanation / Answer

//RandomSort.java

public class RandomSort {

   public RandomSort(int[] i) {
       int counter = 0;
       System.out.println("I'll sort " + i.length + " elements...");
       while(!isSorted(i)) {
           shuffle(i);
           counter++;
       }
       System.out.println("Solution found! (shuffled " + counter + " times)");
       print(i);
   }

   private void print(int[] i) {
       for(int x : i) {
           System.out.print(x + ", ");
       }
       System.out.println();
   }

   private void shuffle(int[] i) {
       for(int x = 0; x < i.length; ++x) {
           int index1 = (int) (Math.random() * i.length),
               index2 = (int) (Math.random() * i.length);
           int a = i[index1];
           i[index1] = i[index2];
           i[index2] = a;
       }
   }

   private boolean isSorted(int[] i) {
       for(int x = 0; x < i.length - 1; ++x) {
           if(i[x] > i[x+1]) {
               return false;
           }
       }
       return true;
   }

   /**
   * @param args
   */
   public static void main(String[] args) {
       int[] i = {1, 5, 2, 8, 5, 2, 4, 2, 6, 7, 66};
       new RandomSort(i);
   }

}

Sample Output1:

I'll sort 11 elements...
Solution found! (shuffled 2485888 times)
1, 2, 2, 2, 4, 5, 5, 6, 7, 8, 66,

Sample Output2:

I'll sort 11 elements...
Solution found! (shuffled 2158793 times)
1, 2, 2, 2, 4, 5, 5, 6, 7, 8, 66,

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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