Форум программистов, компьютерный форум, киберфорум
Наши страницы
JavaScript
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.92/12: Рейтинг темы: голосов - 12, средняя оценка - 4.92
bonifacy7
0 / 0 / 0
Регистрация: 05.04.2011
Сообщений: 14
1

Сортировка слиянием на JS?

15.01.2013, 00:52. Просмотров 2471. Ответов 15
Метки нет (Все метки)

Привет! Не могу найти код сортировки слиянием на JS. В википедии нашел псевдокод, но на JS не представляю как сделать. Подскажите пжл.

Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
L = *In1;
R = *In2;
if( L == R )
{
 *Out++ = L;
 In1++;
 *Out++ = R;
 In2++;
}
else if( L < R )
{
 *Out++ = L;
 In1++;
}
else
{
 *Out++ = R;
 In2++;
}

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.01.2013, 00:52
Ответы с готовыми решениями:

Сортировка массивов пузырьком и слиянием
Привет! Где можно скачать исходники с пузырьковой сортировкой и сортировкой...

Сортировка слиянием. В каком куске кода происходит сортировка и каким именно образом?
Помогите, пожалуйста, разобраться. Подскажите в каком куске кода происходит...

Сортировка слиянием. трехленточная сортировка. считывание из файла
Сделал только без считывания из файла, как это сделать. Нужна помощь. У меня...

2 сортировки: пирамидальная сортировка и сортировка слиянием
Реализовать два улучшенных алгоритма сортировки. Для каждого алгоритма...

Шейкерная сортировка + сортировка слиянием
вот часть когда,которая выполняет шейкерную сортировку : для символьного и...

15
kalabuni
Нарушитель
3310 / 2623 / 629
Регистрация: 18.04.2012
Сообщений: 7,905
15.01.2013, 07:52 2
демонстрационный вариант
HTML5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=windows-1251">
</head>
<body>
<textarea id="inf" style="width: 100%; height: 400px"></textarea>
<script>
function mergeSort (Arr, Step)
{
if (!Step)
   {
   // первый шаг: создание упорядоченных массивов по два элемента
   document.getElementById ('inf').value += Arr.join ('\t') + '\n'; //***DEMO***
   for (var newArr = new Array (), j = 0, lj = Arr.length; j < lj; j += 2)
      if (j + 1 == lj) newArr [newArr.length] = [Arr [j]];
      else newArr [newArr.length] = (Arr [j] > Arr [j + 1]) ? [Arr [j + 1], Arr [j]] : [Arr [j], Arr [j + 1]];
   document.getElementById ('inf').value += newArr.join ('\t\t') + '\n'; //***DEMO***
   mergeSort (newArr, newArr.length);
   }
 
else
   {
   // последующие шаги, в которых соседние массивы упорядоченно сливаются
   // вплоть до получения одного искомого упорядоченного массива
   for (var newArr = new Array (), l = j = 0, lj = Arr.length; j < lj; j += 2)
      {
      newArr [l] = new Array (); if (j + 1 == lj) newArr [l] = Arr [j];
      else
         {
         while (Arr [j].length && Arr [j + 1].length)
            if (Arr [j] [0] < Arr [j + 1] [0]) newArr [l].push (Arr [j].shift ());
            else newArr [l].push (Arr [j + 1].shift ());
         if (!Arr [j].length && Arr [j + 1].length)
            {newArr [l] = newArr [l].concat (Arr [j + 1]); Arr [j + 1] = new Array ()}
         else if (!Arr [j + 1].length && Arr [j].length)
            {newArr [l] = newArr [l].concat (Arr [j]); Arr [j] = new Array ()}
         l++;
         }
      }
   document.getElementById ('inf').value += newArr.join ('\t\t') + '\n'; //***DEMO***
   if (newArr.length == 1) {rezult = newArr [0]; return}
   else mergeSort (newArr, newArr.length);
   }
}
 
var arr0 = [9, 5, 8, 3, 1, 2, 4, 6, 7, 0, 6, 7, 0, 0, 3, 2, 1, 9, 4];
var rezult; mergeSort (arr0); alert (rezult);
</script>
</body>
</html>
если строки, помеченные комментарием ***DEMO***, уберёте, то получите рабочий вариант
не очень рациональный, конечно... можно и попроще, и "покрасивше"
1
student_wbr
3 / 3 / 0
Регистрация: 08.05.2013
Сообщений: 75
19.07.2013, 10:11 3
Вот еще вариант сортировки слиянием на Javascript.
0
Waselews
0 / 0 / 0
Регистрация: 07.10.2013
Сообщений: 4
14.10.2013, 14:36 4
Цитата Сообщение от kalabuni Посмотреть сообщение
демонстрационный вариант
HTML5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=windows-1251">
</head>
<body>
<textarea id="inf" style="width: 100%; height: 400px"></textarea>
<script>
function mergeSort (Arr, Step)
{
if (!Step)
   {
   // первый шаг: создание упорядоченных массивов по два элемента
   document.getElementById ('inf').value += Arr.join ('\t') + '\n'; //***DEMO***
   for (var newArr = new Array (), j = 0, lj = Arr.length; j < lj; j += 2)
      if (j + 1 == lj) newArr [newArr.length] = [Arr [j]];
      else newArr [newArr.length] = (Arr [j] > Arr [j + 1]) ? [Arr [j + 1], Arr [j]] : [Arr [j], Arr [j + 1]];
   document.getElementById ('inf').value += newArr.join ('\t\t') + '\n'; //***DEMO***
   mergeSort (newArr, newArr.length);
   }
 
else
   {
   // последующие шаги, в которых соседние массивы упорядоченно сливаются
   // вплоть до получения одного искомого упорядоченного массива
   for (var newArr = new Array (), l = j = 0, lj = Arr.length; j < lj; j += 2)
      {
      newArr [l] = new Array (); if (j + 1 == lj) newArr [l] = Arr [j];
      else
         {
         while (Arr [j].length && Arr [j + 1].length)
            if (Arr [j] [0] < Arr [j + 1] [0]) newArr [l].push (Arr [j].shift ());
            else newArr [l].push (Arr [j + 1].shift ());
         if (!Arr [j].length && Arr [j + 1].length)
            {newArr [l] = newArr [l].concat (Arr [j + 1]); Arr [j + 1] = new Array ()}
         else if (!Arr [j + 1].length && Arr [j].length)
            {newArr [l] = newArr [l].concat (Arr [j]); Arr [j] = new Array ()}
         l++;
         }
      }
   document.getElementById ('inf').value += newArr.join ('\t\t') + '\n'; //***DEMO***
   if (newArr.length == 1) {rezult = newArr [0]; return}
   else mergeSort (newArr, newArr.length);
   }
}
 
var arr0 = [9, 5, 8, 3, 1, 2, 4, 6, 7, 0, 6, 7, 0, 0, 3, 2, 1, 9, 4];
var rezult; mergeSort (arr0); alert (rezult);
</script>
</body>
</html>
если строки, помеченные комментарием ***DEMO***, уберёте, то получите рабочий вариант
не очень рациональный, конечно... можно и попроще, и "покрасивше"
можеш поподробние обяснить как работает прога
0
nubideus
390 / 272 / 76
Регистрация: 19.09.2011
Сообщений: 828
14.10.2013, 19:22 5
Waselews, в вики нормально расписано.

а в коде, да, разобраться невозможно. в третьем посте есть ссылка на чуть более читабельный код.
0
kalabuni
Нарушитель
3310 / 2623 / 629
Регистрация: 18.04.2012
Сообщений: 7,905
14.10.2013, 20:48 6
Цитата Сообщение от nubideus Посмотреть сообщение
в коде, да, разобраться невозможно
имхо, существующих комментариев вполне достаточно для пытливого ума
0
nubideus
390 / 272 / 76
Регистрация: 19.09.2011
Сообщений: 828
14.10.2013, 23:37 7
Цитата Сообщение от kalabuni Посмотреть сообщение
имхо, существующих комментариев вполне достаточно для пытливого ума
для пытливого ума проще прочитать описание алгоритма и написать самому

Цитата Сообщение от Waselews Посмотреть сообщение
Javascript
1
if (Arr [j] [0] < Arr [j + 1] [0]) newArr [l].push (Arr [j].shift ());
я в детстве и то грамотней писал
0
kalabuni
Нарушитель
3310 / 2623 / 629
Регистрация: 18.04.2012
Сообщений: 7,905
15.10.2013, 00:25 8
Цитата Сообщение от nubideus Посмотреть сообщение
для пытливого ума проще прочитать описание алгоритма и написать самому
я был бы рад увидеть ваш вариант реализации этого алгоритма

но очень сомневаюсь в том, что когда-либо его увижу

Цитата Сообщение от nubideus Посмотреть сообщение
я в детстве и то грамотней писал
и в чём конкретно вы тут неграмотность увидели?

вы, видимо, так в своём счастливом детстве и застряли
когда разбрызгивая сопли критикуют всех подряд, говорят, что могут сделать много лучше,.. но своего решения так и не предъявляют
0
nubideus
390 / 272 / 76
Регистрация: 19.09.2011
Сообщений: 828
15.10.2013, 12:16 9
Цитата Сообщение от kalabuni Посмотреть сообщение
говорят, что могут сделать много лучше
прошу цитату где я это говорил.

Цитата Сообщение от kalabuni Посмотреть сообщение
когда разбрызгивая сопли критикуют всех подряд
твой код то объективно говнястый, это не только мое личное мнение.
0
kalabuni
Нарушитель
3310 / 2623 / 629
Регистрация: 18.04.2012
Сообщений: 7,905
15.10.2013, 17:23 10
Цитата Сообщение от nubideus Посмотреть сообщение
твой код то объективно говнястый, это не только мое личное мнение
честно говоря, мне как бы "насрать и розами засыпать"(с) на чьё-либо мнение

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

так что ваш пук - он прямиком в лужу угодил
и вы же обрызгались

и научитесь говорить "вы" тому, кто к вам на "вы" обращается
0
nubideus
390 / 272 / 76
Регистрация: 19.09.2011
Сообщений: 828
15.10.2013, 18:23 11
Цитата Сообщение от kalabuni Посмотреть сообщение
и научитесь говорить "вы" тому, кто к вам на "вы" обращается
сразу после того, как ты научишься различать "вы" и "Вы".

Цитата Сообщение от kalabuni Посмотреть сообщение
однако в данном конкретном случае не могу не согласиться
ибо я сам изначально написал, что мой код "не очень рациональный, конечно... можно и попроще, и "покрасивше"
это не единственный твой плохой код, который я видел.
даже если ты понимаешь что пишешь какл, какл от этого не перестает быть каклом.
иди читай
http://learn.javascript.ru/coding-style
http://google-styleguide.googlecode.com/svn/trunk/javascriptguide.xml

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

Добавлено через 5 минут
Цитата Сообщение от kalabuni Посмотреть сообщение
честно говоря, мне как бы "насрать и розами засыпать"(с) на чьё-либо мнение
настолько насрать, что ты придумываешь и пишешь обо мне то, что не правда. настолько не правда, что я попросил доказать и ты не доказываешь.
0
alokazay
32 / 32 / 6
Регистрация: 14.03.2013
Сообщений: 89
15.10.2013, 21:28 12
Цитата Сообщение от nubideus Посмотреть сообщение
.
Товарищ ТЫ не прав, можешь сделать лучше показывай пример, а не сопли здесь что код не красивый, тут люди помогают а не пытаются обосрать.
1
nubideus
390 / 272 / 76
Регистрация: 19.09.2011
Сообщений: 828
16.10.2013, 01:47 13
Цитата Сообщение от alokazay Посмотреть сообщение
Товарищ ТЫ не прав
в чем же? сам то ты пробовал прочитать его код?

Цитата Сообщение от alokazay Посмотреть сообщение
можешь сделать лучше показывай пример, а не сопли здесь что код не красивый
да базара ноль,
Javascript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
var mergeSort = function(array){
  var chunkSize = array.length / 2;
  if(chunkSize >= 1){
    var left = mergeSort(array.slice(0, chunkSize));
    var right = mergeSort(array.slice(chunkSize));
    
    var result = [];
    while(left.length && right.length){
      if(left[0] < right[0]){
        result.push(left.shift());
      } else{
        result.push(right.shift());
      }
    }
    
    return result.concat(left, right);
  }
  
  return array;
};
 
var N = 9;
var testArray = [];
for(var i = 0; i < N; i++){
  testArray.push(Math.random() * N);
}
 
console.log(mergeSort(testArray));
стало лучше? kalabuni будет от этого писать читаемый код?
ящитаю, что по настоящему помочь новичку - это когда он сам разберется в задаче и в решении. не вижу смысла в том, что у него будет рабочий исходник, которого он не понимает.

сделать "лишь бы работало, лишь бы отстал и плюсик поставил" - это не помощь.
0
kalabuni
Нарушитель
3310 / 2623 / 629
Регистрация: 18.04.2012
Сообщений: 7,905
16.10.2013, 07:29 14
Цитата Сообщение от nubideus Посмотреть сообщение
это не единственный твой плохой код, который я видел
повторяю, "тыкайте" своим друзьям из подворотни, они заценят по достоинству
Цитата Сообщение от nubideus Посмотреть сообщение
ящитаю, что
купите словарь
орфографический
0
nubideus
390 / 272 / 76
Регистрация: 19.09.2011
Сообщений: 828
16.10.2013, 14:17 15
Цитата Сообщение от kalabuni Посмотреть сообщение
повторяю, "тыкайте" своим друзьям из подворотни, они заценят по достоинству
повторяю, перестану "тыкать" сразу после того, как ты научишься различать "Вы" и "вы".
местоимения(вики).

Цитата Сообщение от kalabuni Посмотреть сообщение
купите словарь
орфографический
когда аргументов больше нет, остается только найти орфографические или грамматические ошибки в тексте.
короче спор ты просрал, иди учи сначала это, а потом это.
0
Vovan-VE
16.10.2013, 15:18     Сортировка слиянием на JS?
  #16
 Комментарий модератора 
Заканчиваем оффтоп. Личные разборки устраивайте где-нибудь за рамками форума.
0
16.10.2013, 15:18
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.10.2013, 15:18
Привет! Вот еще темы с ответами:

Сортировка слиянием
Здравствуйте, изучая сортировку, в интернете наткнулся на код сортировки...

Сортировка с слиянием
Добрый вечер! Помогите с подсчетом перестановок и сравнений при сортировке с...

Сортировка слиянием
Восходящая сортировка слиянием массива. Метод слияния прямой.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru