Quick Sort Algorithm implimentation in Python, Java with Examples

Quick Sort is a highly efficient and widely used sorting algorithm. It is a comparison-based algorithm that uses a divide-and-conquer strategy to sort elements. Quick Sort is particularly popular because of its average-case performance of (O(n log n)), making it faster than other (O(n^2)) algorithms like Bubble Sort and Selection Sort for large datasets. Let's dive deeper into how Quick Sort works, followed by implementations in both Python and Java.

How Quick Sort Works

1. Divide and Conquer: Quick Sort works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The pivot can be selected in various ways: first element, last element, random element, or median.

2. Partitioning: The partition function reorders the array such that all elements with values less than the pivot come before it, and all elements with values greater come after it. This step is crucial as it ensures that the pivot is in its final sorted position.

3. Recursion: The algorithm recursively applies the above steps to the sub-arrays of elements with smaller values and greater values.

4. Base Case: The recursion ends when the array or sub-array has zero or one element, which is inherently sorted.

Python Implementation of Quick Sort

Below is a Python implementation of Quick Sort:

  def partition(arr, low, high):

    pivot = arr[high]

    i = low-1 #gretest element

    for j in range(low, high):

        if(arr[j] <= pivot):

            i+=1

            (arr[i], arr[j]) = (arr[j], arr[i])

            print("After swapped : ",arr)

    arr[i+1],arr[high] = arr[high], arr[i+1]

    print("After swapped with highest element : ",arr)

    return i + 1

  def quickSort(arr, low, high):

    if(low < high):

        print("Next Iteration")

        pivotIndx = partition(arr, low, high)

        quickSort(arr, low, pivotIndx-1)

        quickSort(arr, pivotIndx+1, high)

  # Driver code

  if __name__ == '__main__':

    arr = [80, 70, 60, 50, 40, 30, 20, 10]

    print("Unsorted array : ", arr)

    n = len(arr)

    low = 0

    high = n-1

    quickSort(arr, low, high)

    print("Sorted array : ", arr)

Java Implementation of Quick Sort

Below is a Java implementation of Quick Sort:

public class QuickSort {

    // Method to partition the array

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

        int pivot = arr[high];  // Choosing the last element as the pivot

        int i = low - 1;  // Index of the smaller element

        for (int j = low; j < high; j++) {

            if (arr[j] <= pivot) {

                i++;

                int temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

                System.out.println("After swapping: " + java.util.Arrays.toString(arr));

            }

        }

        int temp = arr[i + 1];

        arr[i + 1] = arr[high];

        arr[high] = temp;

        System.out.println("After swapping with the highest element: " + java.util.Arrays.toString(arr));

        return i + 1;

    }

    // Method to perform quicksort

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

        if (low < high) {

            System.out.println("Next Iteration");

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

            quickSort(arr, low, pivotIndex - 1);

            quickSort(arr, pivotIndex + 1, high);

        }

    }

    // Driver code

    public static void main(String[] args) {

        int[] arr = {80, 70, 60, 50, 40, 30, 20, 10};

        System.out.println("Unsorted array: " + java.util.Arrays.toString(arr));

        quickSort(arr, 0, arr.length - 1);

        System.out.println("Sorted array: " + java.util.Arrays.toString(arr));

    }

}

Explanation of the Code

1. Partition Function:

    - The pivot is chosen as the last element of the array.

    - Elements smaller than the pivot are moved to the left of the pivot.

    - Elements greater than the pivot are moved to the right.

    - Finally, the pivot is placed in its correct sorted position.

2. Quick Sort Function:

    - Recursively applies the partitioning process to sub-arrays.

    - Ensures that the sub-arrays are sorted by partitioning around the pivot.

Complexity Analysis

Time Complexity:

    - Best Case: (O(n log n)) when the pivot divides the array into two nearly equal halves.

    - Average Case: (O(n log n)) because it generally does divide the array into two parts.

    - Worst Case: (O(n^2)) when the smallest or largest element is always chosen as the pivot, leading to unbalanced partitions (e.g., already sorted array).

Space Complexity:

    - (O(log n)) due to the recursion stack in the best case.

    - (O(n)) in the worst case.

Conclusion

Quick Sort is an efficient, in-place sorting algorithm that uses a divide-and-conquer approach. It performs well on average, but care must be taken to avoid its worst-case scenario. Proper pivot selection can help ensure optimal performance. Both the Python and Java implementations demonstrate the core principles of the algorithm, highlighting its partitioning and recursive nature.