Kauhan lajittelu on lajittelutekniikka, joka sisältää elementtien jakamisen eri ryhmiin tai ämpäriin. Nämä kauhat muodostetaan jakamalla elementit tasaisesti. Kun elementit on jaettu ryhmiin, ne voidaan lajitella millä tahansa muulla lajittelualgoritmilla. Lopuksi lajitellut elementit kootaan yhteen järjestyksessä.
Säilön lajittelualgoritmi:
Luoda n tyhjennä sangot (tai listat) ja tee seuraava jokaiselle taulukon elementille arr[i].
- Lisää arr[i] ämpäriin[n*array[i]]
- Lajittele yksittäiset ryhmät lisäyslajittelulla.
- Yhdistä kaikki lajitellut kauhat.
Kuinka ämpärilajittelu toimii?
Säilytyslajittelun käyttäminen syöttötaulukossa [0,78, 0,17, 0,39, 0,26, 0,72, 0,94, 0,21, 0,12, 0,23, 0,68] , noudatamme näitä vaiheita:
Vaihe 1: Luo taulukko, jonka koko on 10, jossa jokainen paikka edustaa ämpäriä.
Kauhojen luominen lajittelua varten
Vaihe 2: Lisää elementtejä syöttötaulukon ryhmiin niiden alueen perusteella.
Elementtien asettaminen ämpäriin:
muuntaa merkkijono int javaksi
- Ota jokainen elementti syöttötaulukosta.
- Kerro elementti kauhataulukon koolla (tässä tapauksessa 10). Esimerkiksi elementille 0.23 saamme 0.23 * 10 = 2.3.
- Muunna tulos kokonaisluvuksi, joka antaa meille bucket-indeksin. Tässä tapauksessa 2.3 muunnetaan kokonaisluvuksi 2.
- Aseta elementti laskettua indeksiä vastaavaan ämpäriin.
- Toista nämä vaiheet kaikille syöttötaulukon elementeille.
Array-elementtien lisääminen vastaaviin kauhoihin
Vaihe 3: Lajittele elementit kussakin ryhmässä. Tässä esimerkissä käytämme pikalajittelua (tai mitä tahansa vakaata lajittelualgoritmia) lajittelemaan elementit kussakin ryhmässä.
Elementtien lajittelu kussakin ryhmässä:
- Käytä vakaata lajittelualgoritmia (esim. kuplalajittelu, yhdistämislajittelu) lajitellaksesi elementit kussakin ryhmässä.
- Jokaisen ryhmän elementit on nyt lajiteltu.
Yksittäisen kauhan lajittelu
Vaihe 4: Kerää elementit kustakin ämpäristä ja laita ne takaisin alkuperäiseen taulukkoon.
Elementtien kerääminen jokaisesta ämpäristä:
10/40
- Toista jokainen ämpäri järjestyksessä.
- Lisää kukin yksittäinen elementti sängystä alkuperäiseen taulukkoon.
- Kun elementti on kopioitu, se poistetaan kauhasta.
- Toista tämä prosessi kaikille kauhoille, kunnes kaikki elementit on koottu.
Sanojen lisääminen nousevassa järjestyksessä tuloksena olevaan taulukkoon
Vaihe 5: Alkuperäinen taulukko sisältää nyt lajitellut elementit.
Lopullinen lajiteltu matriisi, jossa käytetään ryhmälajittelua tietylle syötteelle, on [0,12, 0,17, 0,21, 0,23, 0,26, 0,39, 0,68, 0,72, 0,78, 0,94].
Palauta lajiteltu taulukko
Sämpärilajittelualgoritmin toteutus:
Alla on Bucket Sort -sovelluksen toteutus:
C++ #include #include using namespace std; // Insertion sort function to sort individual buckets void insertionSort(vector& bucket) { for (int i = 1; i< bucket.size(); ++i) { float key = bucket[i]; int j = i - 1; while (j>= 0 && bucket[j]> avain) { bucket[j + 1] = bucket[j]; j--; } bucket[j + 1] = avain; } } // Toiminto lajitella arr[] koon n avulla bucket sort void bucketSort(float arr[], int n) { // 1) Luo n tyhjää kauhaa vektorib[n]; // 2) Laita taulukon elementit eri ryhmiin kohteelle (int i = 0; i< n; i++) { int bi = n * arr[i]; b[bi].push_back(arr[i]); } // 3) Sort individual buckets using insertion sort for (int i = 0; i < n; i++) { insertionSort(b[i]); } // 4) Concatenate all buckets into arr[] int index = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < b[i].size(); j++) { arr[index++] = b[i][j]; } } } // Driver program to test above function int main() { float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434}; int n = sizeof(arr) / sizeof(arr[0]); bucketSort(arr, n); cout << 'Sorted array is
'; for (int i = 0; i < n; i++) { cout << arr[i] << ' '; } return 0; }>
Java import java.util.ArrayList; import java.util.List; public class Main { // Insertion sort function to sort individual buckets public static void insertionSort(Listbucket) { for (int i = 1; i< bucket.size(); ++i) { float key = bucket.get(i); int j = i - 1; while (j>= 0 && bucket.get(j)> avain) { bucket.set(j + 1, bucket.get(j)); j--; } bucket.set(j + 1, avain); } } // Toiminto lajitella arr[] kokoa n käyttäen bucket sort public static void bucketSort(float[] arr) { int n = arr.length; // 1) Luo n tyhjää ämpärilistaa[] buckets = uusi ArrayList[n]; for (int i = 0; i< n; i++) { buckets[i] = new ArrayList(); } // 2) Put array elements in different buckets for (int i = 0; i < n; i++) { int bi = (int) (n * arr[i]); buckets[bi].add(arr[i]); } // 3) Sort individual buckets using insertion sort for (int i = 0; i < n; i++) { insertionSort(buckets[i]); } // 4) Concatenate all buckets into arr[] int index = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < buckets[i].size(); j++) { arr[index++] = buckets[i].get(j); } } } // Driver program to test above function public static void main(String[] args) { float[] arr = {0.897f, 0.565f, 0.656f, 0.1234f, 0.665f, 0.3434f}; bucketSort(arr); System.out.println('Sorted array is:'); for (float num : arr) { System.out.print(num + ' '); } } }> Python def insertion_sort(bucket): for i in range(1, len(bucket)): key = bucket[i] j = i - 1 while j>= 0 ja bucket[j]> avain: bucket[j + 1] = bucket[j] j -= 1 bucket[j + 1] = key def bucket_sort(arr): n = len(arr) buckets = [[] for _ in range(n)] # Laita taulukon elementit eri ryhmiin arvolle num in arr: bi = int(n * num) buckets[bi].append(num) # Lajittele yksittäiset ryhmät käyttämällä lisäyslajittelua ämpäriin: insertion_sort (bucket) # Yhdistä kaikki segmentit osaan arr[] index = 0, jos segmentti on segmentissä: jos numero on segmentissä: arr[index] = numeroindeksi += 1 arr = [0,897, 0,565, 0,656, 0,1234, 0,665, 0,656, 0,1234, 0,665, ]0. (arr) print('Lajiteltu taulukko on:') print(' '.join(map(str, arr)))> C# using System; using System.Collections.Generic; class Program { // Insertion sort function to sort individual buckets static void InsertionSort(Listbucket) { for (int i = 1; i< bucket.Count; ++i) { float key = bucket[i]; int j = i - 1; while (j>= 0 && bucket[j]> avain) { bucket[j + 1] = bucket[j]; j--; } bucket[j + 1] = avain; } } // Toiminto lajitella arr[] kokoa n käyttämällä bucket sort static void BucketSort(float[] arr) { int n = arr.Length; // 1) Luo n tyhjää ämpärilistaa[] buckets = uusi luettelo[n]; for (int i = 0; i< n; i++) { buckets[i] = new List(); } // 2) Laita taulukon elementit eri ryhmiin kohteelle (int i = 0; i< n; i++) { int bi = (int)(n * arr[i]); buckets[bi].Add(arr[i]); } // 3) Sort individual buckets using insertion sort for (int i = 0; i < n; i++) { InsertionSort(buckets[i]); } // 4) Concatenate all buckets into arr[] int index = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < buckets[i].Count; j++) { arr[index++] = buckets[i][j]; } } } // Driver program to test above function static void Main(string[] args) { float[] arr = { 0.897f, 0.565f, 0.656f, 0.1234f, 0.665f, 0.3434f }; BucketSort(arr); Console.WriteLine('Sorted array is:'); foreach (float num in arr) { Console.Write(num + ' '); } } }> JavaScript function insertionSort(bucket) { for (let i = 1; i < bucket.length; ++i) { let key = bucket[i]; let j = i - 1; while (j>= 0 && bucket[j]> avain) { bucket[j + 1] = bucket[j]; j--; } bucket[j + 1] = avain; } } function bucketSort(arr) { anna n = arr.length; anna buckets = Array.from({length: n}, () => []); // Laita taulukon elementit eri ryhmiin for (olkoon i = 0; i< n; i++) { let bi = Math.floor(n * arr[i]); buckets[bi].push(arr[i]); } // Sort individual buckets using insertion sort for (let i = 0; i < n; i++) { insertionSort(buckets[i]); } // Concatenate all buckets into arr[] let index = 0; for (let i = 0; i < n; i++) { for (let j = 0; j < buckets[i].length; j++) { arr[index++] = buckets[i][j]; } } } let arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]; bucketSort(arr); console.log('Sorted array is:'); console.log(arr.join(' '));> Lähtö
Sorted array is 0.1234 0.3434 0.565 0.656 0.665 0.897>
Sämpärilajittelualgoritmin monimutkaisuusanalyysi:
Aika monimutkaisuus: Päällä2),
- Jos oletetaan, että lisääminen ämpäriin vie O(1) aikaa, niin yllä olevan algoritmin vaiheet 1 ja 2 vievät selvästi O(n) aikaa.
- O(1) on helposti mahdollinen, jos käytämme linkitettyä listaa edustamaan ämpäri.
- Vaihe 4 vie myös O(n) aikaa, koska kaikissa ämpeissä on n tuotetta.
- Pääasiallinen analysointivaihe on vaihe 3. Tämä vaihe kestää myös keskimäärin O(n) aikaa, jos kaikki luvut ovat jakautuneet tasaisesti.
Aputila: O(n+k)