Hink sort är en sorteringsteknik som går ut på att dela in element i olika grupper, eller hinkar. Dessa hinkar bildas genom att elementen fördelas jämnt. När elementen väl är uppdelade i hinkar kan de sorteras med vilken annan sorteringsalgoritm som helst. Slutligen samlas de sorterade elementen ihop på ett ordnat sätt.
Bucket Sortering Algoritm:
Skapa n tomma hinkar (eller listor) och gör följande för varje matriselement arr[i].
- Sätt in arr[i] i hink[n*array[i]]
- Sortera enskilda hinkar med hjälp av instickssortering.
- Sammanfoga alla sorterade hinkar.
Hur fungerar Bucket Sort?
För att tillämpa hinksortering på inmatningsmatrisen [0,78, 0,17, 0,39, 0,26, 0,72, 0,94, 0,21, 0,12, 0,23, 0,68] , följer vi dessa steg:
Steg 1: Skapa en array av storlek 10, där varje plats representerar en hink.
bash sammanfoga strängar
Skapa hinkar för sortering
Steg 2: Infoga element i hinkarna från inmatningsmatrisen baserat på deras räckvidd.
Sätta in element i hinkarna:
- Ta varje element från inmatningsmatrisen.
- Multiplicera elementet med storleken på hinkmatrisen (10 i det här fallet). Till exempel, för element 0,23 får vi 0,23 * 10 = 2,3.
- Konvertera resultatet till ett heltal, vilket ger oss hinkindex. I det här fallet konverteras 2,3 till heltal 2.
- Sätt in elementet i hinken som motsvarar det beräknade indexet.
- Upprepa dessa steg för alla element i inmatningsmatrisen.
Infoga Array-element i respektive hinkar
Steg 3: Sortera elementen i varje hink. I det här exemplet använder vi quicksort (eller någon stabil sorteringsalgoritm) för att sortera elementen inom varje hink.
Sortera elementen i varje hink:
vlc för att ladda ner youtube
- Använd en stabil sorteringsalgoritm (t.ex. Bubblesortering, Merge Sortering) för att sortera elementen inom varje hink.
- Elementen i varje hink är nu sorterade.
Sortering av enskild hink
Steg 4: Samla elementen från varje hink och sätt tillbaka dem i den ursprungliga arrayen.
Samla in element från varje hink:
konvertera byte array till sträng
- Iterera genom varje hink i ordning.
- Sätt in varje enskilt element från hinken i den ursprungliga arrayen.
- När ett element har kopierats tas det bort från hinken.
- Upprepa denna process för alla hinkar tills alla element har samlats.
Infoga hinkar i stigande ordning i den resulterande arrayen
Steg 5: Den ursprungliga arrayen innehåller nu de sorterade elementen.
Den slutliga sorterade matrisen som använder hinksortering för den givna ingången är [0,12, 0,17, 0,21, 0,23, 0,26, 0,39, 0,68, 0,72, 0,78, 0,94].
fotnoter markdown
Returnera den sorterade arrayen
Implementering av Bucket Sort Algorithm:
Nedan är implementeringen för Bucket Sort:
C++ #include #include using namespace std; // Insertion sort function to sort individual buckets void insertionSort(vector& hink) { för (int i = 1; i< bucket.size(); ++i) { float key = bucket[i]; int j = i - 1; while (j>= 0 && hink[j]> nyckel) { hink[j + 1] = hink[j]; j--; } hink[j + 1] = nyckel; } } // Funktion för att sortera arr[] av storlek n med bucket sort void bucketSort(float arr[], int n) { // 1) Skapa n tomma hinkar vektorb[n]; // 2) Placera arrayelement i olika hinkar för (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(Listhink) { för (int i = 1; i< bucket.size(); ++i) { float key = bucket.get(i); int j = i - 1; while (j>= 0 && bucket.get(j)> nyckel) { bucket.set(j + 1, bucket.get(j)); j--; } bucket.set(j + 1, nyckel); } } // Funktion för att sortera arr[] av storlek n med bucket sort public static void bucketSort(float[] arr) { int n = arr.length; // 1) Skapa n tomma buckets List[] hinkar = ny ArrayList[n]; för (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 + ' '); } } }> Pytonorm def insertion_sort(bucket): for i in range(1, len(bucket)): key = bucket[i] j = i - 1 while j>= 0 och hink[j]> nyckel: hink[j + 1] = hink[j] j -= 1 hink[j + 1] = nyckel def bucket_sort(arr): n = len(arr) hinkar = [[] för _ i intervall(n)] # Sätt arrayelement i olika hinkar för num i arr: bi = int(n * num) hinkar[bi].append(num) # Sortera enskilda hinkar med hjälp av insättningssortering för hink i hinkar: insertion_sort (hink) # Sammanfoga alla hinkar till arr[] index = 0 för hink i hinkar: för num i hink: arr[index] = num index += 1 arr = [0,897, 0,565, 0,656, 0,1234, 0,6345, 40 sort.] (arr) print('Sorterad array är:') print(' '.join(map(str, arr)))> C# using System; using System.Collections.Generic; class Program { // Insertion sort function to sort individual buckets static void InsertionSort(Listhink) { för (int i = 1; i< bucket.Count; ++i) { float key = bucket[i]; int j = i - 1; while (j>= 0 && hink[j]> nyckel) { hink[j + 1] = hink[j]; j--; } hink[j + 1] = nyckel; } } // Funktion för att sortera arr[] av storlek n med bucket sort static void BucketSort(float[] arr) { int n = arr.Length; // 1) Skapa n tomma buckets List[] hinkar = ny lista[n]; för (int i = 0; i< n; i++) { buckets[i] = new List(); } // 2) Placera arrayelement i olika hinkar för (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 && hink[j]> nyckel) { hink[j + 1] = hink[j]; j--; } hink[j + 1] = nyckel; } } funktion bucketSort(arr) { låt n = arr.length; let buckets = Array.from({längd: n}, () => []); // Placera arrayelement i olika hinkar för (låt 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(' '));> Produktion
Sorted array is 0.1234 0.3434 0.565 0.656 0.665 0.897>
Komplexitetsanalys av Bucket Sort Algorithm:
Tidskomplexitet: På2),
- Om vi antar att insättning i en hink tar O(1)-tid tar steg 1 och 2 i ovanstående algoritm helt klart O(n)-tid.
- O(1) är lätt möjligt om vi använder en länkad lista för att representera en hink.
- Steg 4 tar också O(n) tid eftersom det kommer att finnas n objekt i alla hinkar.
- Huvudsteget att analysera är steg 3. Detta steg tar också O(n) tid i genomsnitt om alla tal är jämnt fördelade.
Hjälputrymme: O(n+k)