Садржај

• Упоредни графикон
• Дефиниција Куицк Сорт
• Дефиниција сортирања спајања
• Закључак

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

Обе технике сортирања, брзо сортирање и спајање сортиране су на методи раздвајања и освајања у којој се скуп елемената дели и затим комбинује након преуређења. Брза врста обично захтева више поређења од спајања за сортирање великог броја елемената.

1. 1. Упоредни графикон
   2. Дефиниција
   3. Кључне разлике
   4. Закључак

Упоредни графикон

Основе за поређење	Брза врста	Сортирање спајањем
Подјела елемената у низу	Дељење листе елемената није нужно подељено на половину.	Низ је увек подељен на половину (н / 2).
Најгора сложеност случаја	На2)	О (н лог н)
Одлично ради	Мањи низ	Добро функционише у било којој врсти низа.
Брзина	Бржи од осталих алгоритама за сортирање малих скупова података.	Доследна брзина у свим врстама података.
Додатни захтеви за складишни простор	Мање	Више
Ефикасност	Неефикасно за веће низове.	Ефикаснији.
Метода сортирања	Интерни	Спољашњи

Дефиниција Куицк Сорт

Брза врста је раширени алгоритам сортирања јер је брз за кратке низове. Скуп елемената је више пута подељен на делове док их није могуће даље поделити. Брза сорта је такође позната као врста размене партиција. За партиционирање елемената користи кључни елемент (познат као вртиште). Једна партиција садржи оне елементе који су мањи од кључног елемента. Друга партиција садржи оне елементе који су већи од кључног елемента. Елементи су сортирани рекурзивно.

Претпоставимо да је А низ А, А, А, …… .., А од н броја који се морају сортирати. Алгоритам за брзо сортирање састојао се од следећих корака.

1. Први елемент или било који случајни елемент изабран као кључ, претпоставимо да је кључ = А (1).
2. Показивач „низак“ поставља се на други, а показивач „горе“ је позициониран на последњи елемент матрице, тј. Низак = 2 и горе = н;
3. Доследно, увећајте „ниски“ показивач за једну позицију до (А> тастер).
4. Константно, усмјерите показивач "горе" за један положај до (А <= тастер).
5. Ако је горе већи од ниског, размена А са А.
6. Понављајте кораке 3,4 и 5 док услов из корака 5 не успије (тј. Горе <= низак), а затим размијените А с типком.
7. Ако су елементи лијеви од кључа мањи од кључа, а елементи десно од кључа, већи су од кључа, тада је низ подијељен на два подреда.
8. Горња процедура се више пута примењује на подраслове све док се целокупни низ не сортира.

   

   
   

Предности и мане

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

Дефиниција сортирања спајања

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

Нека је А низ низа елемената који ће се сортирати А, А, ………, А. Разврставање спајања прати дане кораке.

1. Подијелите низ А на приближно н / 2 сортирано под-низу по 2, што значи да се елементи у (А, А), (А, А), (А, А), (А, А) подрачуналу морају бити у сортираном редоследу.
2. Комбинујте сваки пар парова да бисте добили листу сортираних подрачуна величине 4; елементи у подраслима су такође поредани редоследом, (А, А, А, А), ……, (А, А, А, А), ……., (А, А, А, А).
3. Корак 2 се опетовано изводи све док не постоји само један сортирани низ величине н.

   

Предности и мане

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

1. Код сортирања спајања низ се мора раставити на само две половине (тј. Н / 2). За разлику од тога, у брзом сортирању, нема присиле да се листа подели на једнаке елементе.
2. Најгора сложеност брзог сортирања је О (н²) јер је у најгорем стању потребно много више поређења. Супротно томе, врста спајања имају исте најгоре случајеве и просечне сложености случаја, то јест О (н лог н).
3. Разврставање врста спајања може добро функционирати на било којој врсти података, било да је велика или мала. Супротно томе, брза врста не може добро функционирати са великим скуповима података.
4. Брзо сортирање је брже од спајања сортирања у неким случајевима, попут за мале скупове података.
5. Спајање сортирања захтијева додатни меморијски простор за спремање помоћних низова. С друге стране, за брзо сортирање није потребно много простора за додатно складиштење.
6. Разврставање спајања је ефикасније од брзог сортирања.
7. Брза врста је интерна метода сортирања где се подаци које треба сортирати подешавају у главној меморији. Супротно томе, врста спајања је метода екстерног сортирања у којој се подаци који ће се сортирати не могу истовремено сместити у меморију, а неки морају чувати у помоћној меморији.

Закључак

Брза врста је бржих случајева, али је неефикасна у неким ситуацијама и такође обавља пуно поређења у поређењу са спајањем. Иако је за разврставање потребно мање упоређивања, за складиштење додатног низа потребан је додатни меморијски простор од 0 (н), док брзом разврставању треба простор од О (лог н).