Лингвофорум

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
Если передача параметров по референсу, то изменится.

По кому? 

Цитата: RawonaM от ноября  5, 2011, 17:34
В следущий раз буду выкладывать псевдокод, чтобы не было тенденции конкретную имплементацию обсуждать.

В следующий раз внятно описывайте, что за переменные используются, или давайте им говорящие имена.

А то я прочитал переменные как «А, И, Р», и долго не мог врубиться, что они суть такое.

Цитата: Hellerick от ноября  5, 2011, 17:39
По кому? 

По ссылке.

Цитата: Hellerick от ноября  5, 2011, 17:39
В следующий раз внятно описывайте, что за переменные используются, или давайте им говорящие имена.

А то я прочитал переменные как «А, И, Р», и долго не мог врубиться, что они суть такое.

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