Методы сортировки. Их сравнительный анализ

str.Format("%d,",mas2[i]);//формирование строки

pDC->TextOut(10+i*20,80,str);//вывод строки на экран

}

str.Format("Количество перестановок в нашем случае: %d",count);//формирование строки

pDC->TextOut(10,110,str);//вывод строки на экран

if(metod==3)//если был выбран метод "Пузырька"

{

str.Format("Максимальное количество перестановок для массива из %d элементов методом 'Пузырька': %d",kol, kol*(kol-1)/2);//формирование строки

pDC->TextOut(10,140,str);//вывод строки на экран

}

}

}

/////////////////////////////////////////////////////////////////////////////

// CSortView diagnostics

#ifdef _DEBUG

void CSortView::AssertValid() const

{

CView::AssertValid();

}

void CSortView::Dump(CDumpContext& dc) const

{

CView::Dump(dc);

}

CSortDoc* CSortView::GetDocument() // non-debug version is inline

{

ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CSortDoc)));

return (CSortDoc*)m_pDocument;

}

#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////

// CSortView message handlers

//при выборе сортировки Quicksort

void CSortView::OnQuick()

{

//объявление локальных переменных

sort=true;

metod=1;

int i;

count=0;

for(i=0;i<kol;i++)

{

mas2[i]=mas[i];

}

quicksort(0, kol-1);//вызов функции quicksort

Invalidate(true);//перерисовка содержимого окна

}

//при выборе сортировки Shell

void CSortView::OnShell()

{

//объявление локальных переменных

sort=true;

metod=2;

int ii,t=5,i,j, k, s, m, h[6], x;

count=0;

for(ii=0;ii<kol;ii++)

{

mas2[ii]=mas[ii];

}

h[1]=9; h[2]=5; h[3]=3; h[4]=2; h[5]=1;

////////////////////////////////////////////

//АЛГОРИТМ

for(m=1;m<=t;m++)

{

k=h[m];

s=-k;

for(i=k+1; i<=kol;i++)

{

x=mas2[i];

j=i-k;

while (x<mas2[j] && j<kol)

{

mas2[j+k]=mas2[j];

j=j-k;

}

mas2[j+k]=x;

count++;

}

}

x=mas2[0];

mas2[0]=mas2[1];

mas2[1]=x;

////////////////////////////////////////////

Invalidate(true);//перерисовка содержимого окна

}

//при выборе сортировки Bubble

void CSortView::OnPuzirok()

{

//объявление локальных переменных

int dop;

bool end;

count=0;

sort=true;

metod=3;

int i, j;

for(i=0;i<kol;i++)

{

mas2[i]=mas[i];

}

////////////////////////////////////////////

//АЛГОРИТМ

for(i=0;i<kol;i++)

{

end=true;

for(j=i+1;j<kol;j++)

{

if(mas2[i]>mas2[j])

{

dop=mas2[i];

mas2[i]=mas2[j];

mas2[j]=dop;

end=false;

count++;

}

}

if(end==true) break;

}

/////////////////////////////////////////////

Invalidate(true);//перерисовка содержимого окна

}

//функция быстрого поиска

void CSortView::quicksort(int l, int r)

{

int i, j;

i=l;j=r;

{

part(l, r, i, j);

if(i<r)quicksort(i, r);// переход к сортировке левой части

if(j>l)quicksort(l, j);// переход к сортировке правой части

}

}

//функция поиска по частям

void CSortView::part(int l, int r, int &i, int &j)

{

int x, dop;

i=l;

j=r;

x=(l+r)/2;

do

{

while(mas2[i]<mas2[x])

i++;

while(mas2[j]>mas2[x])

j--;

if(i<=j)

{

dop=mas2[i];

mas2[i]=mas2[j];

mas2[j]=dop;

i++;j--;count++;

}

}

while(i<j);

}

Литература

1. Петзольд Ч. Программирование под Windows 95. В двух книгах: BHV – Санкт - Петербург, 1997, silt.

2. Ричард С.Линкер, Том Арчер. Программирование для Windows 98. Библия разработчика. “Диалектика ” – Москва, 1999.-864 с.: ил.- Парал. тит. англ. Уч.пос.

3. Джесс Либерти. С++ за 21 день. ”Вильямс” - Москва, 2000.-816 с.: ил. - Парал.тит. англ.

4. Дэвид Дж. Круглински. Основы С++. “Русская редакция” – Москва, 1997.- 696 с.: ил.

5. Кэйт Грегори. Использование Visual C++. “Вильямс” – Москва, 1999.-864 с.: ил.. - Парал.тит. англ., уч. пос.

7. Конспект лекций.