Алгоритам сортирања сегмента

У овом упутству ћете научити како функционише сортирање сегмената. Такође, наћи ћете радне примере сортирања сегмената у Ц, Ц ++, Јава и Питхон.

Сортирање кашике је техника сортирања која разврстава елементе тако што се елементи прво поделе у неколико група које се називају сегменти . Елементи унутар сваког сегмента разврставају се помоћу било ког од одговарајућих алгоритама за сортирање или рекурзивним позивањем истог алгоритма.

Створено је неколико кашика. Свака канта је испуњена одређеним опсегом елемената. Елементи унутар сефа сортирани су помоћу било ког другог алгоритма. Коначно, елементи сегмента се сакупљају да би се добио сортирани низ.

Процес сортирања сегмента може се схватити као приступ распршивању . Елементи се прво расипају у канте, а затим се елементи канте сортирају. Коначно, елементи се сакупљају редом.

Рад сортиране кашике

Како функционише сортирање сегмената?

Претпоставимо да је улазни низ: Улазни низ
Створимо низ величине 10. Сваки слот овог низа користи се као сегмент за чување елемената. Низ у којем је свака позиција сеф
Уметните елементе у сегменте из низа. Елементи се убацују према опсегу кашике.
У нашем примеру кода имамо сегменте сваки од опсега од 0 до 1, 1 до 2, 2 до 3, … (н-1) до н.
Претпоставимо да .23је узет улазни елемент . Множи се са size = 10(тј. .23*10=2.3). Затим се претвара у цео број (тј. 2.3≈2). Коначно, .23 се убацује у канту-2 . Уметање елемената у сегменте из низа
Слично томе .25 се такође убацује у исти сегмент. Сваки пут се узима подна вредност броја са покретном зарезом.
Ако за унос узмемо целобројне бројеве, морамо га поделити са интервалом (овде 10) да бисмо добили вредност пода.
Слично томе, други елементи се убацују у њихове одговарајуће канте. Уметните све елементе у сегменте из низа
Елементи сваког сегмента сортирани су помоћу било ког стабилног алгоритма за сортирање. Овде смо користили брзи сортирање (уграђена функција). Поредајте елементе у сваком сегменту
Елементи из сваке канте су сакупљени.
То се постиже итерацијом кроз сегмент и уметањем појединачног елемента у оригинални низ у сваком циклусу. Елемент из сегмента брише се након што се копира у оригинални низ. Прикупите елементе из сваке канте

Алгоритам сортирања сегмента

 буцкетСорт () креира Н сегмената од којих свака може да садржи опсег вредности за све сегменте. иницијализује сваки сегмент са 0 вредности за сва сегмента ставља елементе у сегменте који одговарају опсегу за све сегменте елементи за сортирање у сваком сегменту прикупљају елементе из сваког сегмента крај буцкетСорт

Примери за Питхон, Јава и Ц / Ц ++

Питхон Јава Ц Ц ++

 # 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); )

Сложеност

Најгора сложеност случаја: Када у низу постоје елементи блиског домета, они ће вероватно бити смештени у исти сегмент. То може довести до тога да неке сегменте имају већи број елемената од других. Због тога сложеност зависи од алгоритма за сортирање који се користи за сортирање елемената сегмента. Сложеност постаје још гора када су елементи обрнутим редоследом. Ако се сортирање уметањем користи за сортирање елемената сегмента, тада временска сложеност постаје сложенија .O(n²)

O(n²)
Сложеност најбољег случаја: O(n+k)
До тога долази када се елементи равномерно распореде у сегменте са скоро једнаким бројем елемената у сваком сегменту.
Сложеност постаје још боља ако су елементи унутар кашика већ сортирани.
Ако се сортирање уметањем користи за сортирање елемената сегмента, тада ће укупна сложеност у најбољем случају бити линеарна, тј. O(n+k). O(n)је сложеност израде сегмената и O(k)сложеност сортирања елемената сегмента помоћу алгоритама који у најбољем случају имају линеарну временску сложеност.
Просечна сложеност случаја: O(n)
Појављује се када се елементи насумично распореде у низу. Чак и ако се елементи не дистрибуирају једнолико, сортирање сегмента ради у линеарном времену. Важи све док зброј квадрата величина кашике не буде линеаран у укупном броју елемената.