Bucket sort (bin sort) is a stable sorting algorithm based on partitioning the input array into several parts – so called buckets – and using some other sorting algorithm for the actual sorting of these subproblems.

Description

At first algorithm divides the input array into buckets. Each bucket contains some range of input elements (the elements should be uniformly distributed to ensure optimal division among buckets).In the second phase the bucket sort orderes each bucket using some other sorting algorithm, or by recursively calling itself – with bucket count equal to the range of values, bucket sort degenerates to counting sort. Finally the algorithm merges all the ordered buckets. Because every bucket contains different range of element values, bucket sort simply copies the elements of each bucket into the output array (concatenates the buckets).

The asymptotic complexity of bucket sort is O(m \\cdot C(n/m)), where n is size of the input array, m is the number of buckets and C(x) is the complexity of the inner sorting algorithm.

Usage

Bucket sort can be used for distributed sorting – each bucket can be ordered by a different thread or even by a different computer. Another use case is a sorting of huge input data, which cannot be loaded into the main memory by an ordinary O(n\\cdot \\log(n)) algorithm. This problem can be solved by dividing the data into sufficiently small buckets, sorting them one by one by appropriate algorithm, while storing rest of the data in the external memory (e.g. hard drive).

Code

    /**
     * Bucket sort
     * @param array array to be sorted
     * @param bucketCount number of buckets
     * @return array sorted in ascending order
     */
    public static int[] bucketSort(int[] array, int bucketCount) {
        if (bucketCount <= 0) throw new IllegalArgumentException("Invalid bucket count");
        if (array.length <= 1) return array; //trivially sorted

        int high = array[0];
        int low = array[0];
        for (int i = 1; i < array.length; i++) { //find the range of input elements
            if (array[i] > high) high = array[i];
            if (array[i] < low) low = array[i];
        }
        double interval = ((double)(high - low + 1))/bucketCount; //range of one bucket

        ArrayList<Integer> buckets[] = new ArrayList[bucketCount];
        for (int i = 0; i < bucketCount; i++) { //initialize buckets
            buckets[i] = new ArrayList();
        }

        for (int i = 0; i < array.length; i++) { //partition the input array
            buckets[(int)((array[i] - low)/interval)].add(array[i]);
        }

        int pointer = 0;
        for (int i = 0; i < buckets.length; i++) {
            Collections.sort(buckets[i]); //mergeSort
            for (int j = 0; j < buckets[i].size(); j++) { //merge the buckets
                array[pointer] = buckets[i].get(j);
                pointer++;
            }
        }
        return array;
    }

SEO od společnosti Digital Pylon


Online casino s algoritmem

České casino online online slot-vegas.cz

Hrajte nejlepší hry jako je GoodGame Empire.





Zajímavé články: Jak najít práci snů? Zvolte kariéru v IT!, Češi mají rádi hrací automaty online, Jak funguje algoritmické obchodování Casino, Online výuka Algoritmus a online marketing mají svá pravidla, Automaty, Matematický vliv, Ratings, Jak fungují algoritmy hazardních her online: více znalostí, více peněz, SYPWAI - nástroj pro vědecký vývoj, Vynikají na globálním trhu: Nejlepší vývojáři softwaru pro online výherní automaty, Jak si vybrat nejlepší české online casino, Proč byste měli hrát online casino VPN revoluce, Kde najdeme algoritmy v každodenním životě?, Čeká vás pracovní pohovor mimo město? Podívejte se, jak dokonale zvládnout včasný příchod, 5 úžasných technologií ze světa hazardních her, Mirror and access to Mostbet, Svou kancelář můžete mít stále po ruce, Jaké výhody má digitalizovaná firma oproti off-line konkurenci?, Jaký systém vybrat pro snadné řízení výroby?, Nahradí umělá inteligence ajťáky?, Důvody, proč používat SnapTik ke stahování videí TikTok, Dokonalý den na pláži: Co si vzít s sebou, aby byl výlet zábavný a bezpečný?, Jak přežít dlouhý let?, Go pay GoodGame Empire, Blockchain, Rozhovor, Umělá inteligence


Doporučujeme

Internet pro vaši firmu na míru

https://www.algoritmy.net