Question

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.

Answer 1

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(n²) 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.