Сортировка.

[IgnisFatuus]

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

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

Код: (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++)
{

[RXL]

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

Код: (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]

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

[Вад]

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

[IgnisFatuus]

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

[Dimka]

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

[IgnisFatuus]

Ну вот разложил. 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;

Вот что это? Я хз....

[Джон]

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

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

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

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

[IgnisFatuus]

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

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

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

[RXL]

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

Запомни: машина не может типа посмотреть и типа увидеть. Она вообще слепая: ткнет пальцем в "бумажку" и только тогда читает, что на ней написано.
Также полезно помнить: машина тупая. Она ничего не умеет. Она ничего не знает. Она следует четким и простым инструкциям.

[IgnisFatuus]

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

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

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

[RXL]

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

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

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

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


Для закрепления понимания несколько раз проделай описанные шаги с реальными бумажками.

[IgnisFatuus]

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

[Вад]

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

[IgnisFatuus]

И как это реализовать в коде?

[Вад]

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

[IgnisFatuus]

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

Добавлено через 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}

Или мне опять идти курить логику? 

[Dimka]

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

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

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

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

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

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

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

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

[Вад]

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

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

(да что такое, сначала правильно подумал, потом сбился на Димкином комментарии, потом опять сбился )

[Dimka]

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

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

[Вад]

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

[Dimka]

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

[Джон]

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

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

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

зы Такой вопрос. Как ты уже понял существуют различные алгоритмы (будем называть вещи своими именами) сортировки. Ты с ними знаком? Что значит сортировка методом прямого выбора?

[IgnisFatuus]

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

Добавлено через 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");
   
}

Как-то так.

[Sla]

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