Мени

Сортирање љуске на Ц ++ са примерима

shell sort c with examples

Испробајте Наш Инструмент За Елиминисање Проблема

Техника сортирања шкољке на језику Ц ++: Комплетан преглед.

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

У сортирању љуске, листа се сортира рашчлањивањем на већи број мањих подлиста. Није неопходно да листе морају да буду са суседним елементима. Уместо тога, техника сортирања љуске користи прираштај и, који се такође назива „јаз“ и користи га за стварање листе елемената који су „и“ елементи одвојени.

=> Погледајте овде како бисте истражили целу листу водича за Ц ++.

најбољи софтвер за видео конвертере за Виндовс

Схелл Сорт

Шта ћете научити:

Општи алгоритам

Општи алгоритам за сортирање љуске дат је у наставку.

сортирај шкољку (А, Н)
где је А - листа за сортирање; Н - величина_размака

сет гап_сизе = Н, флаг = 1
док је величина_размака> 1 или заставица = 1, поновите
започети
постављена застава = 0
постави величину_празине = (величина_размака + 1) / 2
крај
за и = 0 до и<(N-gap_size) repeat
започети
ако је А (и + величина_размака)> А (и)
заменити А (и + величина_размака), А (и)
постављена застава = 0
крај
крај

Тако смо у горњем алгоритму прво поставили Н, што је празнина за сортирање низа А помоћу сортирања љуске. У следећем кораку делимо низ на поднизове помоћу празнине. Затим у следећем кораку сортирамо сваки од под-низова тако да ћемо на крају петље добити сортирани низ.

Даље, размотримо детаљан пример да бисмо боље разумели сортирање љуске помоћу сликовног приказа.

Илустрација

Покажимо илустрацију шкољке на примеру.

Размотрите следећи низ од 10 елемената.

низ од 10 елемената

Ако пружимо размак од 3, тада ћемо имати следеће под-листе са сваким елементом који је одвојен од 3 елемента. Затим сортирамо ове три подлисте.

подлисте

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

сортиране под-листе и резултујућа листа

Горњи низ који смо добили након обједињавања разврстаних под низова је скоро сортиран. Сада можемо извршити сортирање уметања на овој листи и сортирати читав низ. Овај последњи корак је приказан испод за вашу референцу.

Завршни корак

Као што се горе види, након извођења сортирања љуске и обједињавања сортираних подлиста, била су нам потребна само три потеза да бисмо листу у потпуности сортирали. Тако можемо видети да можемо знатно смањити број корака потребних за сортирање низа.

Избор прираста за стварање под-листа је јединствена карактеристика сортирања љуске.

Пример Ц ++

Погледајмо имплементацију сортирања љуске у Ц ++ испод.

#include using namespace std; // shellsort implementation int shellSort(int arr(), int N) { for (int gap = N/2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } int main() { int arr() = {45,23,53,43,18,24,8,95,101}, i; //Calculate size of array int N = sizeof(arr)/sizeof(arr(0)); cout << 'Array to be sorted: '; for (int i=0; i

Излаз:

Низ за сортирање:

45 23 53 43 18 24 8 95 101

Низ након сортирања љуске:

8 18 23 24 43 45 53 95 101

Користили смо исти списак који смо користили на илустрацији и можемо видети да смо у почетку креирали две под-листе, а затим додатно смањили јаз. Једном када се под-листе креирају према наведеном размаку, сортирамо сваку од под-листа. Након што су све под-листе сортиране, добијамо готово сортирану листу. Сада се ова листа може сортирати помоћу основне сорте за уметање која ће требати врло мало потеза.

Даље, применимо сортирање љуске помоћу Јава језика.

Пример Јаве

// Java class for ShellSort class ShellSort { //function to sort the array using shell sort int sort(int arr()) { int N = arr.length; // Start with a big gap, then narrow the gap for (int gap = N/2; gap > 0; gap /= 2) { //sort sub lists created by applying gap for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } } class Main{ public static void main(String args()) { int arr() = {45,23,53,43,18,24,8,95,101}; int N = arr.length; System.out.println('Array to be sorted: '); for (int i=0; i

Излаз:

Низ за сортирање:

45 23 53 43 18 24 8 95 101

Низ након сортирања љуске:

8 18 23 24 43 45 53 95 101

Применили смо исту логику за сортирање љуске и у Ц ++ и у Јава програмима. Стога, како је горе објашњено у програму Јава, прво делимо низ на поднизове, а затим их сортирамо да бисмо добили комплетни сортирани низ.

Закључак

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

Док сортирање уметања дјелује тако што повећава своје елементе за 1, сортирање љуске користи параметар „јаз“ да подијели низ на поднизове чији су елементи раздвојени. Тада можемо сортирати појединачну листу помоћу сортирања уметањем да бисмо добили комплетни сортирани низ.

Сортирање љуске изводи се брже од сортирања уметања и узима мање потеза за сортирање низа у поређењу са сортирањем уметања. Наш предстојећи водич ће истражити све о техници сортирања гомиле за сортирање структура података.

=> Посетите овде да бисте научили Ц ++ из огреботина.

Препоручено читање

^