Day 18: Quick Sort

Quick Sort is one of the most efficient and widely used sorting algorithms in computer science. Its efficiency and performance make it a favorite among developers. In this post, we’ll explore the Quick Sort algorithm, provide its implementation in Java, analyze its time complexity, and present some example problems.

What is Quick Sort?

Quick Sort is a divide-and-conquer sorting algorithm. It 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 sub-arrays are then sorted recursively. This process continues until the entire array is sorted.

How Quick Sort Works:

1. Choose a pivot element from the array.
2. Partition the array into two halves: elements less than the pivot and elements greater than the pivot.
3. Recursively apply the above steps to the sub-arrays.

Implementation in Java

Here’s how you can implement Quick Sort in Java:

javaCopy codepublic class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            // Recursively sort elements before and after partition
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // pivot
        int i = (low - 1); // Index of smaller element
        for (int j = low; j < high; j++) {
            // If current element is smaller than or equal to 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;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: " + java.util.Arrays.toString(arr));
    }
}

Time Complexity Analysis

• Best Case: O(n log n) – This occurs when the pivot divides the array into two equal halves.
• Average Case: O(n log n) – On average, Quick Sort performs well, maintaining its logarithmic nature.
• Worst Case: O(n²) – This occurs when the pivot is consistently the smallest or largest element, leading to unbalanced partitions (e.g., when the array is already sorted).

Example Problems

1. Example 1: Given an array of integers: {12, 11, 13, 5, 6, 7}, using Quick Sort will transform it to {5, 6, 7, 11, 12, 13}.
2. Example 2: Given an array: {3, 6, 8, 10, 1, 2, 1}, applying Quick Sort results in {1, 1, 2, 3, 6, 8, 10}.

Conclusion

Quick Sort is a powerful and efficient sorting algorithm, particularly well-suited for large datasets. Its divide-and-conquer strategy, combined with an average time complexity of O(n log n), makes it a go-to choice for many applications.

In our next post, we will explore Searching Algorithms, including Linear and Binary Search. Stay tuned!

Also see: The Z Blogs

my other Blog: The Z Blog ZBDay 18: Quick Sort

Quick Sort is one of the most efficient and widely used sorting algorithms in computer science. Its efficiency and performance make it a favorite among developers. In this post, we’ll explore the Quick Sort algorithm, provide its implementation in Java, analyze its time complexity, and present some example problems.

What is Quick Sort?

Quick Sort is a divide-and-conquer sorting algorithm. It 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 sub-arrays are then sorted recursively. This process continues until the entire array is sorted.

How Quick Sort Works:

1. Choose a pivot element from the array.
2. Partition the array into two halves: elements less than the pivot and elements greater than the pivot.
3. Recursively apply the above steps to the sub-arrays.

Implementation in Java

Here’s how you can implement Quick Sort in Java:

javaCopy codepublic class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            // Recursively sort elements before and after partition
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // pivot
        int i = (low - 1); // Index of smaller element
        for (int j = low; j < high; j++) {
            // If current element is smaller than or equal to 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;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: " + java.util.Arrays.toString(arr));
    }
}

Time Complexity Analysis

• Best Case: O(n log n) – This occurs when the pivot divides the array into two equal halves.
• Average Case: O(n log n) – On average, Quick Sort performs well, maintaining its logarithmic nature.
• Worst Case: O(n²) – This occurs when the pivot is consistently the smallest or largest element, leading to unbalanced partitions (e.g., when the array is already sorted).

Example Problems

1. Example 1: Given an array of integers: {12, 11, 13, 5, 6, 7}, using Quick Sort will transform it to {5, 6, 7, 11, 12, 13}.
2. Example 2: Given an array: {3, 6, 8, 10, 1, 2, 1}, applying Quick Sort results in {1, 1, 2, 3, 6, 8, 10}.

Conclusion

Quick Sort is a powerful and efficient sorting algorithm, particularly well-suited for large datasets. Its divide-and-conquer strategy, combined with an average time complexity of O(n log n), makes it a go-to choice for many applications.

In our next post, we will explore Searching Algorithms, including Linear and Binary Search. Stay tuned!

Also see: The Z Blogs

my other Blog: The Z Blog ZBDay 18: Quick Sort

Quick Sort is one of the most efficient and widely used sorting algorithms in computer science. Its efficiency and performance make it a favorite among developers. In this post, we’ll explore the Quick Sort algorithm, provide its implementation in Java, analyze its time complexity, and present some example problems.

What is Quick Sort?

Quick Sort is a divide-and-conquer sorting algorithm. It 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 sub-arrays are then sorted recursively. This process continues until the entire array is sorted.

How Quick Sort Works:

1. Choose a pivot element from the array.
2. Partition the array into two halves: elements less than the pivot and elements greater than the pivot.
3. Recursively apply the above steps to the sub-arrays.

Implementation in Java

Here’s how you can implement Quick Sort in Java:

javaCopy codepublic class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            // Recursively sort elements before and after partition
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // pivot
        int i = (low - 1); // Index of smaller element
        for (int j = low; j < high; j++) {
            // If current element is smaller than or equal to 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;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: " + java.util.Arrays.toString(arr));
    }
}

Time Complexity Analysis

• Best Case: O(n log n) – This occurs when the pivot divides the array into two equal halves.
• Average Case: O(n log n) – On average, Quick Sort performs well, maintaining its logarithmic nature.
• Worst Case: O(n²) – This occurs when the pivot is consistently the smallest or largest element, leading to unbalanced partitions (e.g., when the array is already sorted).

Example Problems

1. Example 1: Given an array of integers: {12, 11, 13, 5, 6, 7}, using Quick Sort will transform it to {5, 6, 7, 11, 12, 13}.
2. Example 2: Given an array: {3, 6, 8, 10, 1, 2, 1}, applying Quick Sort results in {1, 1, 2, 3, 6, 8, 10}.

Conclusion

Quick Sort is a powerful and efficient sorting algorithm, particularly well-suited for large datasets. Its divide-and-conquer strategy, combined with an average time complexity of O(n log n), makes it a go-to choice for many applications.

In our next post, we will explore Searching Algorithms, including Linear and Binary Search. Stay tuned!

Also see: The Z Blogs

my other Blog: The Z Blog ZB