Автор Тема: Сортировка вставками  (Прочитано 269 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Космич

  • Активный участник
  • ***
  • Сообщений: 194
    • Просмотр профиля
Сортировка вставками
« : Май 15, 2019, 11:57:48 pm »
после того как элементы массива под индексами 0 и 1 меняются местами, $k становится = 0, но выхода и вложенного цикла не происходит. Почему так происходит, где я накосячил? 

Код: Clickermann
  1. SUB(_SWAP, $var1, $var2)
  2.   $sub_temp_var = GETVAR($var1)
  3.   SETVAR($var1, GETVAR($var2))
  4.   SETVAR($var2, $sub_temp_var)
  5. END_SUB
  6.  

Код: Clickermann
  1. #include "data\include\swap.cms"
  2.  
  3. $arr[0] = 9
  4. $arr[1] = 8
  5. $arr[2] = 3
  6. $arr[3] = 4
  7.  
  8. FOR($i = 1, $i < ARRSIZE($arr))
  9.   FOR($k = $i, ( ($k > 0) and ($arr[$k-1] > $arr[$k]) ), - 1)
  10.      _SWAP(STRCONCAT("$arr[", GETVAR("$k") - 1, "]"), STRCONCAT("$arr[", GETVAR("$k"),"]") )
  11.   END_CYC
  12. END_CYC
  13.  
  14. FOR($i = 0, $i < ARRSIZE($arr))
  15.   PRINT($arr[$i])
  16. END_CYC
  17.  
  18. halt

P.S. А вот даже не знаю, я косяка не вижу и на ++ всё работает  :(
« Последнее редактирование: Май 16, 2019, 01:07:49 am от Космич »

Oraven

  • Супермодератор
  • Герой форума
  • *
  • Сообщений: 3577
  • Котэ
    • Просмотр профиля
Re: Сортировка вставками
« Ответ #1 : Май 16, 2019, 07:36:06 am »
SETVAR и GETVAR не работают с массивами.

Если я все правильно понял
Код: Clickermann
  1. $arr[0] = 9
  2. $arr[1] = 8
  3. $arr[2] = 3
  4. $arr[3] = 4
  5.  
  6. FOR($i = 1, $i < ARRSIZE($arr),2)
  7.   IF($arr[$i-1] > $arr[$i])
  8.      $temp = $arr[$i - 1]
  9.      $arr[$i - 1] = $arr[$i]
  10.      $arr[$i] = $temp
  11.   END_IF
  12. END_CYC
  13.  
  14. FOR($i = 0, $i < ARRSIZE($arr))
  15.   PRINT($arr[$i])
  16. END_CYC
  17.  
  18. halt

Лог:
08:33:15 8
08:33:15 9
08:33:15 3
08:33:15 4

dramster

  • Герой форума
  • *****
  • Сообщений: 956
    • Просмотр профиля
Re: Сортировка вставками
« Ответ #2 : Май 16, 2019, 08:53:22 am »
SETVAR и GETVAR не работают с массивами.

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

Код: Clickermann
  1. $arr[0] = 9
  2. $arr[1] = 8
  3.  
  4. print(GETVAR("$arr[0]"))    //  тут 9
  5. SETVAR("$arr[0]", GETVAR("$arr[1]"))
  6. print(GETVAR("$arr[0]"))   // тут 8
  7.  
  8. halt


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

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

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

Код: Clickermann
  1.   FOR($k = $i, $k > 0, - 1)
  2.  
  3.      if ($arr[$k-1] > $arr[$k])
  4.  
  5.         _SWAP(STRCONCAT("$arr[", GETVAR("$k") - 1, "]"), STRCONCAT("$arr[", GETVAR("$k"),"]") )
  6.  
  7.      end_if
  8.  
  9.   END_CYC

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

Код: Clickermann
  1. SUB(_SWAP, $var1, $var2)
  2.   $sub_temp_var = GETVAR($var1)
  3.   SETVAR($var1, GETVAR($var2))
  4.   SETVAR($var2, $sub_temp_var)
  5. END_SUB
  6.  
  7.  
  8. $arr[0] = 9
  9. $arr[1] = 8
  10. $arr[2] = 3
  11. $arr[3] = 4
  12.  
  13.  
  14.  
  15.  
  16. FOR($i = 1, $i < ARRSIZE($arr))
  17.  
  18.   FOR($k = $i, $k > 0, - 1)
  19.  
  20.      if ($arr[$k-1] > $arr[$k])
  21.  
  22.         _SWAP(STRCONCAT("$arr[", $k - 1, "]"), STRCONCAT("$arr[", $k,"]") )
  23.  
  24.  
  25.      end_if
  26.  
  27.   END_CYC
  28. END_CYC
  29.  
  30. FOR($i = 0, $i < ARRSIZE($arr))
  31.   PRINT($arr[$i])
  32. END_CYC
  33.  
  34. halt

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

Код: Clickermann
  1. $arr[0] = 9
  2. $arr[1] = 8
  3. $arr[2] = 3
  4. $arr[3] = 4
  5.  
  6.  
  7. FOR($i = 1, $i < ARRSIZE($arr))
  8.  
  9.   FOR($k = $i, $k > 0, - 1)
  10.  
  11.      if ($arr[$k-1] > $arr[$k])
  12.  
  13.         $temp_var = $arr[$k - 1]
  14.         $arr[$k - 1] = $arr[$k]
  15.         $arr[$k] =  $temp_var
  16.  
  17.      end_if
  18.  
  19.   END_CYC
  20. END_CYC
  21.  
  22. FOR($i = 0, $i < ARRSIZE($arr))
  23.   PRINT($arr[$i])
  24. END_CYC
  25.  
  26. halt

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

dramster

  • Герой форума
  • *****
  • Сообщений: 956
    • Просмотр профиля
Re: Сортировка вставками
« Ответ #3 : Май 16, 2019, 09:09:25 am »
https://infostart.ru/public/204320/ - ссылка популярных алгоритмов сортировок массива.

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

Так он выглядит на кликермане:
Код: Clickermann
  1. FOR($i = 0, $i < ARRSIZE($arr))
  2.  
  3.   FOR($j = 0, $j < ARRSIZE($arr) - $i - 1)
  4.  
  5.      if ($arr[$j] > $arr[$j + 1])
  6.  
  7.         $temp_var = $arr[$j]
  8.         $arr[$j] = $arr[$j + 1]
  9.         $arr[$j + 1] =  $temp_var
  10.  
  11.      end_if
  12.  
  13.   END_CYC
  14. END_CYC

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

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

Космич

  • Активный участник
  • ***
  • Сообщений: 194
    • Просмотр профиля
Re: Сортировка вставками
« Ответ #4 : Май 16, 2019, 11:35:43 am »
Ну да, можно вынести условие в тело цикла. Но опять же, почему после проверки $k > 0 продолжается проверка условия выхода из цикла? или всё как то по другому работает?

Oraven

  • Супермодератор
  • Герой форума
  • *
  • Сообщений: 3577
  • Котэ
    • Просмотр профиля
Re: Сортировка вставками
« Ответ #5 : Май 16, 2019, 12:43:28 pm »
Ну да, можно вынести условие в тело цикла. Но опять же, почему после проверки $k > 0 продолжается проверка условия выхода из цикла? или всё как то по другому работает?

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

Vint

  • Супермодератор
  • Герой форума
  • *
  • Сообщений: 3301
  • Лечу куда хочу. cman 4.13.014x32, W10, W7
    • Просмотр профиля
Re: Сортировка вставками
« Ответ #6 : Май 16, 2019, 01:05:51 pm »
Далее берем готовую процедуру сортировки ARRSORT, и она сортирует нам массив... только вот засада, ее так и не починили  :-\, массив сортируется только как строковый.
Почему не работает? Работает.
Код: Clickermann
  1. #define @CRLF:STRCONCAT(char(13),char(10))
  2.  
  3. PRINT("Как числовой")
  4. STRSEPARATE("10,1,300,4,5,0,427,78,34", ",", $arr)
  5. ARRSORT($arr, 0)
  6. FOR($i = 0, $i < ARRSIZE($arr))
  7.    PRINT($arr[$i])
  8. END_CYC
  9. PRINT("---------------------------------", @CRLF)
  10.  
  11. UNDEFINE($arr)
  12.  
  13. PRINT("Как строковый")
  14. STRSEPARATE("10,1,300,4,5,0,427,78,34", ",", $arr)
  15. ARRSORT($arr, 1)
  16. FOR($i = 0, $i < ARRSIZE($arr))
  17.    PRINT($arr[$i])
  18. END_CYC
  19. PRINT("---------------------------------", @CRLF)
  20.  
  21. HALT

Цитировать
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 ---------------------------------


Космич

  • Активный участник
  • ***
  • Сообщений: 194
    • Просмотр профиля
Re: Сортировка вставками
« Ответ #7 : Май 16, 2019, 02:07:15 pm »
Ну да, можно вынести условие в тело цикла. Но опять же, почему после проверки $k > 0 продолжается проверка условия выхода из цикла? или всё как то по другому работает?

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

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

Код: Clickermann
  1. FOR($k = $i, ( ($k > 0) and ($arr[$k-1] > $arr[$k]) ), - 1)

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

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

Не знаю, насколько корректно сравнивать верcию cm 4.14 и C++ 11, но код алгоритма одинаковый и скрин я приложу.
« Последнее редактирование: Май 16, 2019, 02:44:53 pm от Космич »

Vint

  • Супермодератор
  • Герой форума
  • *
  • Сообщений: 3301
  • Лечу куда хочу. cman 4.13.014x32, W10, W7
    • Просмотр профиля
Re: Сортировка вставками
« Ответ #8 : Май 16, 2019, 02:57:13 pm »
Кажется я понял.

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


Космич

  • Активный участник
  • ***
  • Сообщений: 194
    • Просмотр профиля
Re: Сортировка вставками
« Ответ #9 : Май 16, 2019, 03:12:53 pm »
Пробовал, а так же пробовал перестановку условий и скобок приоритета, но ничего не изменилось)

Проблема конкретно в составном условии с использованием массива, причём это касается не только оператора FOR но и WHILE тоже

Vint

  • Супермодератор
  • Герой форума
  • *
  • Сообщений: 3301
  • Лечу куда хочу. cman 4.13.014x32, W10, W7
    • Просмотр профиля
Re: Сортировка вставками
« Ответ #10 : Май 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++ проверка
Код: Clickermann
  1. (($k > 0) and ($arr[$k-1] > $arr[$k]))
вычислит только ($k > 0) и не будет обращаться к неправильным элементам массива.
Кликер сначала вычислит все операнды... точнее попытается, индекс то выходит уже неправильный.

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

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


Космич

  • Активный участник
  • ***
  • Сообщений: 194
    • Просмотр профиля
Re: Сортировка вставками
« Ответ #11 : Май 16, 2019, 04:03:56 pm »
Вот теперь всё, огромное спасибо. Я то думал, что это ошибка и так быть не должно.
« Последнее редактирование: Май 16, 2019, 08:45:15 pm от Космич »