поиск кратчайшей сортировки, с минимальным кол-вом перестановок

[sad8c]

Задача: найти комбинацию из минимального количества перестановок, необходимых для упорядочиивания некоторой числовой последовательности. За отсутствием какого оибо опыта в решении подобных задач я сначала пошел как оказалось окольными и никуда не ведущими путями: разбиваю массив на подмассивы из уже упорядоченных элементов, т.е. подпоследовательностей, "внутрь" которых ниче вставлять уже не придется. далее сортирую полученное по первому элементу подпоследовательности методом выбора. Какбы работает, но далеко не во всех случаях(((
Если ктонибудь уже сталкивался с этой задачей или знает существующие методы решения - буду очень благодарен за помощь.

[kommunist]

Так тебе сортировка массива нужна? Каким методом?

[sad8c]

язык реализации - Java. а насчет метода сортировки - тут немного не та задача. попробую сформулировать проще - мне нужно минимальным количеством перемещений элементов последовательности упорядочить эту последовательность. например:
4 1 2 3

1 перемещение: 4 в конец.

если к примеру это делать методом простого выбора, будет 3 перемещения(поочереди 1,2,3).

поэтому я и разбиваю массив на уже упорядоченные группы. в данном случае:
4
1 2 3

и эти группы уже сортирую выбором. т.е. теперь, я нахожу минимальный элемент при первой итэреции - это 1. зная что 1 в группе с 2 и3, и что 4, ктороая стоит на месте 1 - "одинока", а значит "легче", перемещаю на правильную позицию 4. и так иду по всему массиву, совершая необходимые перестановки с учетом "веса" элементов. но это как оказалось не всегда работает. поэтому я ищу уже существующий алгоритм сортировки минимальным количеством перестановок...

[kommunist]

Посмотри это может чем нибудь-поможет

[sad8c]

спасибо большое, но к сожалению это не то(((

[mihali4]

я ищу уже существующий алгоритм сортировки минимальным количеством перестановок

Например, "метод быстрой сортировки" C.A.R. Noare.
Для вашего примера - будет 2 перестановки (при правильном выборе компаранда).

[sad8c]

Для вашего примера - будет 2 перестановки

но ведь в моем примере минимальное кол-во перестановок - ОДНА!

[mihali4]

Сообщение от sad8c

но ведь в моем примере минимальное кол-во перестановок - ОДНА!

Так ведь и вы - не компьютер, а человек!
Раз вы "знаете", как сделать любую сортировку за минимальное количество ходов, научите этому ваш компьютер.
Рекомендую сначала почитать про методы сортировок, их придумали далеко не глупые люди... Все, как один - выдающиеся математики.
Вам это ни о чем не говорит?
Ни один метод сортировки не является абсолютно универсальным. Для одного массива данных оптимальным может оказаться метод Шелла, а для другого - может быть даже и "пузырьки"...
К тому же параметры любого метода не исчерпываются только "количеством перестановок". Не менее важно и количество предваряющих их сравнений, не так ли?

[sad8c]

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

[sad8c]

всем спасибо огромное! ответ на вопрос нашел на другом форуме:

В таком случае основой алгоритма должен стать поиск длиннейшей последовательности упорядоченных элементов без учета выпадающих из порядка промежуточных элементов.
Поясню примером. Скажем есть у нас последовательность элементов 153264. Какие есть упорядоченные последовательности?
124
126
134
136
14
156
16
24
26
34
36
56
Берем за основу любую из длиннейших, и начинаем перемещать не входящие в нее на соответствующие места. При этом куда именно помещать - пофиг, скажем, если начать с 134, то 2 можно поместить как перед, так и после 6. Не влияет.