quicksort 1

 import java.util.Random;

public class QuicksortExample {

    public static void main(String[] args) {

        int N = 500; // Number of elements to sort

        // Initialize an array of random integers

        int[] arr = new int[N];

        Random rand = new Random();

        for (int i = 0; i < N; i++) {

            arr[i] = rand.nextInt(1000); // Random integers between 0 and 999

        }

        // Displaying the unsorted array (optional)

        System.out.println("Unsorted array:");

        printArray(arr);

        // Start measuring time

        long startTime = System.nanoTime();

        // Call the quicksort method

        quicksort(arr, 0, N - 1);

        // End measuring time

        long endTime = System.nanoTime();

        // Calculate time taken to sort

        long duration = (endTime - startTime); // Time in nanoseconds

        // Displaying the sorted array (optional)

        System.out.println("\nSorted array:");

        printArray(arr);

        // Display the time taken for sorting

        System.out.println("\nTime taken for Quicksort: " + duration + " nanoseconds.");

    }

    // Quicksort function using divide and conquer strategy

    public static void quicksort(int[] arr, int low, int high) {

        if (low < high) {

            // Partition the array

            int pivotIndex = partition(arr, low, high);

            // Recursively sort elements before and after partition

            quicksort(arr, low, pivotIndex - 1);

            quicksort(arr, pivotIndex + 1, high);

        }

    }

    // Partition function to select pivot and divide the array

    public static int partition(int[] arr, int low, int high) {

        // Choose the rightmost element as pivot

        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++; // increment index of smaller element

                swap(arr, i, j); // Swap elements at i and j

            }

        }

        // Swap the pivot element with the element at i+1

        swap(arr, i + 1, high);

        return i + 1; // Return the index of the pivot

    }

    // Helper function to swap elements in the array

    public static void swap(int[] arr, int i, int j) {

        int temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

    }

    // Helper function to print the array (optional)

    public static void printArray(int[] arr) {

        for (int i = 0; i < arr.length; i++) {

            System.out.print(arr[i] + " ");

        }

        System.out.println();

    }

}