coderz.py

What is Quick Sort?

Quick sort is a common sorting algorithm that sorts an array using the divide-and-conquer technique. Quick sort works by selecting a pivot element, partitioning the array around the pivot element, and recursively sorting the sub-arrays.

Algorithm:

The basic steps of the Quick sort algorithm are as follows:

• Choose one of the array’s pivot elements. The pivot element can be chosen in a variety of ways, but the most typical method is to choose the final member in the array.
• Divide the array into two sub-arrays: one with all elements smaller than the pivot, and the other with all elements greater than the pivot. This may be accomplished by starting two pointers at the beginning and end of the array, respectively, and moving towards each other until they cross.
• Sort the sub-arrays recursively. Separately apply the Quick sort algorithm to the two sub-arrays.
• Concatenate the sorted sub-arrays. Concatenate the sorted sub-arrays back together to produce the final sorted array.

Time Complexity:

• Worst case: O(n^2)
• Best case: Ω(n log(n))
• Average case: Θ(n log(n))

Implementation of the algorithm in Java:

public class QuickSort {
    public static void sort(int[] arr) {
        quicksort(arr, 0, arr.length - 1);
    }
    
    private static void quicksort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quicksort(arr, low, pivotIndex - 1);
            quicksort(arr, pivotIndex + 1, high);
        }
    }
    
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

The sort function in this version is a wrapper that executes the quicksort method with the complete array as input. The recursive implementation of the Quick sort algorithm is the quicksort technique. To partition the array around the pivot element, use the partition method. Finally, the swap function is used to swap array elements.

Problems based on Quick Sort:

• You are given an array of strings names, and an array heights that consists of distinct positive integers. Both arrays are of length n. For each index i, names[i] and heights[i] denote the name and height of the ith person.

Return names sorted in descending order by the people’s heights.

Example:

Input: names = ["Mary","John","Emma"], heights = [180,165,170]
Output: ["Mary","Emma","John"]
Explanation: Mary is the tallest, followed by Emma and John.

Solution:

class Solution {
    public String[] sortPeople(String[] names, int[] heights) {
        if (names == null || heights == null || names.length != heights.length) {
            throw new IllegalArgumentException("Invalid input.");
        }
        quicksort(names, heights, 0, names.length - 1);
        return names;
    }
     
    private static void quicksort(String[] names, int[] heights, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(names, heights, left, right);
            quicksort(names, heights, left, pivotIndex - 1);
            quicksort(names, heights, pivotIndex + 1, right);
        }
    }

    private static int partition(String[] names, int[] heights, int left, int right) {
        int pivot = heights[right];
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (heights[j] >= pivot) {
                i++;
                swap(names, i, j);
                swap(heights, i, j);
            }
        }
        swap(names, i + 1, right);
        swap(heights, i + 1, right);
        return i + 1;
    }

    private static void swap(String[] names, int i, int j) {
        String temp = names[i];
        names[i] = names[j];
        names[j] = temp;
    }
    private static void swap(int[] heights, int i, int j) {
        int temp = heights[i];
        heights[i] = heights[j];
        heights[j] = temp;
    }
}

The partition function selects the last element as the pivot and compares the heights of each element to determine which side of the pivot it should go. If the heights are the same, the elements are compared by names to break ties. The swap function is used to swap elements in both arrays at the same time.

• You are given an integer array arr. Sort the integers in the array in ascending order by the number of 1‘s in their binary representation, and in case of two or more integers have the same number of 1‘s you have to sort them in ascending order.

Return the array after sorting it.

Example:

Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Solution:

class Solution {
    
    public static int[] sortByBits(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return arr;
        }
        quicksort(arr, 0, arr.length - 1);
        return arr;
    }

    private static void quicksort(int[] arr, int left, int right) {
        if (left < right) {
            int pivotIndex = partition(arr, left, right);
            quicksort(arr, left, pivotIndex - 1);
            quicksort(arr, pivotIndex + 1, right);
        }
    }

    private static int partition(int[] arr, int left, int right) {
        int pivot = countOnes(arr[right]);
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (countOnes(arr[j]) < pivot || (countOnes(arr[j]) == pivot && arr[j] < arr[right])) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, right);
        return i + 1;
    }

    private static int countOnes(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

• The sortByBits method takes an integer array arr as input and returns the sorted array. It first checks if the input array is null or its length is less than or equal to 1, in which case it returns the array as is.
• Otherwise, it calls the quicksort method passing the array, left, and right indices.
• The quicksort method is a recursive implementation of the quicksort algorithm that uses the partition method to partition the input array into two parts, and sorts each part separately.
• The countOnes method takes an integer n as input and returns the number of 1’s in its binary representation.
• The swap method takes an integer array arr and two indices i and j as input, and swaps the elements at those indices.

Note: also read about Insertion Sort

Follow Me

Please follow me to read my latest post on programming and technology if you like my post.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py