Преглед садржаја
- Увод
- Шта је сортирање спајањем у Ц++?
- Приступ завади па владај
- Алгоритам за сортирање спајањем
- Имплементација сортирања спајањем у Ц++
- Закључак
1. Представљање
Алгоритми за сортирање у рачунарству се користе за сређивање података у растућем или опадајућем редоследу. Постоји више алгоритама за сортирање са различитим својствима. Сортирање спајањем је једна од метода у Ц++ која може сортирати низове.
2. Шта је сортирање спајањем у Ц++
Сортирање спајањем користи технику завади па владај која може да организује елементе низа. Такође може сортирати листу елемената у Ц++. Он дели унос на две половине, сортира сваку половину независно, а затим их спаја у исправном редоследу.
3. Приступ завади па владај
Алгоритам за сортирање примењује стратегију завади и владај, која подразумева партиционисање улазног низа на мање поднизе, њихово решавање одвојено, а затим спајање резултата да би се произвео сортирани излаз. У случају сортирања спајањем, низ се рекурзивно дели на две половине све док у свакој половини не остане само један елемент.
4. Алгоритам за сортирање спајањем
Алгоритам сортирања спајањем се састоји од два главна корака: подела и спајање. Кораци су следећи:
4.1 Подели
Алгоритам сортирања спајањем прати стратегију завади па владај за сортирање елемената у низу.
- Први корак у алгоритму ће проверити елементе низа. Ако садржи један елемент, онда се већ сматра сортираним, а алгоритам ће вратити исти низ без икаквих промена.
- Ако низ садржи више од једног елемента, алгоритам наставља да га дели на две половине: леву и десну половину.
- Алгоритам за сортирање спајањем се затим примењује рекурзивно на леву и десну половину низа, ефективно их дели на мање поднизе и сортира их појединачно.
- Овај рекурзивни процес се наставља све док поднизови не садрже само по један елемент (као у кораку 1), у ком тренутку се могу спојити да би се произвео коначни, сортирани излазни низ.
4.2 Спајање
Сада ћемо видети кораке за спајање низова:
- Први корак за алгоритам сортирања спајањем укључује креирање празног низа.
- Алгоритам затим наставља да упоређује прве елементе леве и десне половине улазног низа.
- Мањи од два елемента се додаје новом низу, а затим уклања из одговарајуће половине улазног низа.
- Кораци 2-3 се затим понављају док се једна од половина не испразни.
- Сви преостали елементи у непразној половини се затим додају у нови низ.
- Добијени низ је сада потпуно сортиран и представља коначни излаз алгоритма сортирања спајањем.
5. Имплементација сортирања спајањем у Ц++
Да би се имплементирало сортирање спајањем у Ц++, користе се две различите методе. Временска сложеност обе методе је еквивалентна, али се њихова употреба привремених поднизова разликује.
Први метод за сортирање спајањем у Ц++ користи два привремена подниза, док други користи само један. Вреди напоменути да је укупна величина два привремена подниза у првој методи једнака величини оригиналног низа у другој методи, тако да комплексност простора остаје константна.
Метод 1 – Коришћење два Темп подниза
Ево примера програма за сортирање спајањем у Ц++ користећи метод 1, који користи два привремена подниза:
#инцлуде <иостреам>користећи простор имена стд ;
празнина спојити ( инт арр [ ] , инт л , инт м , инт р )
{
инт н1 = м - л + 1 ;
инт н2 = р - м ;
инт Л [ н1 ] , Р [ н2 ] ;
за ( инт и = 0 ; и < н1 ; и ++ )
Л [ и ] = арр [ л + и ] ;
за ( инт ј = 0 ; ј < н2 ; ј ++ )
Р [ ј ] = арр [ м + 1 + ј ] ;
инт и = 0 , ј = 0 , к = л ;
док ( и < н1 && ј < н2 ) {
ако ( Л [ и ] <= Р [ ј ] ) {
арр [ к ] = Л [ и ] ;
и ++;
}
друго {
арр [ к ] = Р [ ј ] ;
ј ++;
}
к ++;
}
док ( и < н1 ) {
арр [ к ] = Л [ и ] ;
и ++;
к ++;
}
док ( ј < н2 ) {
арр [ к ] = Р [ ј ] ;
ј ++;
к ++;
}
}
празнина сортирање спајањем ( инт арр [ ] , инт л , инт р )
{
ако ( л < р ) {
инт м = л + ( р - л ) / 2 ;
сортирање спајањем ( арр , л , м ) ;
сортирање спајањем ( арр , м + 1 , р ) ;
спојити ( арр , л , м , р ) ;
}
}
инт главни ( )
{
инт арр [ ] = { 12 , Једанаест , 13 , 5 , 6 , 7 } ;
инт арр_сизе = величина ( арр ) / величина ( арр [ 0 ] ) ;
цоут << „Дати низ је \н ' ;
за ( инт и = 0 ; и < арр_сизе ; и ++ )
цоут << арр [ и ] << ' ' ;
сортирање спајањем ( арр , 0 , арр_сизе - 1 ) ;
цоут << ' \н Сортирани низ је \н ' ;
за ( инт и = 0 ; и < арр_сизе ; и ++ )
цоут << арр [ и ] << ' ' ;
повратак 0 ;
}
У овом програму, функција спајања узима три аргумента арр, л и р, који представљају низ који треба сортирати и показује индексе подниза који треба спојити. Функција прво проналази величине два подниза која ће се спојити, а затим креира два привремена подниза Л и Р за чување елемената ових подниза. Затим упоређује елементе у Л и Р и спаја их у оригинални низ под називом арр у растућем редоследу.
Технику завади и владај користи функција мергеСорт да би се низ рекурзивно поделио на две половине све док у поднизу не остане само један елемент. Затим спаја два подниза у сортирани подниз. Функција наставља да спаја поднизе осим ако не сортира цео низ.
У главној функцији дефинишемо низ арр са 6 елемената и позивамо функцију мергеСорт да га сортирамо. На крају кода се штампа сортирани низ.
Метод 2 – Коришћење једног Темп подниза
Ево примера програма за сортирање спајањем у Ц++ користећи метод 2, који користи један привремени подниз:
#инцлуде <иостреам>користећи простор имена стд ;
празнина спојити ( инт арр [ ] , инт л , инт м , инт р )
{
инт и , ј , к ;
инт н1 = м - л + 1 ;
инт н2 = р - м ;
// Креирање привремених поднизова
инт Л [ н1 ] , Р [ н2 ] ;
// Копирај податке у поднисе
за ( и = 0 ; и < н1 ; и ++ )
Л [ и ] = арр [ л + и ] ;
за ( ј = 0 ; ј < н2 ; ј ++ )
Р [ ј ] = арр [ м + 1 + ј ] ;
// Спајање привремених поднизова назад у оригинални низ
и = 0 ;
ј = 0 ;
к = л ;
док ( и < н1 && ј < н2 ) {
ако ( Л [ и ] <= Р [ ј ] ) {
арр [ к ] = Л [ и ] ;
и ++;
}
друго {
арр [ к ] = Р [ ј ] ;
ј ++;
}
к ++;
}
// Копирај преостале елементе Л[]
док ( и < н1 ) {
арр [ к ] = Л [ и ] ;
и ++;
к ++;
}
// Копирај преостале елементе Р[]
док ( ј < н2 ) {
арр [ к ] = Р [ ј ] ;
ј ++;
к ++;
}
}
празнина сортирање спајањем ( инт арр [ ] , инт л , инт р )
{
ако ( л < р ) {
инт м = л + ( р - л ) / 2 ;
// Сортирај леву и десну половину рекурзивно
сортирање спајањем ( арр , л , м ) ;
сортирање спајањем ( арр , м + 1 , р ) ;
// Споји две сортиране половине
спојити ( арр , л , м , р ) ;
}
}
инт главни ( )
{
инт арр [ ] = { 12 , Једанаест , 13 , 5 , 6 , 7 } ;
инт арр_сизе = величина ( арр ) / величина ( арр [ 0 ] ) ;
цоут << „Дати низ је \н ' ;
за ( инт и = 0 ; и < арр_сизе ; и ++ )
цоут << арр [ и ] << ' ' ;
сортирање спајањем ( арр , 0 , арр_сизе - 1 ) ;
цоут << ' \н Сортирани низ је \н ' ;
за ( инт и = 0 ; и < арр_сизе ; и ++ )
цоут << арр [ и ] << ' ' ;
повратак 0 ;
}
Овај програм је попут претходног, али уместо да користи два привремена подниза Л и Р, користи једну привремену поднизу темп. Функција спајања ради на исти начин као и раније, али уместо да копира податке у Л и Р, она их копира у темп. Затим спаја елементе привременог низа назад у арр што је оригинални низ.
Функција мергеСорт је иста као и раније, осим што користи темп уместо Л и Р за чување привременог подниза.
У главној функцији дефинишемо низ арр са 6 елемената и позивамо функцију мергеСорт да га сортирамо. Извршење кода се завршава штампањем сортираног низа на екрану.
Закључак
Сортирање спајањем је алгоритам који сортира елементе низа и користи технику завади па владај и прави поређења између елемената. Сортирање спајањем у Ц++ има временску сложеност од О(н лог н) и посебно је ефикасно за сортирање великих низова. Иако захтева додатну меморију за складиштење спојених поднизова, његова стабилност га чини популарним избором за сортирање.