2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Помогите с сортировкой.
Сообщение21.09.2013, 22:03 
Здравствуйте, уважаемые посетители форума! Я столкнулся с задачей по сортировке элементов массива по возрастанию и потерпел некоторый провал в ее решении :-( (Я ровно три недели программирую на С, если что.) Дан небольшой массив, который вводится с клавиатуры. Отсортировать его элементы по возрастанию и напечатать это дело.
Теперь о том, что у меня вышло. До того, как я столкнулся с этой программой, никаких алгоритмов по сортировке я не знал и сел писать свой :D Идея была и есть, но вот реализовать ее не удалось - пришлось узнавать и использовать пузырьковый алгоритм. Итак - я сейчас принципиально не читал про остальные алгоритмы (знаю, они есть), а снова пробовал реализовать свою идею.

Код:
#include <stdio.h>
#include <math.h>
#include <locale.h>
int main (void)
{
   int n,i,j,min,max,k;
   char a[255];
   char b[255];
   setlocale(LC_ALL, "rus");
   printf("Алгоритм сортировки 1.0 \n");
   printf("n=");
   scanf("%i", &n);

   for(i=0;i<n;i++)
   {
      printf("a[%i]=",i);
      scanf("%i", &a[i]);
   }

   for(i=0;i<n;i++)
   {
      max=a[0];
          if(a[i]>max)
         {
            max=a[i];
         }
   }
        k=a[0];
   for(j=0;j<n;j++)
   {       
             min=k;
                       for(i=0;i<n;i++)
               {
                          if(a[i]<=min)
                     {
                        min=a[i];
                        a[i]=max+1;
                     }
               }

            b[j]=min;
   }
   
      for(j=0;j<n;j++)
   {
      printf("%i \n", b[j]);
   }
      return 0;
}


Этот код нерабочий, но надеюсь, что он все таки намекает, что я хочу сделать. Прошу мне помочь, подсказать,как, сохранив идею, реализовать сортировку.

 
 
 
 Re: Помогите с сортировкой.
Сообщение22.09.2013, 06:58 
Аватара пользователя
Процесс поиска ошибок в программе называет отладкой.
Для того чтобы было проще разбей задачу на подзадачи и проверяй их по отдельности.

К примеру вот тут ошибка, вполне очевидная
shukshin в сообщении #766397 писал(а):
Код:

for(i=0;i<n;i++)
{
  max=a[0];
  if(a[i]>max)
  {
    max=a[i];
  }
}



И здесь бы код подправить не помешало бы. Если этого не сделать, то условный оператор - if() может ни разу не дать true.
Цитата:
Код:
       k=a[0];
   for(j=0;j<n;j++)
   {       
             min=k;


А ещё во всём коде не учтено то, что во входном массиве числа могут повторяться.

 
 
 
 Re: Помогите с сортировкой.
Сообщение22.09.2013, 12:55 
shukshin в сообщении #766397 писал(а):
Код:
min=a[i];
a[i]=max+1;


Здесь какая-то ошибка возможна, хотя бы потому, что элемент может стать уже равным $\max+1$, и при этом непопавшим в конечный массив.


В принципе, Ваш алгоритм сильно похож на

(Название алгоритма скрыто здесь, появляется при нажатии.)

Сортировку методом выбора максимума
,
причем в исходном варианте не используется дополнительный массив.

(Описание того, как переделать программу так, чтобы она работала по алгоритму, название которого скрыто.)

Можно было бы сначала просто присваивать номер маленького элемента в отдельную переменную $t$, если дальше появятся еще меньшие, перезаписывать $t$, а в конце просто поменять местами $a[j]$ и $a[t]$. Тогда не потребуется дополнительной памяти, но это будет чуть-чуть другой алгоритм.

 
 
 
 Re: Помогите с сортировкой.
Сообщение22.09.2013, 14:01 
shukshin, программа может не работать как минимум из-за ошибок двух типов - в алгоритме и в его реализации. Предлагаю вам сначала описать словами алгоритм, а не предлагать участникам понять его суть из кода, и выясним - есть ли ошибки в нем. А уже потом перейдем к реализации (на любом языке программирования).

 
 
 
 Re: Помогите с сортировкой.
Сообщение22.09.2013, 14:51 
_Ivana, конечно.
1)Сначала нам вводится массив, по умолчанию заведомо небольшой - a.
2)Мы заводим еще один, пока пустой - b.
3)Затем мы находим один из максимальных элементов a, max.
4) Затем находим минимальный элемент a и первому элементу массива b присваиваем его значение. А этому минимальному элементу массива a присваиваем значение max+1.
5 и далее)Пункт 4 повторить
Массив b на выход, а состоит из одних max+1.

 
 
 
 Re: Помогите с сортировкой.
Сообщение22.09.2013, 15:13 
shukshin в сообщении #766595 писал(а):
А этому минимальному элементу массива a присваиваем значение max+1.
А если у вас максимум — наибольшее представимое данным типом значение?

-- Вс сен 22, 2013 18:18:28 --

P. S. Для внутритекстовых фрагментов кода удобно использовать теги [t​t]max[​/tt]: max.

 
 
 
 Re: Помогите с сортировкой.
Сообщение22.09.2013, 15:39 
shukshin, понятно, алгоритм рабочий, хотя конечно arseniiv нашел возможную ошибку, но если пока не обращать на нее внимания (или принять меры по ее устранению, например, переписать весь исходный массив в другой с расширенным типом), а также оставить за рамками обсуждения явную неоптимальность вашего алгоритма, то можно его реализовывать и проверять. Вместо вываливания текста кода и просьб о его анализе на предмет ошибок, рекомендую вам самому научиться искать ошибки и отлаживать код. Для этого есть как минимум, 2 инструмента: отладчик и отладочная печать промежуточных значений при выполнении программы. Начните сначала - проверьте, прапвильно ли у вас выполняется пункт 3 - поставьте после него возврат функции и перед этим выведите на экран значение $max+1$. Если оно правильно, проверьте что возвращает минимум и какая его позиция (индекс). И т.д., пока не обнаружите и не вычистите все ошибки реализации правильного алгоритма.

 
 
 
 Re: Помогите с сортировкой.
Сообщение22.09.2013, 17:56 
Спасибо большое всем, ибо я все отладил! :-)

 
 
 
 Re: Помогите с сортировкой.
Сообщение22.09.2013, 21:01 
А теперь реализуйте какой-нибудь нормальный алгоритм! :-)

 
 
 
 Re: Помогите с сортировкой.
Сообщение28.09.2013, 10:23 
Аватара пользователя
arseniiv в сообщении #766739 писал(а):
А теперь реализуйте какой-нибудь нормальный алгоритм! :-)
Или используйте функцию qsort() :-)

 
 
 
 Re: Помогите с сортировкой.
Сообщение29.09.2013, 19:19 
whitefox в сообщении #768575 писал(а):
Или используйте функцию qsort() :-)
В учебной задаче? :-)

 
 
 
 Re: Помогите с сортировкой.
Сообщение30.09.2013, 19:59 
Аватара пользователя
Yuri Gendelman в сообщении #769116 писал(а):
whitefox в сообщении #768575 писал(а):
Или используйте функцию qsort() :-)
В учебной задаче? :-)

Как я понял, ТС изучает язык С, а не алгоритмы сортировки
shukshin в сообщении #766397 писал(а):
До того, как я столкнулся с этой программой, никаких алгоритмов по сортировке я не знал и сел писать свой :D Идея была и есть, но вот реализовать ее не удалось - пришлось узнавать и использовать пузырьковый алгоритм. Итак - я сейчас принципиально не читал про остальные алгоритмы (знаю, они есть), а снова пробовал реализовать свою идею.

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

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group