Question

In: Computer Science

Write a java program which can randomly generate a permutation of the integer {1, 2, 3,...

Write a java program which can randomly generate a permutation of the integer {1, 2, 3, ..., 48,49,50}. Use the most efficient sorting algorithm to sort the list in an acceding order.

Solutions

Expert Solution

CODE:

import java.util.Random;
public class QuickSort
{
   /* This function takes last element as pivot,
   places the pivot element at its correct
   position in sorted array, and places all
   smaller (smaller than pivot) to left of
   pivot and all greater elements to right
   of pivot */
   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; j++)
       {
           // If current element is smaller than the pivot
           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 */
   void sort(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
           sort(arr, low, pi-1);
           sort(arr, pi+1, high);
       }
   }

   /* A utility function to print array of size n */
   static void printArray(int arr[])
   {
       int n = arr.length;
       for (int i=0; i<n; ++i)
           System.out.print(arr[i]+" ");
       System.out.println();
   }

   // Driver program
   public static void main(String args[])
   {
   Random rand = new Random();
       int arr[] = new int[50];
   int n = 50;
      
   for(int i=0;i<n;i++)
   arr[i] = rand.nextInt(100) + 1;
  
   System.out.println("generated array");
   printArray(arr);

       QuickSort ob = new QuickSort();
       ob.sort(arr, 0, n-1);

       System.out.println("sorted array");
       printArray(arr);
   }
}

OUTPUT:

Used Algorithm: Quick Sort

Although the worst-case time complexity of QuickSort is O(n2) which is more than many other sorting algorithms like Merge Sort and Heap Sort, QuickSort is faster in practice, because its inner loop can be efficiently implemented on most architectures, and in most real-world data.


Related Solutions

Write a program in java which randomly generates two integer number n1 and n2 (suppose the...
Write a program in java which randomly generates two integer number n1 and n2 (suppose the range for each integer is [1, 100]), then asks the user what is the value of n1*n2, if the user’s answer is correct, call method printGoodComment to print out something nice, otherwise, call printBadComment to print out something “mean”. The method signatures are:                   public static void printGoodComment() and                   public static void printBadComment() in your printGoodComment method, it will randomly print one sentence from the...
Write a program in java which randomly generates two integer number n1 and n2 (suppose the...
Write a program in java which randomly generates two integer number n1 and n2 (suppose the range for each integer is [1, 100]), then asks the user what is the value of n1*n2, if the user’s answer is correct, call method printGoodComment to print out something nice, otherwise, call printBadComment to print out something “mean”. The method signatures are:                   public static void printGoodComment() and                   public static void printBadComment() in your printGoodComment method, it will randomly print one sentence from the...
Write an Java/C program code to perform known-plaintext attack on Permutation Cipher. This program can be...
Write an Java/C program code to perform known-plaintext attack on Permutation Cipher. This program can be used to determine the length of the permutation m and the key permutation.
Using Miller-Rabin primality test algorithm to write a Java program which can test if an integer...
Using Miller-Rabin primality test algorithm to write a Java program which can test if an integer is a prime. The input of the algorithm is a large positive integer. The output is “the number *** is a prime” or “the number *** is not a prime”. The error probability of the algorithm should be no more than 1 256 . Use this program to test some big integers. In Java, there is a class BigInteger. You can use methods of...
in .java Write a program that reads an integer with 3 digits and prints each digit...
in .java Write a program that reads an integer with 3 digits and prints each digit per line in reverse order. Hint: consider what you get from these operations: 319%10, 319/10, 31%10, ... Enter an integer of exactly 3 digits(e.g. 538): 319 9 1 3 Hint: consider what you get from these operations: 319%10 319/10 31%10
java please 1. Write a Java program to generate random numbers in the following range a....
java please 1. Write a Java program to generate random numbers in the following range a. 1 <=n <= 3 b. 1 <= n <= 200 c. 0 <= n <= 9 d. 1000 <= n <= 2112 e. -1 <= n <= 5 2. Write statements that assign random integers to the variable n in the following ranges: a) 1 ≤ n ≤ 2 b) 1 ≤ n ≤ 100 c) 0 ≤ n ≤ 9 d) 1000 ≤...
*Java program* Use while loop 1.) Write a program that reads an integer, and then prints...
*Java program* Use while loop 1.) Write a program that reads an integer, and then prints the sum of the even and odd integers. 2.) Write program to calculate the sum of the following series where in is input by user. (1/1 + 1/2 + 1/3 +..... 1/n)
Write a Java program which reads a positive integer from the command line, then displays the...
Write a Java program which reads a positive integer from the command line, then displays the sum of all even values up to and including the value provided, followed by the sum of all odd values up to and including the value provided. validate that the command line argument is an integer greater than 0 to validate the type, you can use Integer.parseInt() with a try/catch for NumberFormatException use one or more for loops to perform the even and odd...
Write a Java program to generate random numbers in the following range a. 1 <=n <=...
Write a Java program to generate random numbers in the following range a. 1 <=n <= 3 b. 1 <= n <= 200 c. 0 <= n <= 9 d. 1000 <= n <= 2112 e. -1 <= n <= 5 JAVA PROGRAMMING
need to output this in java Enter an integer: 5 1 2 2 2 3 3...
need to output this in java Enter an integer: 5 1 2 2 2 3 3 3 3 3 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 3 3 3 3 3 2 2 2 1 (in the shape of a diamond) please help me with the correct code, thanks
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT