Algoritam sortiranja segmenta

U ovom vodiču naučit ćete kako funkcionira sortiranje segmenata. Također ćete naći radne primjere sortiranja u skupinama u C, C ++, Java i Python.

Sortiranje prema kašikama tehnika je sortiranja koja razvrstava elemente tako da se elementi prvo podijele u nekoliko skupina koje se nazivaju kante . Elementi unutar svakog segmenta razvrstavaju se pomoću bilo kojeg odgovarajućeg algoritma za sortiranje ili rekurzivnim pozivanjem istog algoritma.

Stvoreno je nekoliko kanta. Svaka kanta ispunjena je određenim nizom elemenata. Elementi unutar sefa sortirani su pomoću bilo kojeg drugog algoritma. Konačno, elementi segmenta skupljaju se kako bi se dobio sortirani niz.

Proces sortiranja segmenata može se shvatiti kao pristup raspršivanju . Elementi se prvo rasipaju u kante, a zatim se elementi kante sortiraju. Napokon, elementi se sakupljaju redom.

Rad sortirane žlice

Kako sortiranje u kantama djeluje?

Pretpostavimo, ulazni niz je: Ulazni niz
Stvori niz veličine 10. Svaki utor ovog polja koristi se kao segment za spremanje elemenata. Niz u kojem je svaki položaj vjedro
Umetnite elemente u segmente iz niza. Elementi se umetnu prema rasponu kante.
U našem primjeru koda imamo segmente u rasponu od 0 do 1, 1 do 2, 2 do 3, … (n-1) do n.
Pretpostavimo da .23je uzet ulazni element . Množi se s size = 10(tj. .23*10=2.3). Zatim se pretvara u cijeli broj (tj. 2.3≈2). Konačno, .23 se umetne u kantu-2 . Umetanje elemenata u segmente iz polja
Slično tome, .25 se također ubacuje u isti segment. Svaki put se uzima podna vrijednost broja s pomičnom zarezom.
Ako za ulaz uzmemo cjelobrojne brojeve, moramo ga podijeliti s intervalom (ovdje 10) da bismo dobili najnižu vrijednost.
Slično tome, drugi su elementi umetnuti u odgovarajuće kante. Umetnite sve elemente u segmente iz niza
Elementi svakog segmenta razvrstavaju se pomoću bilo kojeg stabilnog algoritma za sortiranje. Ovdje smo koristili brzi sortiranje (ugrađena funkcija). Poredajte elemente u svakoj skupini
Elementi iz svake kante su prikupljeni.
To se postiže iteracijom kroz skupinu i umetanjem pojedinačnog elementa u izvorni niz u svakom ciklusu. Element iz segmenta briše se nakon kopiranja u izvorni niz. Skupite elemente iz svake kante

Algoritam sortiranja segmenta

 bucketSort () stvori N segmenata od kojih svaka može sadržavati raspon vrijednosti za sve segmente. inicijalizirati svaki segment sa 0 vrijednostima za sve segmente staviti elemente u segmente koji odgovaraju opsegu za sve segmente elementi za sortiranje u svakom segmentu prikupiti elemente iz svakog segmenta kraj kanteSort

Primjeri Pythona, Java i C / C ++

Python Java C C ++

 # Bucket Sort in Python def bucketSort(array): bucket = () # Create empty buckets for i in range(len(array)): bucket.append(()) # Insert elements into their respective buckets for j in array: index_b = int(10 * j) bucket(index_b).append(j) # Sort the elements of each bucket for i in range(len(array)): bucket(i) = sorted(bucket(i)) # Get the sorted elements k = 0 for i in range(len(array)): for j in range(len(bucket(i))): array(k) = bucket(i)(j) k += 1 return array array = (.42, .32, .33, .52, .37, .47, .51) print("Sorted Array in descending order is") print(bucketSort(array))

 // Bucket sort in Java import java.util.ArrayList; import java.util.Collections; public class BucketSort ( public void bucketSort(float() arr, int n) ( if (n <= 0) return; @SuppressWarnings("unchecked") ArrayList() bucket = new ArrayList(n); // Create empty buckets for (int i = 0; i < n; i++) bucket(i) = new ArrayList(); // Add elements into the buckets for (int i = 0; i < n; i++) ( int bucketIndex = (int) arr(i) * n; bucket(bucketIndex).add(arr(i)); ) // Sort the elements of each bucket for (int i = 0; i < n; i++) ( Collections.sort((bucket(i))); ) // Get the sorted array int index = 0; for (int i = 0; i < n; i++) ( for (int j = 0, size = bucket(i).size(); j < size; j++) ( arr(index++) = bucket(i).get(j); ) ) ) // Driver code public static void main(String() args) ( BucketSort b = new BucketSort(); float() arr = ( (float) 0.42, (float) 0.32, (float) 0.33, (float) 0.52, (float) 0.37, (float) 0.47, (float) 0.51 ); b.bucketSort(arr, 7); for (float i : arr) System.out.print(i + " "); ) )

 // Bucket sort in C #include #include #define NARRAY 7 // Array size #define NBUCKET 6 // Number of buckets #define INTERVAL 10 // Each bucket capacity struct Node ( int data; struct Node *next; ); void BucketSort(int arr()); struct Node *InsertionSort(struct Node *list); void print(int arr()); void printBuckets(struct Node *list); int getBucketIndex(int value); // Sorting function void BucketSort(int arr()) ( int i, j; struct Node **buckets; // Create buckets and allocate memory size buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET); // Initialize empty buckets for (i = 0; i < NBUCKET; ++i) ( buckets(i) = NULL; ) // Fill the buckets with respective elements for (i = 0; i data = arr(i); current->next = buckets(pos); buckets(pos) = current; ) // Print the buckets along with their elements for (i = 0; i < NBUCKET; i++) ( printf("Bucket(%d): ", i); printBuckets(buckets(i)); printf(""); ) // Sort the elements of each bucket for (i = 0; i < NBUCKET; ++i) ( buckets(i) = InsertionSort(buckets(i)); ) printf("-------------"); printf("Bucktets after sorting"); for (i = 0; i < NBUCKET; i++) ( printf("Bucket(%d): ", i); printBuckets(buckets(i)); printf(""); ) // Put sorted elements on arr for (j = 0, i = 0; i data; node = node->next; ) ) return; ) // Function to sort the elements of each bucket struct Node *InsertionSort(struct Node *list) ( struct Node *k, *nodeList; if (list == 0 || list->next == 0) ( return list; ) nodeList = list; k = list->next; nodeList->next = 0; while (k != 0) ( struct Node *ptr; if (nodeList->data> k->data) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = nodeList; nodeList = tmp; continue; ) for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) ( if (ptr->next->data> k->data) break; ) if (ptr->next != 0) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = ptr->next; ptr->next = tmp; continue; ) else ( ptr->next = k; k = k->next; ptr->next->next = 0; continue; ) ) return nodeList; ) int getBucketIndex(int value) ( return value / INTERVAL; ) void print(int ar()) ( int i; for (i = 0; i data); cur = cur->next; ) ) // Driver code int main(void) ( int array(NARRAY) = (42, 32, 33, 52, 37, 47, 51); printf("Initial array: "); print(array); printf("-------------"); BucketSort(array); printf("-------------"); printf("Sorted array: "); print(array); return 0; )

 // Bucket sort in C++ #include #include using namespace std; #define NARRAY 7 // Array size #define NBUCKET 6 // Number of buckets #define INTERVAL 10 // Each bucket capacity struct Node ( int data; struct Node *next; ); void BucketSort(int arr()); struct Node *InsertionSort(struct Node *list); void print(int arr()); void printBuckets(struct Node *list); int getBucketIndex(int value); // Sorting function void BucketSort(int arr()) ( int i, j; struct Node **buckets; // Create buckets and allocate memory size buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET); // Initialize empty buckets for (i = 0; i < NBUCKET; ++i) ( buckets(i) = NULL; ) // Fill the buckets with respective elements for (i = 0; i data = arr(i); current->next = buckets(pos); buckets(pos) = current; ) // Print the buckets along with their elements for (i = 0; i < NBUCKET; i++) ( cout << "Bucket(" << i << ") : "; printBuckets(buckets(i)); cout << endl; ) // Sort the elements of each bucket for (i = 0; i < NBUCKET; ++i) ( buckets(i) = InsertionSort(buckets(i)); ) cout << "-------------" << endl; cout << "Bucktets after sorted" << endl; for (i = 0; i < NBUCKET; i++) ( cout << "Bucket(" << i << ") : "; printBuckets(buckets(i)); cout << endl; ) // Put sorted elements on arr for (j = 0, i = 0; i data; node = node->next; ) ) for (i = 0; i next; free(tmp); ) ) free(buckets); return; ) // Function to sort the elements of each bucket struct Node *InsertionSort(struct Node *list) ( struct Node *k, *nodeList; if (list == 0 || list->next == 0) ( return list; ) nodeList = list; k = list->next; nodeList->next = 0; while (k != 0) ( struct Node *ptr; if (nodeList->data> k->data) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = nodeList; nodeList = tmp; continue; ) for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) ( if (ptr->next->data> k->data) break; ) if (ptr->next != 0) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = ptr->next; ptr->next = tmp; continue; ) else ( ptr->next = k; k = k->next; ptr->next->next = 0; continue; ) ) return nodeList; ) int getBucketIndex(int value) ( return value / INTERVAL; ) // Print buckets void print(int ar()) ( int i; for (i = 0; i < NARRAY; ++i) ( cout << setw(3) << ar(i); ) cout << endl; ) void printBuckets(struct Node *list) ( struct Node *cur = list; while (cur) ( cout << setw(3)  next; ) ) // Driver code int main(void) ( int array(NARRAY) = (42, 32, 33, 52, 37, 47, 51); cout << "Initial array: " << endl; print(array); cout << "-------------" << endl; BucketSort(array); cout << "-------------" << endl; cout << "Sorted array: " << endl; print(array); )

Složenost

Najgora složenost slučaja: Kada u nizu postoje elementi bliskog dometa, oni će vjerojatno biti smješteni u istu kantu. To može dovesti do toga da neke skupine imaju veći broj elemenata od drugih. Zbog toga složenost ovisi o algoritmu za sortiranje koji se koristi za sortiranje elemenata segmenta. Složenost postaje još gora kada su elementi obrnutim redoslijedom. Ako se sortiranje umetanjem koristi za sortiranje elemenata segmenta, tada postaje složenost vremena .O(n²)

O(n²)
Složenost najboljeg slučaja: O(n+k)
Događa se kada su elementi jednoliko raspoređeni u skupinama s gotovo jednakim brojem elemenata u svakoj skupini.
Složenost postaje još bolja ako su elementi unutar žlica već sortirani.
Ako se sortiranje umetanjem koristi za sortiranje elemenata segmenta, tada će ukupna složenost u najboljem slučaju biti linearna, tj. O(n+k). O(n)je složenost izrade segmenata i O(k)složenost sortiranja elemenata segmenta pomoću algoritama koji u najboljem slučaju imaju linearnu vremensku složenost.
Prosječna složenost slučaja: O(n)
Događa se kada se elementi nasumično rasporede u polju. Čak i ako se elementi ne distribuiraju jednoliko, sortiranje segmenata radi u linearnom vremenu. To vrijedi sve dok zbroj kvadrata veličina kante nije linearan u ukupnom broju elemenata.