QuickSort

import java.util.Scanner;

public class QuickSort {
    
    public static void quickSort(int[] a, int lb, int ub) {
        if (lb < ub) {
            int pivotIndex = partition(a, lb, ub);
            quickSort(a, lb, pivotIndex - 1);
            quickSort(a, pivotIndex + 1, ub);
        }
    }

    public static int partition(int[] a, int lb, int ub) {
        int pivot = a[lb];
        int start = lb;
        int end = ub;
        while (start < end) {
            while (start <= ub && a[start] <= pivot) {
                start++;
            }
            while (a[end] > pivot) {
                end--;
            }
            if (start < end) {
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
            }
        }
        int temp = a[end];
        a[end] = a[lb];
        a[lb] = temp;
        return end;
    }

    public static void display(int[] a) {
        System.out.println("Sorted array:");
        for (int i : a) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter array size:");
        int n = sc.nextInt();
        int[] a = new int[n];
        
        System.out.println("Enter elements into array:");
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        quickSort(a, 0, n - 1);
        display(a);
        
        sc.close();
    }
}

import matplotlib.pyplot as plt
import numpy as np

n = np.linspace(1, 1000, 100)
best_case = n * np.log2(n) 
average_case = n * np.log2(n)  
worst_case = n ** 2  

plt.figure(figsize=(10, 6))
plt.plot(n, best_case, label='Best Case (O(n log n))', color='green')
plt.plot(n, average_case, label='Average Case (O(n log n))', color='blue')
plt.plot(n, worst_case, label='Worst Case (O(n^2))', color='red')

plt.title('Quick Sort Time Complexity')
plt.xlabel('Input Size (n)')
plt.ylabel('Number of Operations')
plt.legend()
plt.grid(True)
plt.show()