Сортиране на масив чрез вмъкване

[Evertom]

Здравейте,наясно съм с принципа на работа на този вид сортиране.Разбирам го чисто алгоритмично,но не мога да разбера как е направен в c++ кода,гледам го кода и не мога да го разбера а и никъде не е обяснено кое какво прави.Ако може малко помощ с обяснението.

 

Ето го и кода

 

 

#include<iostream>

using namespace std;

int main()

{

int Masiv[5]={20,31,42,52,30};

int i,j,index;

 

for(i=1;i<5;i++){

index=Masiv;

j=i;

whie( (j>0) && (Masiv[j-1]>index) )

{ Masiv[j]=Masiv[j-1];

j=j-1;}

Masiv[j]=index;

}}

 

 

for(int i=0;i<5;i++)

cout<<Masiv<<" ";

return 0;

}

 

 

Частта с различен шрифт и цвят е същинското сортиране.Кода го намерих в интернет и се надявах че ще го разбера като гледах алгоритъма за сортиране и следвам кода,но изобщо не виждам как този код следва алгоритъма.

[s.feradov]

Методът се гради на два масива - масив с ненаредени стойности и готовия масив със сортирани такива.

 

Първоначално се присвоява стойността на даден елемент от масива на декларираната променлива index. След което, на другата декларирана променлива j се присвоява стойността на i.

 

Цикълът while е въведен по следния начин:

while((j>0) && (Masiv[j-1]>index)

 

В този случай се задава условието, че за да се изпълни цикъла и двата израза трябва да бъдат истина. При True, цикълът се задейства и на съответния елемент от масива ( Masiv[j] ) се присвоява стойността на елемента Masiv[j-1], тъй като от цикъла следва, че

Masiv[j-1]> index

т.е. предишния елемент е по-голям от следващия в подредбата.

 

Най-накрая се присвоява стойността на index на елемента Masiv[j] и цикълът for започва да се повтаря докато:

i<5 = False

[Evertom]

Благодаря за отговора,но това ми е ясно.Как се задават и т.н.не мога да разбера логиката по която се прави,защо точно така се пише.Тоест не мога да си представя как тези команди ще подредят числата,не разбирам как ще го направят.

Например имаме редицата 3 5 1.Можеш ли да обясниш стъпка по стъпка какво ще направят командите с числата,защото така нищо не разбирам.

Може ако искаш само за едно минаване през цикъла да обясниш защото иначе писането сигурно ще е много.

[s.feradov]

Добре.

 

Да приемем, че това е кодът:

 

int Masiv[3]={3,5,1}
int i,j,index;

for(i=1;i<5;i++)
{
index=Masiv[i];
j=i;
while((j>0)&&(Masiv[j-1]>index))
{
Masiv[j]=Masiv[j-1];
j=j-1;
}
Masiv[j]=index;
}

 

Първи цикъл:

 

index = 5 //5=Masiv[1]
j=1
while ((j>0)&& (Masiv[0]> index)) //false
Masiv[1] = 5

 

Втори цикъл:

 

index = 1 //1 = Masiv[2]
j=2
while ((j>0) && (Masiv[1]> index)) // True
Masiv[2]=5 // Masiv[1] =5
j=1
while ((j>0) && (Masiv[0]>index)) //True
Masiv[1] = 3 //Masiv[0] = 3
j=0 -> Край на цикъл.
Masiv[0] = 1

 

Допълнително описание:

 

Резултат от първи цикъл на for: 3,5,1
Резултат от втори цикъл на for:
Първи цикъл на while: 3,1,5
Втори цикъл на while: 1,3,5

[Evertom]

3 5 1

Мисля че го разбрах while проверява условието дали има лявостоящо число по-голямо от дясно стоящото например 5>1 и 1 трябва да се размени със 5-цата.Изпълняват се командите във цикъла while и списъка с цифри ще изглежда така 3 5 5.Сваляме j с 1 и проверяваме дали отговаря на условията на while в случая j=1 и masiv[0]=3 > index=1 и пак изпълняваме командите в цикъла while,списъка става 3 3 5.

j-1=0 и този път вече не отговаря на на условията затова отиваме директно на

Masiv[j]=index; и списъка става 1 3 5 и вече е подреден.

 

Доста е трудно да се осмисли всичко това,никога не бих се сетил сам да напиша кода. Сега горе долу ми се изясни благодаря за помощта

[s.feradov]

Основната функция на while тук е точно такава. Проверка на това, дали дадена стойност е по-висока от предходната. Ако е, то цикълът приключва тъй като едно от условията не е удовлетворено. Ако стойността е по-ниска, то се изпълняват командите в while блока и стойността се присвоява на по-преден елемент в масива.