Увод у алгоритам сортирања стапања

Сортирање обједињавањем је алгоритам за сортирање заснован на техници „подели и освоји“. То је један од најефикаснијих алгоритама за сортирање.

У овом чланку ћете сазнати о раду алгоритма за сортирање стапања, алгоритму за сортирање стапања, његовом сложеност времена и простора и његова примена у различитим програмским језицима попут Ц ++, Питхон и ЈаваСцрипт.

Како функционише алгоритам сортирања стапања?

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

Овај концепт се може ефикасније објаснити уз помоћ примера. Размотрите несортирани низ са следећим елементима: {16, 12, 15, 13, 19, 17, 11, 18}.

Овде алгоритам сортирања спајања дели низ на две половине, позива се на две половине, а затим спаја две сортиране половине.

Споји алгоритам сортирања

Испод је алгоритам сортирања спајања:

МергеСорт (арр [], лефтИндек, ригхтИндек)





instagram viewer


ако лефтИндек> = ригхтИндек
повратак
иначе
Пронађите средњи индекс који дели низ на две половине: 
миддлеИндек = лефтИндек + (ригхтИндек-лефтИндек) / 2
Позовите мергеСорт () за прво полувреме: 
Позовите мергеСорт (арр, лефтИндек, миддлеИндек)
Позовите мергеСорт () за друго полувреме:
Позовите мергеСорт (арр, миддлеИндек + 1, ригхтИндек)
Спојите две половине сортиране у кораку 2 и 3:
Спајање позива (арр, лефтИндек, миддлеИндек, ригхтИндек)

Повезан: Шта је рекурзија и како је користите?

Сложеност времена и простора алгоритма сортирања стапања

Алгоритам сортирања спајања може се изразити у облику следеће релације понављања:

Т (н) = 2Т (н / 2) + О (н)

Након решавања ове релације понављања помоћу мастер теореме или методе стабла понављања, добићете решење као О (н логн). Дакле, временска сложеност алгоритма за сортирање спајања је О (н пријава).

Најбоља временска сложеност врсте спајања: О (н пријава)

Просечна временска сложеност врсте спајања: О (н пријава)

Најгора временска сложеност врсте спајања: О (н пријава)

Повезан: Шта је Биг-О нотација?

Комплексност помоћног простора алгоритма за сортирање спајања је На) као што н потребан је помоћни простор у имплементацији сортирања спајања.

Ц ++ Имплементација алгоритма сортирања стапања

Испод је примена Ц ++ алгоритма за сортирање спајања:

// Ц ++ имплементација
// спајање алгоритма сортирања
#инцлуде 
коришћење простора имена стд;
// Ова функција спаја два подниза арр []
// Леви подниз: арр [лефтИндек..миддлеИндек]
// Десни подниз: арр [миддлеИндек + 1..ригхтИндек]
спајање празнина (инт арр [], инт лефтИндек, инт миддлеИндек, инт ригхтИндек)
{
инт лефтСубарраиСизе = миддлеИндек - лефтИндек + 1;
инт ригхтСубарраиСизе = ригхтИндек - миддлеИндек;
// Стварање привремених низова
инт Л [лефтСубарраиСизе], Р [ригхтСубарраиСизе];
// Копирање података у привремене низове Л [] и Р []
за (инт и = 0; и Л [и] = арр [лефтИндек + и];
за (инт ј = 0; ј Р [ј] = арр [миддлеИндек + 1 + ј];
// Спајање привремених низова назад у арр [лефтИндек..ригхтИндек]
// Иницијални индекс левог подниза
инт и = 0;
// Иницијални индекс десног низа
инт ј = 0;
// Иницијални индекс спојеног низа
инт к = лефтИндек;
док (и {
ако (Л [и] <= Р [ј])
{
арр [к] = Л [и];
и ++;
}
иначе
{
арр [к] = Р [ј];
ј ++;
}
к ++;
}
// Ако у Л има неких преосталих елемената []
// Копирај у арр []
вхиле (и {
арр [к] = Л [и];
и ++;
к ++;
}
// Ако има неких преосталих елемената у Р []
// Копирај у арр []
вхиле (ј {
арр [к] = Р [ј];
ј ++;
к ++;
}
}
воид мергеСорт (инт арр [], инт лефтИндек, инт ригхтИндек)
{
иф (лефтИндек> = ригхтИндек)
{
повратак;
}
инт миддлеИндек = лефтИндек + (ригхтИндек - лефтИндек) / 2;
мергеСорт (арр, лефтИндек, миддлеИндек);
мергеСорт (арр, миддлеИндек + 1, ригхтИндек);
спајање (арр, лефтИндек, миддлеИндек, ригхтИндек);
}
// Функција за испис елемената
// низа
воид принтАрраи (инт арр [], инт величина)
{
за (инт и = 0; и {
цоут << арр [и] << "";
}
цоут << ендл;
}
// шифра возача
инт маин ()
{
инт арр [] = {16, 12, 15, 13, 19, 17, 11, 18};
инт сизе = сизеоф (арр) / сизеоф (арр [0]);
цоут << "Несортирани низ:" << ендл;
принтАрраи (арр, величина);
мергеСорт (арр, 0, величина - 1);
цоут << "Сортирани низ:" << ендл;
принтАрраи (арр, величина);
ретурн 0;
}

Излаз:

Несортирани низ:
16 12 15 13 19 17 11 18 
Сортирани низ:
11 12 13 15 16 17 18 19

Имплементација ЈаваСцрипт алгоритма за сортирање стапања

Испод је ЈаваСцрипт примена алгоритма за сортирање спајања:

// ЈаваСцрипт имплементација
// спајање алгоритма сортирања
// Ова функција спаја два подниза арр []
// Леви подниз: арр [лефтИндек..миддлеИндек]
// Десни подниз: арр [миддлеИндек + 1..ригхтИндек]
спајање функција (арр, лефтИндек, миддлеИндек, ригхтИндек) {
нека лефтСубарраиСизе = миддлеИндек - лефтИндек + 1;
нека ригхтСубарраиСизе = ригхтИндек - миддлеИндек;
// Стварање привремених низова
вар Л = нови низ (лефтСубарраиСизе);
вар Р = нови низ (ригхтСубарраиСизе);
// Копирање података у привремене низове Л [] и Р []
за (нека је и = 0; иЛ [и] = арр [лефтИндек + и];
}
за (нека ј = 0; јР [ј] = арр [миддлеИндек + 1 + ј];
}
// Спајање привремених низова назад у арр [лефтИндек..ригхтИндек]
// Иницијални индекс левог подниза
вар и = 0;
// Иницијални индекс десног низа
вар ј = 0;
// Иницијални индекс спојеног низа
вар к = лефтИндек;
док (и {
ако (Л [и] <= Р [ј])
{
арр [к] = Л [и];
и ++;
}
иначе
{
арр [к] = Р [ј];
ј ++;
}
к ++;
}
// Ако у Л има неких преосталих елемената []
// Копирај у арр []
вхиле (и {
арр [к] = Л [и];
и ++;
к ++;
}
// Ако има неких преосталих елемената у Р []
// Копирај у арр []
вхиле (ј {
арр [к] = Р [ј];
ј ++;
к ++;
}
}
функција мергеСорт (арр, лефтИндек, ригхтИндек) {
иф (лефтИндек> = ригхтИндек) {
повратак
}
вар миддлеИндек = лефтИндек + парсеИнт ((ригхтИндек - лефтИндек) / 2);
мергеСорт (арр, лефтИндек, миддлеИндек);
мергеСорт (арр, миддлеИндек + 1, ригхтИндек);
спајање (арр, лефтИндек, миддлеИндек, ригхтИндек);
}
// Функција за испис елемената
// низа
функција принтАрраи (арр, величина) {
за (нека је и = 0; идоцумент.врите (арр [и] + "");
}
доцумент.врите ("
");
}
// шифра возача:
вар арр = [16, 12, 15, 13, 19, 17, 11, 18];
вар сизе = арр.ленгтх;
доцумент.врите ("Несортирани низ:
");
принтАрраи (арр, величина);
мергеСорт (арр, 0, величина - 1);
доцумент.врите ("Сортирани низ:
");
принтАрраи (арр, величина);

Излаз:

Несортирани низ:
16 12 15 13 19 17 11 18
Сортирани низ:
11 12 13 15 16 17 18 19

Повезан: Динамичко програмирање: примери, уобичајени проблеми и решења

Питхон имплементација алгоритма сортирања стапања

Испод је примена Питхона алгоритма за сортирање спајања:

# Питхон имплементација
# алгоритам сортирања спајања
деф мергеСорт (арр):
ако је лен (арр)> 1:
# Проналажење средњег индекса низа
миддлеИндек = лен (арр) // 2
# Лева половина низа
Л = арр [: миддлеИндек]
# Десна половина низа
Р = арр [миддлеИндек:]
# Сортирање прве половине низа
мергеСорт (Л)
# Сортирање друге половине низа
мергеСорт (Р)
# Иницијални индекс левог подниза
и = 0
# Иницијални индекс десног низа
ј = 0
# Иницијални индекс спојеног низа
к = 0
# Копирање података у привремене низове Л [] и Р []
док је и ако је Л [и] арр [к] = Л [и]
и = и + 1
иначе:
арр [к] = Р [ј]
ј = ј + 1
к = к + 1
# Провера да ли има неких преосталих елемената
док је и арр [к] = Л [и]
и = и + 1
к = к + 1
док ј арр [к] = Р [ј]
ј = ј + 1
к = к + 1
# Функција за испис елемената
# низа
деф принтАрраи (арр, величина):
за и у опсегу (величина):
испис (арр [и], енд = "")
испис ()
# Шифра возача
арр = [16, 12, 15, 13, 19, 17, 11, 18]
сизе = лен (арр)
принт ("Несортирани низ:")
принтАрраи (арр, величина)
мергеСорт (арр)
принт ("Сортирани низ:")
принтАрраи (арр, величина)

Излаз:

Несортирани низ:
16 12 15 13 19 17 11 18
Сортирани низ:
11 12 13 15 16 17 18 19

Разумевање осталих алгоритама за сортирање

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

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

Увод у алгоритам сортирања мехурића

Алгоритам сортирања облачића: одличан увод у сортирање низова.

Прочитајте следеће

О аутору