def min_max(A, l, r):
if r-l>1:
min = min_i(A, l, r)
swap(A, l, min)
max = max_i(A, l, r)
swap(A, r, max)
min_max(A, l+1, r-1)
elif r-l==1:
if A[l]>A[r]:
swap(A, l, r)
Как вы думаете, этот алгоритм сработает для всех инпутов?
Что такое min_i, max_i, swap?
swap меняет местами два элемента по заданным индексам.
min_i, max_i возвращает индекс минимального и максимального элемента в заданном промежутке.
Цитата: RawonaM от ноября 4, 2011, 19:04
min_i, max_i возвращает индекс минимального и максимального элемента в заданном промежутке.
Тормоз же.
Кто/что тормоз?
min_i, max_i.
Это не имеет значения. Алгоритм рабочий, думаете?
В случае, когда массив из одного элемента состоит r-l=0, а такой вариант не предусмотрен.
Предусмотрен. Массив из одного элемента уже упорядочен.
Цитата: RawonaM от ноября 4, 2011, 19:17
Предусмотрен. Массив из одного элемента уже упорядочен.
Программа не знает, какой ей массив дают, отсортированный или нет. Или это программа для массивов длины >=2? Тогда надо вставить проверку длины массива.
И потом, если число элементов нечётное, то настанет момент, когда сортируемый участок сузится до одного элемента, и что с ним делать непонятно.
Цитата: orang_baik от ноября 4, 2011, 19:19
Цитата: RawonaM от ноября 4, 2011, 19:17Предусмотрен. Массив из одного элемента уже упорядочен.
Программа не знает, какой ей массив дают, отсортированный или нет.
orang_baik, массив из одного элемента ВСЕГДА отсортирован, этот случай проверять не нужно.
Попробуйте добавить случай r-l=0, какие действия вы хотите делать?
Цитата: RawonaM от ноября 4, 2011, 19:09
Это не имеет значения. Алгоритм рабочий, думаете?
Скорее всего, рабочий, но это не имеет значения - он тормозной же.
Если ничего не упустил, то должно работать.
Цитата: RawonaM от ноября 4, 2011, 19:27
Цитата: orang_baik от ноября 4, 2011, 19:19
Цитата: RawonaM от ноября 4, 2011, 19:17Предусмотрен. Массив из одного элемента уже упорядочен.
Программа не знает, какой ей массив дают, отсортированный или нет.
orang_baik, массив из одного элемента ВСЕГДА отсортирован, этот случай проверять не нужно.
Попробуйте добавить случай r-l=0, какие действия вы хотите делать?
Завершить выполнение программы.
Если массив из трёх элементов состоит.
Запустили min_max(A,1,3),3-1>1, выполняется первая ветка и запускается min_max(A,2,2),2-2=0 и что дальше?
Цитата: Alone Coder от ноября 4, 2011, 19:30
Цитата: RawonaM от ноября 4, 2011, 19:09Это не имеет значения. Алгоритм рабочий, думаете?
Скорее всего, рабочий
Мне вот тоже так кажется.
Цитата: orang_baik от ноября 4, 2011, 19:33
Завершить выполнение программы.
Это то, что и просходит.
Цитата: orang_baik от ноября 4, 2011, 19:33
Запустили min_max(A,1,3),3-1>1, выполняется первая ветка и запускается min_max(A,2,2),2-2=0 и что дальше?
Все, сортировка закончена.
Если эта функция\процедура не должна ничего возвращать, тогда ничего не надо.
С помощью swap она изменяет входной массив, зачем возвращать?
Цитата: arseniiv от ноября 5, 2011, 17:12
С помощью swap она изменяет входной массив, зачем возвращать?
Изменит только в пределах самой себя. В основном теле программы ничего не изменится.
Если передача параметров по референсу, то изменится.
В следущий раз буду выкладывать псевдокод, чтобы не было тенденции конкретную имплементацию обсуждать. :)
Просто раз я уже на питоне накалякал, так решил так и выложить.
Цитата: RawonaM от ноября 5, 2011, 17:34
Если передача параметров по референсу, то изменится.
По кому? :what:
Цитата: RawonaM от ноября 5, 2011, 17:34
В следущий раз буду выкладывать псевдокод, чтобы не было тенденции конкретную имплементацию обсуждать. :)
В следующий раз внятно описывайте, что за переменные используются, или давайте им говорящие имена.
А то я прочитал переменные как «А, И, Р», и долго не мог врубиться, что они суть такое.
Цитата: Hellerick от ноября 5, 2011, 17:39
В следующий раз внятно описывайте, что за переменные используются, или давайте им говорящие имена.
А то я прочитал переменные как «А, И, Р», и долго не мог врубиться, что они суть такое.
В этом был и прикол, так у меня в задании и дано.