Сортиране на блокове
Блоковото сортиране е алгоритъм за сортиране (в този случай масив от цели числа), при който елементите на масива се разпределят в отделни блокове. В тези блокове те са разположени така, че всички елементи във всеки следващ блок по ред да са по-големи или по-малки от тези в предишния блок. След това данните в тези блокове се сортират и отново се поставят в оригиналния масив.
Блоковото сортиране изисква едномерен масив от положителни цели числа, които да бъдат сортирани, и двумерен масив от цели числа с низове, индексирани от 0 до n - 1, където n е броят на стойностите в масива, които трябва да бъдат сортирани. Всеки ред от двумерен масив се третира като блок.
Следното е C++ програма, която реализира блоково сортиране на масив. Помислете за работата на програмата точка по точка:
- Поставяме всяка стойност на едномерен масив в ред на блоков масив въз основа на стойността на първия му бит. Например, 97 се поставя на ред 7, 3 се поставя на ред 3, а 100 се поставя на ред 0. Това се нарича „пропускане на разпространение“.
- Преминаваме през блоковия масив ред по ред и копираме стойностите обратно в масива. Това се нарича "събирателен проход". Новият ред на предишните стойности ще бъде 100, 3 и 97.
- Повтаряме този процес за всяка следваща цифра (десетки, стотици, хиляди и т.н.).
При второто преминаване 100 ще бъде поставено на ред 0, 3 ще бъде поставено на ред 0 (тъй като 3 няма цифра десетици), а 97 ще бъде поставено на ред 9. При третото преминаване 100 ще бъде поставено на ред 1, 3 ще бъде поставено на ред 0, а 97 ще бъде поставено на ред 0 след числото 3. След последното преминаване на събиране оригиналният масив ще бъде сортиран.