Процедуры сортировки массива целых чисел в Си

Здравствуйте!!! подскажите пожалуйсто!!!

Порядок выполнения работы:
1. Разработать процедуры сортировки массива целых чисел методом прямого выбора, методом пузырьковой сортировки и методом шейкерной сортировки (язык программирования Си++).
2. Правильность сортировки проверить путем подсчета контрольной суммы и числа серий в массиве.
3. Во время сортировки предусмотреть подсчет количества пересылок и сравнений (М и С), сравнить их с теоретическими оценками.
4. Составить таблицу следующего вида (данные получить экспериментально) для n= 100, 200, 300, 400, 500. (n – количество элементов в массиве)
5. Проанализировать полученные результаты. (Какой из методов самый быстрый? Самый медленный? Как сложность зависит от начальной отсортированности?)

вот код программы на Си:

#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
#include <memory.h>
//максимальная длина массива
const int maxn=500;
int ar[maxn],br[maxn],cr[maxn],dr[maxn];
int kolc,kolm;
//метод прямого выбора
int prv(int size,int* arr)
{
	int i,k,b;
	int m,c;
	int min;
	//количество пересылок и сравнений
	m=0; c=0;
	//проходимся по массиву с 0
	for (i=0; i<size-1; i++)
	{	min=i;
		//проходимся с и до конца массива и ищем минимальный
		for (k=i+1; k<size; k++)
		{	c++;
			if (arr[k]<arr[min]) min=k;
		}
		if (min!=i)
		{	b=arr[i]; arr[i]=arr[min]; arr[min]=b;
			m++;
		} }
	//запоминаем количество пересылок и сравнений
	kolc=c; kolm=m;
	return 0; }
//метод пузырька
int puz(int size,int* arr)
{	int i,k,b,c,m;
	//количество пересылок и сравнений
	c=0; m=0;
	//проходимся по всему массиву 1 раз
	for (i=1; i<size; i++)
	{	//с конца до текущего элемента
		for (k=size-1; k>=i; k--)
		{	c++;
			if (arr[k-1]>arr[k]) 
			{
				b=arr[k-1]; arr[k-1]=arr[k]; arr[k]=b; m++;
			} } }
	//запоминаем количество пересылок и сравнений
	kolc=c; kolm=m;
	return 0; }
//метод Щейкера
int sheiker(int size,int* arr)
{	int i,k,b,m,c;
	m=0; c=0;
	int l=1;
	int r=size-1; k=size-1;
	do
	{	for (i=r; i>=l; i--)		//идем вверх по массиву
		{	c++;
			if (arr[i-1]>arr[i])		//сравниваем элемент по весу с соседним верхним
			{
			   b=arr[i]; arr[i]=arr[i-1]; arr[i-1]=b; k=i; m++;	//двигаем легкий элемент по массиву вверх
			} }
		l=k+1;	//верхняя граница - выше которой алгоритм не поднимется проверять элементы
		for (i=l; i<=r; i++)	//меняем направление - вниз
		{	c++;
			if (arr[i-1]>arr[i])		//сравниваем элемент по весу с соседним нижним
			{
			   b=arr[i-1]; arr[i-1]=arr[i]; arr[i]=b; k=i; m++;	//двигаем тяжелый элемент по массиву вниз
			} }
		r=k-1;	//нижняя граница - ниже которой алгоритм не опускается проверять элементы
	}
	while (r>=l);
	kolm=m; kolc=c;
	return 0; }
//считаем контрольную сумму
int consum(int size, int* arr)
{	int sum=0;
	//считаем сумму всех чисел массива
	for (int i=0; i<size; i++) sum+=arr[i];
	//возращаем данное значение
	return sum; }
//считаем количество серий
int kolser(int size,int* arr)
{	int kol=1;
	for (int i=1; i<size; i++) 
		if (arr[i]!=arr[i-1]) kol++;
	return kol; }

int main(int argc, char* argv[])
{	int n,i=0;
	//делаем ввод данных
	printf("Enter n= ",&n);
	scanf("%i",&n);
	//все числа случайные
	randomize();
	for (i=0; i<n; i++) ar[i]=random(1000000+1);

printf("Dlya slychainogo massiva: \n\n");
   	//сортируем массив разными методами
	//при этом происходит проверка контрольных сумм
	memcpy(br,ar,sizeof(ar)); memcpy(cr,ar,sizeof(ar)); memcpy(dr,ar,sizeof(ar));
	//сортируем и выводим количество пересылок и сравнений
	prv(n,br); printf("Sort Pr.Vib.  m=%i  c=%i\n",kolm,kolc);
	puz(n,cr); printf("Sort M.Puz.  m=%i  c=%i\n",kolm,kolc);
	sheiker(n,dr); printf("Sort She. m=%i  c=%i\n\n",kolm,kolc);

//делаем проверку по контрольным суммам
	if (consum(n,ar)==consum(n,br) && consum(n,ar)==consum(n,cr) && consum(n,ar)==consum(n,dr)) printf("Kontrolnie summi sovpadaut\n");
	else printf("Kontrolnie summi ne sovpadaut\n");
	//делаем подсчет количества серий в отсортированных массивах и сравниваем их
	if (kolser(n,br)==kolser(n,cr) && kolser(n,br)==kolser(n,dr)) printf("Kol-vo seriy sovpadaet\n");
	else printf("Kol-vo seriy ne sovpadaet\n");

printf("Dlya yporadochennogo massiva: \n\n");
	for (i=0;i<n;i++)
		{for (int j=i+1; j<n+1; j++)
			{if (ar[i]>ar[j])
				{int tmp=ar[i];
				ar[i]=ar[j];
				ar[j]=tmp;}}} 
        
	prv(n,br); printf("Sort Pr.Vib.  m=%i  c=%i\n",kolm,kolc);
	puz(n,cr); printf("Sort M.Puz.  m=%i  c=%i\n",kolm,kolc);
	sheiker(n,dr); printf("Sort She. m=%i  c=%i\n\n",kolm,kolc);
//делаем проверку по контрольным суммам
	if (consum(n,ar)==consum(n,br) && consum(n,ar)==consum(n,cr) && consum(n,ar)==consum(n,dr)) printf("Kontrolnie summi sovpadaut\n");
	else printf("Kontrolnie summi ne sovpadaut\n");
	//делаем подсчет количества серий в отсортированных массивах и сравниваем их
	if (kolser(n,br)==kolser(n,cr) && kolser(n,br)==kolser(n,dr)) printf("Kol-vo seriy sovpadaet\n");
	else printf("Kol-vo seriy ne sovpadaet\n");
	getchar(); getchar();
	return 0;
}

при вводе n= 100 и 200 он показывает правельные значения, но при вводе 300, 400, 500 он выдает половину значений отрицательных... поидее чем больше кол-во (n) тем больше сумма пересылок и сравнений... немогу разобраться... подскажите кто сталкивался с такими задачами... (при сортировке другими методами (Шелла, пирамидальной и Хоара) всё работает без проблем...)
может так и должно быть и я чёта не даганяю... прошу у вас помощи...

может быть так и должно быть, и это правельные ответы, но почему то меня терзают сомнения...

[dxdy]

maxgalll если тебя терзают сомнения, то скачай книжку Кнута "Искусство программирования" 2 том, там он очень подробно описывает и анализирует все сортировки.

[RUSt88]

а вообще-то все эти сортировки описаны на википедии, описана их сложность и т.п.

я и по книжке пробежался, и вики сматрел... (мож проглядел)
нашол исходник на делфи там всё работает... и выводит правельные значения....
может по каким-то причинам не получается присвоить значения переменным kolm и kolc.... подскажите пожалуста...