Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Сортировка.  (Прочитано 19484 раз)
0 Пользователей и 1 Гость смотрят эту тему.
IgnisFatuus
Постоялец

ru
Offline Offline

« : 02-07-2012 07:13 » 

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

Бьюсь с кодом - не понимаю его. Кто-то может разложить по полочкам?


Код: (C++)
#include <iostream>
using namespace std;

int main()
{
  const int N = 10;          
  int B,i,j,k;
  int A[N],  b;        

  printf("Vvod massiva: ");
  for (i = 0; i < N; i++)
  {
    printf("A[%d]=",i);      
    scanf("%d",&A[i]);      
  }

  for (i = 1; i < N; i++)
  {
    B = A[i];
    for (j = 0; j < i; j++)
      if (B < A[j])
      {
        for (k = i - 1; k < j; k--)
          A[k + 1] = A[k];
      }
     A[i] = B;
    }
  printf("Sort Massiv:");
  for ( i = 0; i < N; i++)
    printf("%i\n",A[i]);
  system ("PAUSE");
  return 0;
}

Понятно, что вводим с клавы массив... А дальше? Теряюсь в циклах.

Добавлено через 10 минут и 12 секунд:
Кстати, почему сортировка начинается с 1 элемента а не с нулевого?  -

Код: (C++)
for (i = 1; i < N; i++)
{
« Последнее редактирование: 02-07-2012 07:23 от IgnisFatuus » Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 02-07-2012 08:10 » 

А ты догадайся Ага

Код: (C++)
  1.   for (i = 1; i < N; i++)
  2.   {
  3.     B = A[i];
  4.     for (j = 0; j < i; j++)
  5.       if (B < A[j])
  6.       {
  7.         for (k = i - 1; k < j; k--)
  8.           A[k + 1] = A[k];
  9.       }
  10.      A[i] = B;
  11.     }
Кстати, почему сортировка начинается с 1 элемента а не с нулевого?  -
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
IgnisFatuus
Постоялец

ru
Offline Offline

« Ответ #2 : 02-07-2012 08:53 » 

Кстати, сортировка в указанном коде не работает...
Записан
Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #3 : 02-07-2012 08:56 » 

IgnisFatuus, погоди, если задание - написать сортировку, то почему ты пытаешься разобраться в непонятном тебе коде? Пиши свой, понятный и работающий Улыбаюсь
Записан
IgnisFatuus
Постоялец

ru
Offline Offline

« Ответ #4 : 02-07-2012 09:37 » 

Я не могу разобрать концепцию. Как и что делается? Ну вот нашел я минимальное значение. А что дальше?
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #5 : 02-07-2012 09:46 » 

IgnisFatuus, для понимания концепции не нужен код, а нужна наглядность. Возьми 5 предметов (хоть ручек, хоть спичек, хоть жёлтых бумажек с цифрами), придумай для них порядок, разложи с нарушением порядка, а затем восстанови порядок по правилу сортировки выбором.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
IgnisFatuus
Постоялец

ru
Offline Offline

« Ответ #6 : 02-07-2012 09:55 » 

Ну вот разложил. 5 бумажек с номерами {1, 3 , 5, 2, 4}.

Надо соответственно 1, 2, 3, 4, 5.

вот мои действия. ->

Код: (C++)
for (i = 1; i < N; i++)
  {

беру второй элемент массива, т.е. 3.

Код: (C++)
B = A[i];
помещаю во временную переменную.

Код: (C++)
for (j = 0; j < i; j++)

Для этой переменной - беру первый элемент массива, т.е. 1.

Код: (C++)
if (B < A[j])

сравниваю его с переменной В. ( т.е. второй элемент с первым).

Если В меньше чем 1-й элемент => он не на своем месте и мы

Код: (C++)
for (k = i - 1; k < j; k--)
          A[k + 1] = A[k];
      }
     A[i] = B;

Вот что это? Я хз....
Записан
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #7 : 02-07-2012 10:06 » 

IgnisFatuus, ты читаешь что тебе пишут? Причем здесь код? Или код может твои бумажки сортировать? Какие переменные с бумажками? Ясно же сказано:

восстанови порядок по правилу сортировки выбором.

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

Да, и в задании у тебя стоит: "сортирует по убыванию". Значит как должен отсортированный массив выглядеть?

« Последнее редактирование: 02-07-2012 17:09 от Джон » Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
IgnisFatuus
Постоялец

ru
Offline Offline

« Ответ #8 : 02-07-2012 10:22 » 

Хорошо. 1, 3, 5, 2, 4.

Надо выстроить по убыванию.
Нахожу максимальный элемент массива. Это бумажка с надписью 5. Меняю ее местами с бумажкой №1.

Ищу максимальный элемент из оставшихся четырех. И далее по тексту. Скажу честно. Не могу понять как это воплотить в жизни ( в коде). Могу с легкостью найти максимальный. А как их местами поменять? Как найти следующий максимальный? Как отбросить найденный прошлый максимальный?
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #9 : 02-07-2012 10:28 » 

IgnisFatuus, не можешь понять потому, что не пытаешься. Пример: "Нахожу максимальный элемент массива.". Как нашел? Рассказывай элементарными шагами.

Запомни: машина не может типа посмотреть и типа увидеть. Она вообще слепая: ткнет пальцем в "бумажку" и только тогда читает, что на ней написано.
Также полезно помнить: машина тупая. Она ничего не умеет. Она ничего не знает. Она следует четким и простым инструкциям.
« Последнее редактирование: 02-07-2012 10:29 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
IgnisFatuus
Постоялец

ru
Offline Offline

« Ответ #10 : 02-07-2012 10:41 » 

Вы правы, я не пытаюсь. Я делаю. Стараюсь как могу. Без преувеличения. И Благодарен, что Вы согласились помочь.
Итак.

Нахожу максимальный элемент массива.

Беру первую бумажку - [1] и сравниваю со второй, затем с третьей, четвертой, пятой. Если первая бумажка больше их всех, то это максимальный элемент. Если нет - берем вторую бумажку [3] и продолжаем. Верно?


Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #11 : 02-07-2012 11:21 » 

Нет, не верно.

Входные условия: Пять бумажек, расположенных справа на лево. На бумажках написаны произвольные натуральные числа.
 

Выполнение:
1. Палец указывает на первую бумажку. Запоминаем число ноль.
2. Читаем бумажку под пальцем.
3. Сравниваем число на бумажке с числом в памяти. Если номер на бумажке больше номера в памяти, то запоминаем значение на бумажке.
4. Переводим палец на следующую бумажку. Если бумажек больше нет, то поиск завершен. Иначе переходим на пункт 2.

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


Для закрепления понимания несколько раз проделай описанные шаги с реальными бумажками.
« Последнее редактирование: 02-07-2012 11:26 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
IgnisFatuus
Постоялец

ru
Offline Offline

« Ответ #12 : 02-07-2012 11:35 » 

С этим разобрался. Помогло. Каков следующий шаг в сортировке?
Записан
Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #13 : 02-07-2012 11:38 » 

IgnisFatuus, следующий шаг - обменять местами бумажку с максимумом и ту, где этот максимум должен в итоге оказаться (если это не одно и то же). Поскольку нужные позиции нам уже известны, это не должно представлять сложность.
Записан
IgnisFatuus
Постоялец

ru
Offline Offline

« Ответ #14 : 02-07-2012 11:43 » 

И как это реализовать в коде?
Записан
Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #15 : 02-07-2012 11:48 » 

Встречный вопрос: а как это реализуется на бумажках? В смысле, если помнить о том, что мы всю интересующую нас информацию должны где-то хранить (для компьютера - в переменных): индекс начального (сортируемого) элемента, его значение, индекс найденного максимума, его значение, -- какую команду мы должны отдать человеку/компьютеру, чтобы поменять эти бумажки/значения местами? Представь, что человек(компьютер) совсем несмышлёный, умеет находить нужную бумажку только по её порядковому номеру (в "массиве").
Записан
IgnisFatuus
Постоялец

ru
Offline Offline

« Ответ #16 : 02-07-2012 11:55 » 

Нужна переменная. Точнее временная переменная, в которую будет записываться наибольшее (на данный момент ) значение.

Добавлено через 37 минут и 42 секунды:
Взял код -
Код: (C++)
#include <iostream>
using namespace std;
#include <stdlib>

//---------------------------------------------------------------------------

int main()
{
const int MAX_ARRAY = 10;
int array [MAX_ARRAY];
int i = 0, j = 0, min = 0;
for (i = 0; i < MAX_ARRAY; i++) //заполняем с клавиатуры
{
cin >> array[i];
}

for (i = 0; i < MAX_ARRAY; i++) //сортируем массив
{
min = i;
for (j = i + 1; j < MAX_ARRAY; j++)
{
 if (array[j] < array[min])
 {
min = j;
 }
}
int temp = array[min];
array[min] = array[i];
array[i] = temp;
}

for(i = 0; i < MAX_ARRAY; i++) //выводим массив
{
cout << array[i] << ' ';
}
cout << endl;
system("pause");
return 0;
}
//---------------------------------------------------------------------------

Пробежался по нему с ручкой и листочком, проследил циклы. Если я все правильно понял, то массив (скажем из 4-х чисел - {6, 3, 5, 2} будет меняться вот так -

Начало - {6,3,5,2}
{3,6,5,2}
{2,6,5,3}
Затем новый цикл
{2,5,6,3}
{2,3,5,6}

Или мне опять идти курить логику?  Меня одолевают смутные сомнения
« Последнее редактирование: 02-07-2012 12:33 от IgnisFatuus » Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #17 : 02-07-2012 12:44 » 

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

Зачем смотреть чужой код?

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

1) Написать чтение чисел в массив и вывод массива на экран. Эта пара действий создаст основу для написания сортировки, а заодно позволит убедиться, что основа создана правильно: числа в массив попадают, попадают в него правильно, выводятся тоже правильно.

2) Написать поиск индекса максимального числа в части массива между элементами n и m, где n <= m, n и m от 0 до N-1, где N - размер массива. Временно выведи на экран найденный индекс, чтобы убедиться, что поиск работает правильно. Вынеси решение в отдельную функцию, подумай о её параметрах.

3) Написать обмен двух чисел в двух переменных. Тоже подумай, как это проверить и вынести в отдельную функцию.

4) Соединить пункты 2 и 3 в цикле, осуществляющему сортировку выбором.

Всё это называется декомпозицией задачи на подзадачи. Слона кушают по частям.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #18 : 02-07-2012 12:45 » 

Если во втором цикле {2,5,6,3} - это опечатка, и должно быть {2,6,5,3} - то всё остальное правильно.

Dimka, нет, если там описаны только 2 итерации в духе было-стало, то всё правильно, выбор, а не пузырёк.

(да что такое, сначала правильно подумал, потом сбился на Димкином комментарии, потом опять сбился Улыбаюсь)
« Последнее редактирование: 02-07-2012 12:48 от Вад » Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #19 : 02-07-2012 15:26 » 

Вад, да не может это быть выбором. В выборе нужно после начала найти из {3,5,2} минимум и поменять местами с 6, что немедленно даст конец работы. Пузырёк, впрочем, двигал бы 6 в конец с каждым шагом. Ну тогда это сортировка обменом. Сначала он 3 и 6 поменял местами, затем 2 и 3.

В любом случае не выбор, и порядок не в ту сторону.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Вад
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #20 : 02-07-2012 16:06 » 

Dimka, а ты код посмотри - именно это там и делается, выбирается минимум и обменивается с сортируемой позицией. Просто IgnisFatuus это в своём описании упустил, а то, что в начале итераций значится {3,6,5,2} и {2,5,6,3} соответственно - в этом я вижу опечатку от спешки. Если не опечатка - то, конечно, да, ошибка имеет место. Но код изначально для сортировки выбором.
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #21 : 02-07-2012 16:22 » 

Вад, я же говорил, что код не смотрел. Нет смысла смотреть код, если это не его код. Он всё равно его не понимает. О чём и тема.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #22 : 02-07-2012 17:23 » new

Блин, надо запретить код в этой теме. Ключевая фраза:

Я не могу разобрать концепцию. Как и что делается? Ну вот нашел я минимальное значение. А что дальше?

IgnisFatuus, то что ты обозвал концепцией, на самом деле называется неприличным словом "алгоритм", что не самом деле есть описание последовательности действий, приводящих к желаемому результату. Компьютер (компилятор) - тупой. Ему надо всё разжевать, разложить по полочкам. Для этого ты сам сначала должен всё чётко представлять, что от тебя на данном этапе и требуется. Забудь о коде, представь, что ты объясняешь это не компьютеру, а 5-ти летнему пацану, которой только и понимает, что такое меньше, больше и равно. Или посади рядом с собой кто под руку подвернётся, высыпи горсть мелочи и покажи ему как её можно отсортировать.Расскажи (напиши) словами. А уж написать код, имея готовый алгоритм - дело техники. Ты сам это увидишь и, что более важно, поймёшь и почувствуешь. И в будущем, ты, прежде чем написать хоть одну букву кода, сначала разберёшься с задачей на уровне "бумажек".

зы Такой вопрос. Как ты уже понял существуют различные алгоритмы (будем называть вещи своими именами) сортировки. Ты с ними знаком? Что значит сортировка методом прямого выбора?
« Последнее редактирование: 02-07-2012 17:26 от Джон » Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
IgnisFatuus
Постоялец

ru
Offline Offline

« Ответ #23 : 03-07-2012 05:38 » 

Вчера разобрал с бумажечкой код более детально. Остались пара моментов, но в целом я собой доволен. Наконец-то понял. Сейчас намерен сесть и написать самостоятельно. Напишу - скину - оцените.

Добавлено через 20 минут и 47 секунд:
Код: (C++)
#include <iostream>
using namespace std;

int main(){
    int N=4;
    int array [N];
    int i, j, temp, min=0;
   
    for (i=0; i<N; i++){
    cout << "Vvedite massiv : \n";
    cin >> array [i];}
   
    cout << "Sortirovka..... \n";
   
    for (i = 0; i<N; i++){
        min=i;
        for (j = i+1; j< N; j++){
            if (array[j]<array[min])min=j;
        }
        temp = array[min];
        array[min] = array[i];
        array[i]=temp;
    }
    for (i=0; i<N; i++){
        cout << "Array  = "<< array[i] << "\n";
    }
   
    system ("PAUSE");
   
}

Как-то так.
« Последнее редактирование: 03-07-2012 05:59 от IgnisFatuus » Записан
Sla
Модератор

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #24 : 03-07-2012 06:02 » 

Прикольно получилось
Обмен происходит всегда.
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines