сортировка методом Вставки нескольких элементов

[SHad-X]

сортировка методом Вставки нескольких элементов

Всем доброго времени суток! Обращаюсь к вам за помощью... уже часов 6 пытаюсь разобраться!!!
Мне нужно сделать сортировку Вставки одновременно нескольких элементов:

Модификация метода простых вставок заключается в том, что вместо одной переменной Х можно использовать несколько переменных Х1, Х2, ... Xm,
которые имеют значения элементов, подлежащих вставке в уже упорядоченную часть файла. Х1, X2, ... Xm упорядочены по возрастанию, поэтому сравнивая Xm в цикле по переменной i с элементами упорядоченной части, мы можем гарантировать, что, если очередной элемент k больше Xm, то он больше и остальных элементов. Перенос элементов исходного файла вперед в цикле по i выполняется на m элементов, то есть вместо k[i+1]=k в исходном алгоритме в модифицированном алгоритме записывается k[i+m]=k. При нахождении k такого, что он меньше Хm, Хm ставится на место k[i+1] и m уменьшается на 1. Далее цикл по i продолжается с новым m. Экономия числа переносов элементов достигается за счет переносов сразу на m элементов.

ВОТ! это все что я смог найти в инете про эту сортировку! и больше ничего! но я тут даже алгоритма понять не могу! что тут делается... помогите пожалуйста понять алгоритм! обьясните что нужно сделать, плз! а я попробую уже написать на PHP! заранее благодарен!

 

[sunchess]

Для чего тебе это нужно, может есть способ проще?
посмотри array функции там по сортировке массивов много функций может тебе подойдет...

 

[SHad-X]

в том то и дело, что это универское задание! нужно именно этой сортировкой!

 

[sunchess]

так чего ты хочешь добиться этой сортировкой, что сортируешь?

 

[SHad-X]

хочу добиться результатов! =) мне нужно написать алгоритм этой сортировки! прогнать через неё кучу файлов с циферками! отсортировать их, засеч время выполнения и построить графики для разных алгоритмов! интересное задание! но вот с этим алгоритмом мне не повезло!

 

[sunchess]

честно, не совсем понятно расписан алгоритм и не хочеться голову забивать после выпитого пива

офтоп

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

интересное было задание, только когда я спросил вебмастера конторы в которой я тогда работал что типа как это сделать?
На что был получен ответ, что работать в организации где задают такие еб..тые задания я бы не когда не стал работать.

интересное было задание

 

[SHad-X]

не знаю как там насчет работы! а вот из универа из за задания такого я не уйду! =) так что буду что-нить придумывать!

 

[sunchess]

а забыл все таки я сделал то что они просили тока на JS

 

[SHad-X]

молодец! =)
надеюсь кто-нить все таки сможет подсказать что тут за алгоритм такой странный??? =)

 

[sunchess]

блин, ну кто тебе подскажет если ты сам не можешь понять?
Сам описал алгоритм, а понять не можешь, если ты не можешь тока телепат сможет, а таких на форуме я пока не видел

 

[SHad-X]

это не я описывал! я бы такой бред никогда бы не написал! =) это в инете везде такое описание... и в методичке!

 

[SiMM]

Поскольку к PHP это отношения не имеет, то для начала
http://algolist.manual.ru/sort/insert_sort.php
а затем
http://phpclub.ru/talk/showthread.php?threadid=85529
И вообще - я думаю, задания в универе дают не для того, чтобы их решали за тебя. Алгоритм, кстати, вполне достаточно расписан. Если изначально иметь представление о первой ссылке. О которой тебе должны были рассказать на лекциях. Которые ты, видимо, не соизволил посещать.

 

[rotoZOOM]

SHad-X Скорее всего это называется сортировка слиянием. А конкретно есть два упорядоченных массива (в твоем случае файл и X1, X2, ... , Xm) необходимо получить из них один упорядоченный массив, состоящий из всех этих элементов.
Вот тебе еще ссылка. Оттуда для твоего конкретного случая разбери функцию merge.

 

[SHad-X]

rotoZOOM
Спасибо! попробую сегодня разобраться! но у меня точно не 2 упорядоченных массива!
SiMM
про эти сортировки я уже читал! и я не просил ничего за меня делать, а попросил только помочь понять алгоритм, а поскольку я уже все переискал вчера и устал, то решил обратиться в форум... в котором как я думал обсуждают проблему, а не посещение мной лекций!
ВСЕМ ещё раз спасибо! постараюсь сам во всем разобраться!

 

[rotoZOOM]

Модификация метода простых вставок заключается в том, что вместо одной переменной Х можно использовать несколько переменных Х1, Х2, ... Xm,
которые имеют значения элементов, подлежащих вставке в уже упорядоченную часть файла. Х1, X2, ... Xm упорядочены по возрастанию

SHad-X а что же еще у тебя такое как не два упорядоченных массива, именно это и есть ?

 

[SHad-X]

ну да! в алгоритме вроде как и 2 массива должно быть! один из которых m-элементов... но не понятно, где эти массивы и как их отслеживать! потому что мне дан файл, абсолютно неупорядоченный... получается мне сначала надо упорядочить один маленький сассив, а потом его вставить в нужну область! так чтоли? =) но это нерационально получается!

 

[SiMM]

У препода проконсультируйся.

 

[SHad-X]

если кому интересно! вот алгорим я написал:

//СОРТИРОВКА МЕТОДОМ ВСТАВОК НЕСКОЛЬКИХ ПЕРЕМЕННЫХ

$n=count($a);
$m = 64;

 for ($i=1; $i<$m; $i++)
    {
       $j=$i-1;
       if ($a[$i]<$a[$j])
        {
          $t=$a[$i];
           while ($t<@$a[$j] && $j>=0) { $a[$j+1]=$a[$j]; $j--; }
          $a[$j+1]=$t;
        }
    }

 $b = $m-1;

 while (($b+1)!=$n)
  {
      for ($i=$b+1+1; $i<$m+$b+1; $i++)
       {
          $j=$i-1;
          if ($a[$i]<$a[$j])
           {
             $t=$a[$i];
              while ($t<@$a[$j] && $j>=($b+1)) { $a[$j+1]=$a[$j]; $j--; }
             $a[$j+1]=$t;
           }
       }

       $z=1; $j=0;
       while ($j!=$n)
        {
           if ($a[$j]>$a[$b+$z])
            {
              $temp = $a[$b+$z];
              $k=$b+$z-$j;
              while ($k>0) { $a[$j+$k]=$a[$j+$k-1]; $k--; }
              $a[$j] = $temp;
              if ($z<$m) { $z++; $j++; } else { $b=$b+$m; break; }
            } else { $j++; }
            if ($j==($b+$z)) { $b=$b+$m; break; }
        }
  }

 

[kruglov]

что-то у вас сортировка сложности n^3 получилась.
многовато

 

[SHad-X]

ну какая уж есть! согласен, ужасная сортировка! я с ней долго мучался, чтобы время выполнения снять для 72 файлов! сделал, чтобы все автоматически делалось, так там самый большой файл на 16000 элементов - 140 сек сортировался! но что поделать, что задают, то и приходится делать! зато чем больше m, тем быстрее работает сортировка... быстрее чем обычными вставками - по одному элементу... =)