Author Topic: Сортировка вставками  (Read 2381 times)

0 Members and 1 Guest are viewing this topic.

Космич

  • Активный участник
  • ***
  • Posts: 265
    • View Profile
Сортировка вставками
« on: May 15, 2019, 11:57:48 PM »
после того как элементы массива под индексами 0 и 1 меняются местами, $k становится = 0, но выхода и вложенного цикла не происходит. Почему так происходит, где я накосячил? 

Code: (clickermann) [Select]
SUB(_SWAP, $var1, $var2)
   $sub_temp_var = GETVAR($var1)
   SETVAR($var1, GETVAR($var2))
   SETVAR($var2, $sub_temp_var)
END_SUB

Code: (clickermann) [Select]
#include "data\include\swap.cms"

$arr[0] = 9
$arr[1] = 8
$arr[2] = 3
$arr[3] = 4

FOR($i = 1, $i < ARRSIZE($arr))
   FOR($k = $i, ( ($k > 0) and ($arr[$k-1] > $arr[$k]) ), - 1)
      _SWAP(STRCONCAT("$arr[", GETVAR("$k") - 1, "]"), STRCONCAT("$arr[", GETVAR("$k"),"]") )
   END_CYC
END_CYC

FOR($i = 0, $i < ARRSIZE($arr))
   PRINT($arr[$i])
END_CYC

halt

P.S. А вот даже не знаю, я косяка не вижу и на ++ всё работает  :(
« Last Edit: May 16, 2019, 01:07:49 AM by Космич »
«Иногда ты ваяешь до тех пор, пока до тебя не дойдёт, что именно ты делаешь.»

Oraven

  • Супермодератор
  • Герой форума
  • *
  • Posts: 3685
  • Котэ
    • View Profile
Re: Сортировка вставками
« Reply #1 on: May 16, 2019, 07:36:06 AM »
SETVAR и GETVAR не работают с массивами.

Если я все правильно понял
Code: (clickermann) [Select]
$arr[0] = 9
$arr[1] = 8
$arr[2] = 3
$arr[3] = 4

FOR($i = 1, $i < ARRSIZE($arr),2)
   IF($arr[$i-1] > $arr[$i])
      $temp = $arr[$i - 1]
      $arr[$i - 1] = $arr[$i]
      $arr[$i] = $temp
   END_IF
END_CYC

FOR($i = 0, $i < ARRSIZE($arr))
   PRINT($arr[$i])
END_CYC

halt

Лог:
Code: [Select]
08:33:15 8
08:33:15 9
08:33:15 3
08:33:15 4

dramster

  • Герой форума
  • *****
  • Posts: 1134
    • View Profile
Re: Сортировка вставками
« Reply #2 on: May 16, 2019, 08:53:22 AM »
SETVAR и GETVAR не работают с массивами.

В 4.14 - работают.

Code: (clickermann) [Select]
$arr[0] = 9
$arr[1] = 8

print(GETVAR("$arr[0]"))    //  тут 9
SETVAR("$arr[0]", GETVAR("$arr[1]"))
print(GETVAR("$arr[0]"))   // тут 8

halt


после того как элементы массива под индексами 0 и 1 меняются местами, $k становится = 0, но выхода и вложенного цикла не происходит. Почему так происходит, где я накосячил? 

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

Главная ошибка, это обращение к отрицательному элементу массива в FOR($k = $i, ( ($k > 0) and ($arr[$k-1] > $arr[$k]) ), - 1). Для избежания ошибки, выносим условие $arr[$k-1] > $arr[$k] внутрь цикла. Получается так:

Code: (clickermann) [Select]
   FOR($k = $i, $k > 0, - 1)
     
      if ($arr[$k-1] > $arr[$k])
         
         _SWAP(STRCONCAT("$arr[", GETVAR("$k") - 1, "]"), STRCONCAT("$arr[", GETVAR("$k"),"]") )
         
      end_if
     
   END_CYC

Какой смысл возвращать значение переменной $k по ее имени GETVAR("$k")? Берем значение сразу напрямую. В итоге твой рабочий вариант выглядит так:

Code: (clickermann) [Select]
SUB(_SWAP, $var1, $var2)
   $sub_temp_var = GETVAR($var1)
   SETVAR($var1, GETVAR($var2))
   SETVAR($var2, $sub_temp_var)
END_SUB


$arr[0] = 9
$arr[1] = 8
$arr[2] = 3
$arr[3] = 4




FOR($i = 1, $i < ARRSIZE($arr))
   
   FOR($k = $i, $k > 0, - 1)
     
      if ($arr[$k-1] > $arr[$k])
         
         _SWAP(STRCONCAT("$arr[", $k - 1, "]"), STRCONCAT("$arr[", $k,"]") )
         
         
      end_if
     
   END_CYC
END_CYC

FOR($i = 0, $i < ARRSIZE($arr))
   PRINT($arr[$i])
END_CYC

halt

Далее убираем эти все гетвары и сетвары и получаем тот же результат:

Code: (clickermann) [Select]
$arr[0] = 9
$arr[1] = 8
$arr[2] = 3
$arr[3] = 4


FOR($i = 1, $i < ARRSIZE($arr))
   
   FOR($k = $i, $k > 0, - 1)
     
      if ($arr[$k-1] > $arr[$k])

         $temp_var = $arr[$k - 1]
         $arr[$k - 1] = $arr[$k]
         $arr[$k] =  $temp_var
         
      end_if
     
   END_CYC
END_CYC

FOR($i = 0, $i < ARRSIZE($arr))
   PRINT($arr[$i])
END_CYC

halt

Далее берем готовую процедуру сортировки ARRSORT, и она сортирует нам массив... только вот засада, ее так и не починили  :-\, массив сортируется только как строковый.
 

dramster

  • Герой форума
  • *****
  • Posts: 1134
    • View Profile
Re: Сортировка вставками
« Reply #3 on: May 16, 2019, 09:09:25 AM »
https://infostart.ru/public/204320/ - ссылка популярных алгоритмов сортировок массива.

Твой вариант - немного измененный алгоритм сортировки пузырьком:
Quote
Функция СортировкаПузырьком(Знач Массив)
   
    Для i = 0 По Массив.ВГраница() Цикл
        Для j = 0 ПО Массив.Вграница() - i - 1 Цикл
            Если Массив[j] > Массив[j + 1] Тогда
                Замена = Массив[j];
                Массив[j] = Массив[j + 1];
                Массив[j + 1] = Замена;
            КонецЕсли;           
        КонецЦикла;       
    КонецЦикла;   
    Возврат Массив;   
КонецФункции

Так он выглядит на кликермане:
Code: (clickermann) [Select]
FOR($i = 0, $i < ARRSIZE($arr))
 
   FOR($j = 0, $j < ARRSIZE($arr) - $i - 1)
 
      if ($arr[$j] > $arr[$j + 1])
 
         $temp_var = $arr[$j]
         $arr[$j] = $arr[$j + 1]
         $arr[$j + 1] =  $temp_var
 
      end_if
 
   END_CYC
END_CYC

Добавлено
А не, ВРУ  :( . Ты ж сам написал "Сортировка вставками", а я не обратил внимания. И да, такой алгорит тоже есть (они все немного схожи  :D):

Quote
Функция СортировкаВставками(Знач Массив)
   
    Для i = 0 По Массив.ВГраница()-1 Цикл           
        Ключ = i + 1;
        Замена = Массив[Ключ];
        j = i + 1;
        Пока j > 0 И Замена < Массив[j - 1] Цикл
            Массив[j] = Массив[j - 1];
            Замена = j - 1;
            Ключ = j - 1;
            j = j - 1;
        КонецЦикла;   
   
        Массив[Ключ] = Замена;
       
    КонецЦикла;   
   
    Возврат Массив;   
   
КонецФункции
« Last Edit: May 16, 2019, 09:27:40 AM by dramster »

Космич

  • Активный участник
  • ***
  • Posts: 265
    • View Profile
Re: Сортировка вставками
« Reply #4 on: May 16, 2019, 11:35:43 AM »
Ну да, можно вынести условие в тело цикла. Но опять же, почему после проверки $k > 0 продолжается проверка условия выхода из цикла? или всё как то по другому работает?
«Иногда ты ваяешь до тех пор, пока до тебя не дойдёт, что именно ты делаешь.»

Oraven

  • Супермодератор
  • Герой форума
  • *
  • Posts: 3685
  • Котэ
    • View Profile
Re: Сортировка вставками
« Reply #5 on: May 16, 2019, 12:43:28 PM »
Ну да, можно вынести условие в тело цикла. Но опять же, почему после проверки $k > 0 продолжается проверка условия выхода из цикла? или всё как то по другому работает?

Твой код даже на 4.14 не выполняется без ошибок. Об чем мы говорим?....

Vint

  • Супермодератор
  • Герой форума
  • *
  • Posts: 3935
  • Лечу куда хочу. cman 4.13.014x32, 4.14.003 W10
    • View Profile
Re: Сортировка вставками
« Reply #6 on: May 16, 2019, 01:05:51 PM »
Далее берем готовую процедуру сортировки ARRSORT, и она сортирует нам массив... только вот засада, ее так и не починили  :-\, массив сортируется только как строковый.
Почему не работает? Работает.
Code: (clickermann) [Select]
#define @CRLF:STRCONCAT(char(13),char(10))

PRINT("Как числовой")
STRSEPARATE("10,1,300,4,5,0,427,78,34", ",", $arr)
ARRSORT($arr, 0)
FOR($i = 0, $i < ARRSIZE($arr))
    PRINT($arr[$i])
END_CYC
PRINT("---------------------------------", @CRLF)

UNDEFINE($arr)

PRINT("Как строковый")
STRSEPARATE("10,1,300,4,5,0,427,78,34", ",", $arr)
ARRSORT($arr, 1)
FOR($i = 0, $i < ARRSIZE($arr))
    PRINT($arr[$i])
END_CYC
PRINT("---------------------------------", @CRLF)

HALT

Quote
13:04:20 Как числовой
13:04:20 0
13:04:20 1
13:04:20 4
13:04:20 5
13:04:20 10
13:04:20 34
13:04:20 78
13:04:20 300
13:04:20 427
13:04:20 ---------------------------------

13:04:20 Как строковый
13:04:20 0
13:04:20 1
13:04:20 10
13:04:20 300
13:04:20 34
13:04:20 4
13:04:21 427
13:04:21 5
13:04:21 78
13:04:21 ---------------------------------


Космич

  • Активный участник
  • ***
  • Posts: 265
    • View Profile
Re: Сортировка вставками
« Reply #7 on: May 16, 2019, 02:07:15 PM »
Ну да, можно вынести условие в тело цикла. Но опять же, почему после проверки $k > 0 продолжается проверка условия выхода из цикла? или всё как то по другому работает?

Твой код даже на 4.14 не выполняется без ошибок. Об чем мы говорим?....

Я сюда пришёл с ошибкой, а не с рабочим кодом. Ошибку я локализовал и описал, но видимо не так детально как это того требовало.  :D
Как видно из кода ниже, когда $k = 0, должен произойти выход из цикла, но его не происходит. Впоследствии, $k передаёт отрицательное значение в индекс массива $arr[$k-1], что и вызывает ошибку.

Code: (clickermann) [Select]
FOR($k = $i, ( ($k > 0) and ($arr[$k-1] > $arr[$k]) ), - 1)
Ошибку можно обойти, как именно это сделать уже написал dramster.
Code: (clickermann) [Select]
FOR($k = $i, $k > 0, - 1)
   IF($arr[$k-1] > $arr[$k])
P.S. dramster, На счёт GETVAR($k) я действительно погорячился, в первом часу ночи шаманил))

Остался только один вопрос, почему происходит проверка всего условия?

Не знаю, насколько корректно сравнивать верcию cm 4.14 и C++ 11, но код алгоритма одинаковый и скрин я приложу.
« Last Edit: May 16, 2019, 02:44:53 PM by Космич »
«Иногда ты ваяешь до тех пор, пока до тебя не дойдёт, что именно ты делаешь.»

Vint

  • Супермодератор
  • Герой форума
  • *
  • Posts: 3935
  • Лечу куда хочу. cman 4.13.014x32, 4.14.003 W10
    • View Profile
Re: Сортировка вставками
« Reply #8 on: May 16, 2019, 02:57:13 PM »
Кажется я понял.

Давно, до какой-то версии and и & были синонимами.
После смены математического модуля и введения битовых операций "and" это битовое AND.
Используй "&".
(ну и "|" "^" тоже)


Космич

  • Активный участник
  • ***
  • Posts: 265
    • View Profile
Re: Сортировка вставками
« Reply #9 on: May 16, 2019, 03:12:53 PM »
Пробовал, а так же пробовал перестановку условий и скобок приоритета, но ничего не изменилось)

Проблема конкретно в составном условии с использованием массива, причём это касается не только оператора FOR но и WHILE тоже
«Иногда ты ваяешь до тех пор, пока до тебя не дойдёт, что именно ты делаешь.»

Vint

  • Супермодератор
  • Герой форума
  • *
  • Posts: 3935
  • Лечу куда хочу. cman 4.13.014x32, 4.14.003 W10
    • View Profile
Re: Сортировка вставками
« Reply #10 on: May 16, 2019, 03:46:12 PM »
Не пойму, ты хочешь знать почему в C++ не так? Ok.

В некоторых языках, используются ленивые проверки условий (python, C++ наверно...).
Простейшие логические операции or и and не вычисляют второй+ операнд, если результат определяется предыдущими.

Есть условие  (A and B and C), если выражение A=False, то нет смысла вычислять B и C, т.к. результат всего выражения всё равно уже False.
В этом случае в выражениях B и C могут быть уже и не вычисляемые значения при этом ошибки не будет.
В интерпретируемых языках там вообще может быть билиберда, лишь бы проверку синтаксиса прошла при запуске.
А в кликермэне нет ленивых вычислений и условий.

Поэтому в C++ проверка
Code: (clickermann) [Select]
(($k > 0) and ($arr[$k-1] > $arr[$k]))вычислит только ($k > 0) и не будет обращаться к неправильным элементам массива.
Кликер сначала вычислит все операнды... точнее попытается, индекс то выходит уже неправильный.

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

Ленивые введены для скорости, а не для игнора ошибок как в задаче, это побочный эффект.
В примере выше в B и C могут быть вызовы функций со сложными ресурсоёмкими вычислениями. Которые сильно нагрузят процессор или выжрут память.
« Last Edit: May 16, 2019, 03:50:03 PM by Vint »


Космич

  • Активный участник
  • ***
  • Posts: 265
    • View Profile
Re: Сортировка вставками
« Reply #11 on: May 16, 2019, 04:03:56 PM »
Вот теперь всё, огромное спасибо. Я то думал, что это ошибка и так быть не должно.
« Last Edit: May 16, 2019, 08:45:15 PM by Космич »
«Иногда ты ваяешь до тех пор, пока до тебя не дойдёт, что именно ты делаешь.»