An algorithm for continuously outputting interview questions -- assignment sorting

Opening introduction

Hello everyone, I'm sister tights from the most complete interview question bank in Java. Today's article is the fifth on data structures and algorithms, which mainly introduces assignment sorting; In the follow-up, we will continue to summarize along the knowledge line at the beginning of the first article, so as to achieve daily improvement! If I can do 100 days and 100 shifts, I hope you can also follow 100 days and 100 brushes to form a good habit in 100 days.

Allocation sort

The sorting algorithms discussed above are based on the comparison between keywords, and it has been proved in theory:
For such sorting, at least [lgn] keyword comparisons should be made no matter what method is used. According to Stirling formula, lgn ≈ nlgn-1.44n+0(lgn), so the lower bound of sorting time based on keyword comparison is O(nlgn). However, if you do not sort by comparing keywords, you may break through this lower bound. Allocation sorting is just like this. The sorting process does not need to compare keywords, but realizes sorting through "allocation" and "collection" processes, and their time complexity can reach the linear order: O(n)
Allocation sorting includes bucket sorting and cardinality sorting

Bucket sorting

Bucket sort works by dividing the array into a limited number of buckets. Each bucket is sorted individually (it is possible to use another sorting algorithm or continue to use bucket sorting in a recursive manner).

Algorithm steps:
Suppose there is a set of keyword sequence K [1... N] with length n to be arranged.
1. Firstly, the sequence is divided into M sub intervals (buckets).
2. Then, based on a mapping function, the keyword k of the sequence to be arranged is mapped to the ith bucket (i.e. the subscript i of bucket array B), and then the keyword k is used as an element in B[i] (each bucket B[i] is a group of sequences with a size of N/M).
3. Compare and sort all elements in each bucket B[i] (fast sorting can be used).
4. Then enumerate the output B [0] All contents in B [M] are an ordered sequence

characteristic:

  • Time complexity: O(n+k)
  • Space complexity: O(n+k)
  • Stability: stable

Code implementation:

public class BucketSort {

    private static final InsertSort insertSort = new InsertSort();

    public int[] sort(int[] sourceArray) throws Exception {
        // Copy the arr without changing the parameters
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return bucketSort(arr, 5);
    }

    private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
        if (arr.length == 0) {
            return arr;
        }

        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }

        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];

        // The mapping function is used to allocate the data to each bucket
        for (int i = 0; i < arr.length; i++) {
            int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], arr[i]);
        }

        int arrIndex = 0;
        for (int[] bucket : buckets) {
            if (bucket.length <= 0) {
                continue;
            }
            // Sort each bucket. Insert sort is used here
            bucket = insertSort.sort(bucket);
            for (int value : bucket) {
                arr[arrIndex++] = value;
            }
        }

        return arr;
    }

    /**
     * Automatically expand capacity and save data
     *
     * @param arr
     * @param value
     */
    private int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

}

Cardinality sort

Radix sort is an extension of bucket sort. Its basic idea is:
Cut the integer into different numbers according to the number of digits, and then compare them respectively according to each number of digits.

Specific method: unify all values to be compared into the same digit length, and fill zero in front of the shorter digit. Then, start from the lowest order and sort once in turn. In this way, the sequence will become an ordered sequence from the lowest order to the highest order.

Algorithm steps
1. Unify all values to be compared (positive integers) into the same digit length, and fill zero in front of the shorter digit.
2. Start from the lowest order and sort once in sequence.
3. In this way, the sequence will become an ordered sequence from the lowest order to the highest order.

characteristic:

  • Time complexity: O(n*k)
  • Space complexity: O(n+k)
  • Stability: stable

Code implementation:

public class RadixSort {

    public int[] sort(int[] sourceArray) throws Exception {
        // Copy the arr without changing the parameters
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }

    /**
     * Get the highest number of digits
     */
    private int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    protected int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // Considering the negative number, the number of queues is doubled here, where [0-9] corresponds to a negative number and [10-19] corresponds to a positive number (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

    /**
     * Automatically expand capacity and save data
     *
     * @param arr
     * @param value
     */
    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}

Tags: Java

Posted by Johannes80 on Tue, 17 May 2022 11:28:08 +0300