Конкурс. Программирование.

[Sasha]

Опечатался.
Если мне не изменяет память, процедуры могут иметь несколько точек входа.

[Proydoha]

В любом случае во всех популярных языках засилье функций и совсем нет процедур : )

[Sasha]

Сортировка от Jeka затрачивает в 3,4 раза меньше тактов процессора, чем сортировка от Proydoha.
Чтобы было понятней набор из миллиона случайно сгенерированных массивов (условия генерации описаны выше) программа от Jeka сортирует примерно за 5,87 секунды, программа от Proydoha за ~18.18 сeкунды. При чем провел небольшое исследование, при увеличении массива время сортировки Jeka увеличивается совсем не значительно (пропорционально), а вот в случае Proydoha возрастает очень и очень значительно.
В первый раз вижу способ, которым Proydoha передавал массив в функцию. Считаю его недопустимым.

Завтра утром попытаюсь быренько написать свой пузырек, все таки интересно что получится)

[Sasha]

Что не понравилось, нашел в интернете код от Jeka практически слово в слово...

[Sasha]

Написал свой пузырек, ушло 3 минуты (взял тот что использую всегда, когда нужно написать сортировку). Работает чуть быстрее чем за 13,8 секунды. Конечно если немного покопаться можно еще немного ускорить, но до результатов Jeka, как ни крути пузырек не дойдет.
Баллы и новое задание будет завтра.

[Proydoha]

В первый раз вижу способ, которым Proydoha передавал массив в функцию. Считаю его недопустимым.

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

Первым делом я подумал, что приложение должно быть консольным, определённо. Я ввёл в гугле "с++ консольное приложение".

Попал вот сюда (вторая ссылка в гугле): http://www.cyberforum.ru/cpp-beginners/thread138817.html

Затем я написал "с++ cout" и попал вот сюда (первая ссылка в гугле): http://programmersclub.ru/33/

Эти две закладки висели в броузере дня два, я их даже не читал. Затем проглядел по-диагонали, проверил компилирует ли компилятор решения по первой ссылке. Оказалось, что, да, компилирует.

Скелет для программы был, считай, уже готов. Надо было только вырезать все потроха из чужого примера. По второй ссылке я узал о том как работает ввод и вывод всякого. В частности о разделении пробелами входящих переменных и всего такого. Тут же понял, что это мне не подходит и выбрал чтение всей строки как в примере из раздела "ЧТЕНИЕ С КЛАВИАТУРЫ ЦЕЛОЙ СТРОКИ".

Меня очень волновал третий параметр этой функции, так как по второй ссылке не объяснялось, что нажатие на энтэр прекратит ввод по умолчанию. Поэтому я ввёл в гугле "c++ cin.getline". Попал сюда (первая ссылка в гугле): http://www.cplusplus.com/reference/iostream/istream/getline/

Вдумчиво прочитал условие (и всё равно дичайше натупил, как выяснилось этой ночью), особенно меня взволновали строки о том, что можно вводить только числа от ноля до девятки, через пробелы. Очевидно при этом каждый второй символ должен быть пробелом. Это очень легко проверить разделяя его надвое и глядя в остаток.

Запрос в гугл "С++ остаток от деления" (третья ссылка): http://otvet.mail.ru/question/4133351/

Очевидная проверка: если каждый второй символ - не пробел, то вводящий где-то накосячил. Инкоррект инпут.

Инкоррект инпутов я получил целую батарею, несмотря на то, что пробелы я расставлял правильно.

Как выяснилось я заставлял цикл, проверяющий правильность ввода и записывающий числовые переменные из массива, копаться во всей сотне элементов, в том числе и в мусоре. Случайно бросив взгляд на самый конец предпоследней открытой вкладки в броузере я увидел её - функцию, которая возвращала бы количество символов, полученных при последнем вводе. Инкоррект инпуты, связанные с пробелами, прекратились.

Дальше следовало отсеять всё, что не являлось числом. Очевидно следовало прибегнуть к преобразованию типов. Преобразование типов в С++ мне не понравилось её тогда, когда я заимел первый опыт общения с С++ (я давал ссылку на старом форуме). Запрос в гугл "Преобразование строки в число" снова показал целый веер разных вариантов. Я выбрал функцию atoi. Но она, подлая, не хотела превращать один символ в число.

Текст ошибки идёт в гугл:"Could not find a match for 'atoi(char)'"
И по первой же ссылке решение проблемы: http://en.allexperts.com/q/C-1040/checking-string-consists-numbers-2.htm

Заодно я решил узнать что возвращает функция atoi, если ей передать непреобразовываемую строку. Буквы, там, или ещё что-нибудь. "С++ atoi". http://www.cplusplus.com/reference/clibrary/cstdlib/atoi/

Возвращает она ноль. Окей. Значит сперва надо проверить не ноль ли там. Если ноль - записывать в несортированый массив ноль, иначе - в случае ноля при преобразовании писать "Инкоррект инпут". Русские буквы, кстати, компилятор не признавал в упор.

Заносим преобразованную строку в несортированый массив чисел. Но как в с++ объявляются массивы? "С++ массив". http://adorning.ru/2010/01/02/c-urok-4-massivyi/ А, так я уже объявлял такое для строки! Окей.

Заполняю массив. Сортировка должна осуществляться отдельной функцией. Отчего-то у меня именно такая формулировка въелась в голову. Окей. "С++ функции" http://valera.asf.ru/cpp/book/c07.html

Нет проблем, пишу функцию, которая реализовывала бы сортировку пузырьком, так как в школе учили, тут всё чётко как в аптеке, даже проверять не нужно. Задаюсь вопросом:"А как туда передать массив чисел?"

Пишу в гугле:"с++ передача массива в функцию". Попадаю сюда: http://forum.shelek.ru/index.php/topic,15001.0.html
Оттуда по ссылке перехожу сюда: http://forum.shelek.ru/index.php/topic,10178.msg167877.html#msg167877

Выбираю вариант, требующий наименьших переделок внутри моей уже написанной функции. Вылавливаю замысловатый баг со вторым параметром, символизирующим как глубоко надо заходить в деле сортировки.

Делаю вывод. Сдаюсь.

[Jeka]

Что не понравилось, нашел в интернете код от Jeka практически слово в слово...

свою программу написал основываясь на сделанной на первом курсе лабораторной работе на паскале)) могу даже код прислать)) так что парсил я сам у себя а не с интернета) ну а когда саму лабу писал на первом курсе, то может и смотрел какие-то готовые исходники) поверь я этот способ на ЛИСТОЧКЕ преподу два раза сортировал и со второго-таки получил оценку, так что этот метод я ЗНАЮ как работает, а не спарсил его с интернета как обезьяна. переменные как называть особо не запаривался, и как ИНАЧЕ может выглядеть быстрая сортировка??? разве что сортировать, взяв опорный элемент не медиану последовательности, а скажем первый либо последний элемент. по поводу переменных, счетчики i,j нас учили на первом курсе мне что писать p,q место них? левый и правый края последовательности соответственно лефт и райт? и я не намерен их называть как-либо иначе. а сама то функция 5 строчек? что здесь может особо отличаться? пожалуйста, избавьте от подобных намекев, это не приятно!

[Jeka]

Написал свой пузырек, ушло 3 минуты (взял тот что использую всегда, когда нужно написать сортировку). Работает чуть быстрее чем за 13,8 секунды. Конечно если немного покопаться можно еще немного ускорить, но до результатов Jeka, как ни крути пузырек не дойдет.
Баллы и новое задание будет завтра.

ну да, пузырек имеет сложность N в квадрате. соответственно при небольшом уже увеличении числа, время потраченное на сортировку растет в квадратичной сложности, что весьма печально. алгоритм, который я использывал, "быстрая сортировка" имеет сложность N log N, что является гораздо эффективней, особенно на большом числе элементов) . Была к стати идея использовать пирамидальную сортировку, но она сложнее в реализации и даст более эффективный результат разве что на большом числе элементов

[Jeka]

В первый раз вижу способ, которым Proydoha передавал массив в функцию. Считаю его недопустимым.

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

Первым делом я подумал, что приложение должно быть консольным, определённо. Я ввёл в гугле "с++ консольное приложение".

Попал вот сюда (вторая ссылка в гугле): http://www.cyberforum.ru/cpp-beginners/thread138817.html

Затем я написал "с++ cout" и попал вот сюда (первая ссылка в гугле): http://programmersclub.ru/33/

Эти две закладки висели в броузере дня два, я их даже не читал. Затем проглядел по-диагонали, проверил компилирует ли компилятор решения по первой ссылке. Оказалось, что, да, компилирует.

Скелет для программы был, считай, уже готов. Надо было только вырезать все потроха из чужого примера. По второй ссылке я узал о том как работает ввод и вывод всякого. В частности о разделении пробелами входящих переменных и всего такого. Тут же понял, что это мне не подходит и выбрал чтение всей строки как в примере из раздела "ЧТЕНИЕ С КЛАВИАТУРЫ ЦЕЛОЙ СТРОКИ".

Меня очень волновал третий параметр этой функции, так как по второй ссылке не объяснялось, что нажатие на энтэр прекратит ввод по умолчанию. Поэтому я ввёл в гугле "c++ cin.getline". Попал сюда (первая ссылка в гугле): http://www.cplusplus.com/reference/iostream/istream/getline/

Вдумчиво прочитал условие (и всё равно дичайше натупил, как выяснилось этой ночью), особенно меня взволновали строки о том, что можно вводить только числа от ноля до девятки, через пробелы. Очевидно при этом каждый второй символ должен быть пробелом. Это очень легко проверить разделяя его надвое и глядя в остаток.

Запрос в гугл "С++ остаток от деления" (третья ссылка): http://otvet.mail.ru/question/4133351/

Очевидная проверка: если каждый второй символ - не пробел, то вводящий где-то накосячил. Инкоррект инпут.

Инкоррект инпутов я получил целую батарею, несмотря на то, что пробелы я расставлял правильно.

Как выяснилось я заставлял цикл, проверяющий правильность ввода и записывающий числовые переменные из массива, копаться во всей сотне элементов, в том числе и в мусоре. Случайно бросив взгляд на самый конец предпоследней открытой вкладки в броузере я увидел её - функцию, которая возвращала бы количество символов, полученных при последнем вводе. Инкоррект инпуты, связанные с пробелами, прекратились.

Дальше следовало отсеять всё, что не являлось числом. Очевидно следовало прибегнуть к преобразованию типов. Преобразование типов в С++ мне не понравилось её тогда, когда я заимел первый опыт общения с С++ (я давал ссылку на старом форуме). Запрос в гугл "Преобразование строки в число" снова показал целый веер разных вариантов. Я выбрал функцию atoi. Но она, подлая, не хотела превращать один символ в число.

Текст ошибки идёт в гугл:"Could not find a match for 'atoi(char)'"
И по первой же ссылке решение проблемы: http://en.allexperts.com/q/C-1040/checking-string-consists-numbers-2.htm

Заодно я решил узнать что возвращает функция atoi, если ей передать непреобразовываемую строку. Буквы, там, или ещё что-нибудь. "С++ atoi". http://www.cplusplus.com/reference/clibrary/cstdlib/atoi/

Возвращает она ноль. Окей. Значит сперва надо проверить не ноль ли там. Если ноль - записывать в несортированый массив ноль, иначе - в случае ноля при преобразовании писать "Инкоррект инпут". Русские буквы, кстати, компилятор не признавал в упор.

Заносим преобразованную строку в несортированый массив чисел. Но как в с++ объявляются массивы? "С++ массив". http://adorning.ru/2010/01/02/c-urok-4-massivyi/ А, так я уже объявлял такое для строки! Окей.

Заполняю массив. Сортировка должна осуществляться отдельной функцией. Отчего-то у меня именно такая формулировка въелась в голову. Окей. "С++ функции" http://valera.asf.ru/cpp/book/c07.html

Нет проблем, пишу функцию, которая реализовывала бы сортировку пузырьком, так как в школе учили, тут всё чётко как в аптеке, даже проверять не нужно. Задаюсь вопросом:"А как туда передать массив чисел?"

Пишу в гугле:"с++ передача массива в функцию". Попадаю сюда: http://forum.shelek.ru/index.php/topic,15001.0.html
Оттуда по ссылке перехожу сюда: http://forum.shelek.ru/index.php/topic,10178.msg167877.html#msg167877

Выбираю вариант, требующий наименьших переделок внутри моей уже написанной функции. Вылавливаю замысловатый баг со вторым параметром, символизирующим как глубоко надо заходить в деле сортировки.

Делаю вывод. Сдаюсь.

схожу с ума : МНОГО БУКААФ)) там все проще. зачем те этот getline и пробелы. в функцию main поступает массив указателей на строки. каждый элемент массива - по сути есть строка, являющаяся одним из параметров главной функции. например ты пишешь в коммандной строке
proydoha.exe 1 2 3 4
тогда в массиве argv первый элемент это "proydoha", 2ой - число 1 , третий - число 2 и т д
в цикле запустил функцию atoi и перенес эти данные в динамический массив? к стати ты использовал ДИНАМИЧЕСКИЙ массив или как?)

[Proydoha]

схожу с ума : МНОГО БУКААФ))

Многабукаф ты в цитату взял : ) Излагаю всё как есть, что бы все видели как я до такой жизни докатился : )

там все проще. зачем те этот getline и пробелы. в функцию main поступает массив указателей на строки. каждый элемент массива - по сути есть строка, являющаяся одним из параметров главной функции. например ты пишешь в коммандной строке
proydoha.exe 1 2 3 4
тогда в массиве argv первый элемент это "proydoha", 2ой - число 1 , третий - число 2 и т д

Теперь, когда ты это сказал, твоё решение мне кажется в десятки сотен раз разумнее, но в день написания... : )

в цикле запустил функцию atoi и перенес эти данные в динамический массив? к стати ты использовал ДИНАМИЧЕСКИЙ массив или как?)

Не динамический. Парой сообщений раньше было написано, что больше сотни значений ввести нельзя, я сделал строку на 200 символов (сотня пробелов и сотня чисел). Когда будут превышены эти пределы ввод будет считаться завершенным и пойдёт выполняться всё остальное. В теории.

[Sasha]

Результаты задания #3
Jeka - 10 баллов
Proydoha - 7 баллов

[Sasha]

Вот программа с помощью которой я проверял. Здесь quick_sort - функция от Jeka, mybuble - моя, bubble_sort - Proydoha

Код Выделить Развернуть

void quick_sort(int l,int r, int *mas)
{
int i=l;
int j=r;
int m=int((l+r)/2);
int p=mas[m];
do
{
while (mas[i]<p)
{
i++;
}
while (mas[j]>p)
{
  j--;
}
if (i<=j)
{
int tmp=mas[i];
mas[i]=mas[j];
mas[j]=tmp;
i++;
j--;
}
}
   while(i<=j);
     if (j>l)
    quick_sort(l,j,mas);
     if (i<r)
quick_sort(i,r,mas);

}

void mybubble(int *mas, int n)
{
int x;
for(int i = 0; i < n-1; i++)
for( int j = 0; j < n-i-1; j++)
if(mas[j]>mas[j+1])
{
x = mas[j];
mas[j] = mas[j+1];
mas[j+1]=x;
}
}

void bubble_sort (int (&a)[100], int j)
{
int temp;
int i;
temp = 42;
while (temp == 42)
{
  temp = 32167;
  for (i = 0; i<j; i++)
  {
   if (a[i] > a[i+1])
   {
    temp = a[i];
    a[i] = a[i+1];
    a[i+1] = temp;
    temp = 42;
   }
  }
}
}

int _tmain(int argc, _TCHAR* argv[])
{
int *mas1;
int mas2[100];
int *mas3;
int n;
for (int i = 0; i < 1000000; i++)
{
n = rand()%100 + 1;
mas1 = new int[n];
mas3 = new int[n];
for(int j = 0; j < n; j++)
{
int x = rand()%10;
mas1[j] = x;
mas2[j] = x;
mas3[j] = x;
}
bubble_sort(mas2, n-1);
quick_sort(0, n-1, mas1);
mybumble(mas3,n);
delete []mas1;
delete []mas3;
}
}

[Jeka]

Вот программа с помощью которой я проверял. Здесь quick_sort - функция от Jeka, mybuble - моя, bubble_sort - Proydoha

Код Выделить Развернуть

void quick_sort(int l,int r, int *mas)
{
int i=l;
int j=r;
int m=int((l+r)/2);
int p=mas[m];
do
{
while (mas[i]<p)
{
i++;
}
while (mas[j]>p)
{
  j--;
}
if (i<=j)
{
int tmp=mas[i];
mas[i]=mas[j];
mas[j]=tmp;
i++;
j--;
}
}
   while(i<=j);
     if (j>l)
    quick_sort(l,j,mas);
     if (i<r)
quick_sort(i,r,mas);

}

void mybubble(int *mas, int n)
{
int x;
for(int i = 0; i < n-1; i++)
for( int j = 0; j < n-i-1; j++)
if(mas[j]>mas[j+1])
{
x = mas[j];
mas[j] = mas[j+1];
mas[j+1]=x;
}
}

void bubble_sort (int (&a)[100], int j)
{
int temp;
int i;
temp = 42;
while (temp == 42)
{
  temp = 32167;
  for (i = 0; i<j; i++)
  {
   if (a[i] > a[i+1])
   {
    temp = a[i];
    a[i] = a[i+1];
    a[i+1] = temp;
    temp = 42;
   }
  }
}
}

int _tmain(int argc, _TCHAR* argv[])
{
int *mas1;
int mas2[100];
int *mas3;
int n;
for (int i = 0; i < 1000000; i++)
{
n = rand()%100 + 1;
mas1 = new int[n];
mas3 = new int[n];
for(int j = 0; j < n; j++)
{
int x = rand()%10;
mas1[j] = x;
mas2[j] = x;
mas3[j] = x;
}
bubble_sort(mas2, n-1);
quick_sort(0, n-1, mas1);
mybumble(mas3,n);
delete []mas1;
delete []mas3;
}
}

я в замешательстве! какой-то странный метод у Proydoha... напоминает обычный пузырек но тут какое то temp со значением 42, а идея вроде та же что и в обычном пузырьке... в качестве j я так понял передана размерность массива? не очень привычно этой буквой...
Саша, а что тебя смутило в способе передаче массива в функции Пройдохи?

[Jeka]

Вот программа с помощью которой я проверял. Здесь quick_sort - функция от Jeka, mybuble - моя, bubble_sort - Proydoha

Код Выделить Развернуть

void quick_sort(int l,int r, int *mas)
{
int i=l;
int j=r;
int m=int((l+r)/2);
int p=mas[m];
do
{
while (mas[i]<p)
{
i++;
}
while (mas[j]>p)
{
  j--;
}
if (i<=j)
{
int tmp=mas[i];
mas[i]=mas[j];
mas[j]=tmp;
i++;
j--;
}
}
   while(i<=j);
     if (j>l)
    quick_sort(l,j,mas);
     if (i<r)
quick_sort(i,r,mas);

}

void mybubble(int *mas, int n)
{
int x;
for(int i = 0; i < n-1; i++)
for( int j = 0; j < n-i-1; j++)
if(mas[j]>mas[j+1])
{
x = mas[j];
mas[j] = mas[j+1];
mas[j+1]=x;
}
}

void bubble_sort (int (&a)[100], int j)
{
int temp;
int i;
temp = 42;
while (temp == 42)
{
  temp = 32167;
  for (i = 0; i<j; i++)
  {
   if (a[i] > a[i+1])
   {
    temp = a[i];
    a[i] = a[i+1];
    a[i+1] = temp;
    temp = 42;
   }
  }
}
}

int _tmain(int argc, _TCHAR* argv[])
{
int *mas1;
int mas2[100];
int *mas3;
int n;
for (int i = 0; i < 1000000; i++)
{
n = rand()%100 + 1;
mas1 = new int[n];
mas3 = new int[n];
for(int j = 0; j < n; j++)
{
int x = rand()%10;
mas1[j] = x;
mas2[j] = x;
mas3[j] = x;
}
bubble_sort(mas2, n-1);
quick_sort(0, n-1, mas1);
mybumble(mas3,n);
delete []mas1;
delete []mas3;
}
}

не совсем понял... три массива, два из них динамические, один статический... заполняются одними и теми же значениями и прогоняются, подставляя в функции??

[Sasha]

Да. Я по определенным соображениям отказался от идеи запускать ваши программы в отдельном процессе, передавая параметры в main, а просто скопировал ваши функции в одну программу и поочередно вызвал, замерив такты процессора.
Я никогда не видел такого способа передачи и вобще сама конструкция ввела меня немного в замешательство, не представляю как это внутри работает.