In: Computer Science
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.
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.