shell sort c with examples
Техника за сортиране на черупки в C ++: Пълен преглед.
Сортирането на черупки често се нарича подобрение спрямо сортирането с вмъкване. При сортиране при вмъкване вземаме стъпки по 1, за да сравним елементите и да ги поставим в правилното им положение.
При сортиране на черупки списъкът се сортира, като се разделя на няколко по-малки подлиста. Не е необходимо списъците да са със съседни елементи. Вместо това техниката за сортиране на черупки използва инкремент i, който също се нарича „празнина“ и го използва за създаване на списък с елементи, които са „i“ елементи отделно.
=> Вижте тук, за да разгледате пълния списък с уроци за C ++.
конвертирате YouTube в wav файл безплатно
Какво ще научите:
Общ алгоритъм
Общият алгоритъм за сортиране на черупки е даден по-долу.
сортиране на черупки (A, N)
където A - списък за сортиране; N - размер на пропастта
задайте пропуск_размер = N, флаг = 1
докато gap_size> 1 или флаг = 1, повторете
започнете
задайте флаг = 0
задайте размери_размери = (размери_размери + 1) / 2
край
за i = 0 до i<(N-gap_size) repeat
започнете
ако A (i + размери_размери)> A (i)
суап A (i + пропуск_размер), A (i)
задайте флаг = 0
край
край
По този начин в горния алгоритъм първо задаваме N, което е празнината за сортиране на масива A, използвайки сортиране на черупката. В следващата стъпка разделяме масива на подмасиви, като използваме празнината. След това в следващата стъпка ние сортираме всеки от под-масивите, така че в края на цикъла ще получим сортиран масив.
След това нека разгледаме подробен пример, за да разберем по-добре сортирането на черупката, използвайки изобразително представяне.
Илюстрация
Нека илюстрираме сорта на Shell с пример.
Обмислете следния масив от 10 елемента.
Ако осигурим празнина от 3, тогава ще имаме следните под-списъци с всеки елемент, който е разделен на 3 елемента. След това сортираме тези три подлиста.
Сортираните под-списъци и полученият списък, който получаваме след комбиниране на трите сортирани под-списъка, са показани по-долу.
Горният масив, който получихме след обединяване на сортираните подмасиви, е почти сортиран. Сега можем да извършим сортиране на вмъкване в този списък и да сортираме целия масив. Тази последна стъпка е показана по-долу за справка.
Както се вижда по-горе, след извършване на сортиране на черупки и обединяване на сортираните подлисти, ние изисквахме само три хода, за да сортираме напълно списъка. По този начин можем да видим, че можем значително да намалим броя стъпки, необходими за сортиране на масива.
Изборът на стъпка за създаване на под-списъци е уникална характеристика на сортирането на черупката.
Пример за C ++
Нека видим изпълнението на сортирането на черупки в C ++ по-долу.
#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 език.
Пример за Java
// 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
Внедрихме една и съща логика за сортиране на черупки както в C ++, така и в Java програми. По този начин, както е обяснено по-горе в програмата Java, първо разделяме масива на подмасиви и след това ги сортираме, за да получим пълен сортиран масив.
Заключение
Сортирането на черупки е високоефективният алгоритъм, който се подобрява спрямо сортирането при вмъкване.
Докато сортирането при вмъкване работи чрез увеличаване на елементите му с 1, сортирането на черупката използва параметъра „gap“, за да раздели масива на подмасиви, чиито елементи са „gap“. След това можем да сортираме отделния списък, като използваме сортиране с вмъкване, за да получим пълния сортиран масив.
Сортирането на черупки се извършва по-бързо от сортирането с вмъкване и отнема по-малко движения, за да сортира масива в сравнение с сортирането с вмъкване. Нашият предстоящ урок ще разгледа всичко за техниката за сортиране на купчина за сортиране на структури от данни.
=> Посетете тук, за да научите C ++ от нулата.
Препоръчително четене
- Сортиране на избора в C ++ с примери
- Метод за сортиране на MongoDB () с примери
- Команда за сортиране на Unix със синтаксис, опции и примери
- Сортиране на балончета в C ++ с примери
- Сортиране по вмъкване в C ++ с примери
- Обединяване на сортиране в C ++ с примери
- Сортиране на купчини в C ++ с примери
- Бързо сортиране в C ++ с примери