Меню
Что нового?

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

  • Автор темы Автор темы SHad-X
  • Дата начала Дата начала

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! заранее благодарен!
 
Для чего тебе это нужно, может есть способ проще?
посмотри array функции там по сортировке массивов много функций может тебе подойдет...
 
в том то и дело, что это универское задание! нужно именно этой сортировкой!
 
так чего ты хочешь добиться этой сортировкой, что сортируешь?
 
хочу добиться результатов! =) мне нужно написать алгоритм этой сортировки! прогнать через неё кучу файлов с циферками! отсортировать их, засеч время выполнения и построить графики для разных алгоритмов! интересное задание! но вот с этим алгоритмом мне не повезло!
 
честно, не совсем понятно расписан алгоритм и не хочеться голову забивать после выпитого пива :)

офтоп

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

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

интересное было задание :)
 
не знаю как там насчет работы! а вот из универа из за задания такого я не уйду! =) так что буду что-нить придумывать!
 
молодец! =)
надеюсь кто-нить все таки сможет подсказать что тут за алгоритм такой странный??? =)
 
блин, ну кто тебе подскажет если ты сам не можешь понять?
Сам описал алгоритм, а понять не можешь, если ты не можешь тока телепат сможет, а таких на форуме я пока не видел :)
 
это не я описывал! я бы такой бред никогда бы не написал! =) это в инете везде такое описание... и в методичке!
 
Поскольку к PHP это отношения не имеет, то для начала
http://algolist.manual.ru/sort/insert_sort.php
а затем
http://phpclub.ru/talk/showthread.php?threadid=85529
И вообще - я думаю, задания в универе дают не для того, чтобы их решали за тебя. Алгоритм, кстати, вполне достаточно расписан. Если изначально иметь представление о первой ссылке. О которой тебе должны были рассказать на лекциях. Которые ты, видимо, не соизволил посещать.
 
SHad-X Скорее всего это называется сортировка слиянием. А конкретно есть два упорядоченных массива (в твоем случае файл и X1, X2, ... , Xm) необходимо получить из них один упорядоченный массив, состоящий из всех этих элементов.
Вот тебе еще ссылка. Оттуда для твоего конкретного случая разбери функцию merge.
 
rotoZOOM
Спасибо! попробую сегодня разобраться! но у меня точно не 2 упорядоченных массива!
SiMM
про эти сортировки я уже читал! и я не просил ничего за меня делать, а попросил только помочь понять алгоритм, а поскольку я уже все переискал вчера и устал, то решил обратиться в форум... в котором как я думал обсуждают проблему, а не посещение мной лекций!
ВСЕМ ещё раз спасибо! постараюсь сам во всем разобраться!
 
Модификация метода простых вставок заключается в том, что вместо одной переменной Х можно использовать несколько переменных Х1, Х2, ... Xm,
которые имеют значения элементов, подлежащих вставке в уже упорядоченную часть файла. Х1, X2, ... Xm упорядочены по возрастанию
Нажмите для раскрытия...
SHad-X а что же еще у тебя такое как не два упорядоченных массива, именно это и есть ? :)
 
ну да! в алгоритме вроде как и 2 массива должно быть! один из которых m-элементов... но не понятно, где эти массивы и как их отслеживать! потому что мне дан файл, абсолютно неупорядоченный... получается мне сначала надо упорядочить один маленький сассив, а потом его вставить в нужну область! так чтоли? =) но это нерационально получается!
 
если кому интересно! вот алгорим я написал:
PHP: 
//СОРТИРОВКА МЕТОДОМ ВСТАВОК НЕСКОЛЬКИХ ПЕРЕМЕННЫХ

$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; }
        }
  }
 
ну какая уж есть! согласен, ужасная сортировка! я с ней долго мучался, чтобы время выполнения снять для 72 файлов! сделал, чтобы все автоматически делалось, так там самый большой файл на 16000 элементов - 140 сек сортировался! но что поделать, что задают, то и приходится делать! зато чем больше m, тем быстрее работает сортировка... быстрее чем обычными вставками - по одному элементу... =)
 
Войдите или зарегистрируйтесь для ответа.
Сверху