Как отсортировать li алгоритмом merge sort?

Question

[mardari98]

Есть такой список:

<ul class="items">
				{% for item in items %}
				<li data-sort="{{item.price}}">
					<a href="{{item.link}}">
						<span class="title">{{item.title}}</span>
						<div class="price">
							<span class="num">{{item.price}}</span>
						</div>
					</a>
				</li>
				{% endfor %}
			</ul>

Нужно отсортировать по атрибуту data-sort (дублируется цена из span).
Реализовал при помощи bubble sort таким образом:

bubble sort

var items  = document.querySelector('.items')
function sortAsc()
{
	for(let i = 0; i<items.children.length; i++)
	{
		for(let j = i; j<items.children.length; j++)
		{
			if(+items.children[i].getAttribute('data-sort') > +items.children[j].getAttribute('data-sort'))
			{
				replacedNode = items.replaceChild(items.children[j], items.children[i]);
				insertAfter(replacedNode, items.children[i]);
			}
		}
	}
}

function insertAfter(elem, refElem)
{
	return refElem.parentNode.insertBefore(elem,refElem.nextSibling)
}

Но пузырёк - это не дело. Мне нужно сделать это через Merge Sort. Вот алгоритм для простого массива (но он почему-то не меняет массив, выводится первоначальный массив):

Merge sort

function mergeSort (unsortedArray) {
  // No need to sort the array if the array only has one element or empty
  if (unsortedArray.length <= 1) {
    return unsortedArray;
  }
  // In order to divide the array in half, we need to figure out the middle
  const middle = Math.floor(unsortedArray.length / 2);

  // This is where we will be dividing the array into left and right
  const left = unsortedArray.slice(0, middle);
  const right = unsortedArray.slice(middle);

  // Using recursion to combine the left and right
  return merge(
    mergeSort(left), mergeSort(right)
  );
}
function merge (left, right) {
  let resultArray = [], leftIndex = 0, rightIndex = 0;

  // We will concatenate values into the resultArray in order
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      resultArray.push(left[leftIndex]);
      leftIndex++; // move left array cursor
    } else {
      resultArray.push(right[rightIndex]);
      rightIndex++; // move right array cursor
    }
  }

  // We need to concat here because there will be one element remaining
  // from either left OR the right
  return resultArray
          .concat(left.slice(leftIndex))
          .concat(right.slice(rightIndex));
}

Буду признателен, если поможете адаптировать Алгоритм под мою задачу. Завтра дедлайн, вся надежда на вас.
P.S. Была идея поместить данные li в массив объектов (создать класс), отсортировать его, а потом по новой отобразить на странице в виде li. Но не хватает знаний JS для этого.

Comments

[Дмитрий Беляев]

почему бы не использовать встроенный метод массива .sort вместо изобретения велосипеда?
на spider-monkey будет тот же merge-sort только написанный на плюсах и работающий быстрее
на v8 будет qsort, который в большинстве случаев работает с той же скоростью, что и merge-sort

[mardari98]

Дмитрий Беляев, Дело в том, что это для университета. И весь смысл именно в алгоритме. А если использовать встроенный метод, какой тогда смысл?

Answer 1

[twobomb]

alert(mergesort([10,9,8,232,437,6,5435,4,3]));//пример
function mergesort(m){
    return m.length <= 1? m: merge(mergesort(m.splice(0,Math.floor(m.length / 2))),  mergesort(m.splice(0)))
}

function merge(left,right){
    var result = [];
    while (left.length > 0 && right.length > 0){
        if (left[0] <= right[0]){
        		result.push(left[0]);
             left.splice(0,1);
            }
        else{
            result.push(right[0]);
             right.splice(0,1);
         }
    }
    return result.concat(left).concat(right);     
 }

Ну сам лист нужно сортировать до вывода страницы, потому что так теряется вся логика сортировки.

function sortList(){
 	document.querySelectorAll(".items").forEach(itemsCont=>{
  		var items = Array.from(itemsCont.querySelectorAll("li"));
      var arr = [];
      items.forEach(el=>arr.push(parseInt(el.getAttribute("data-sort"))));
      arr = mergesort(arr);
      //arr = arr.sort(); //Лучше использовать sort вместо mergesort, работает примерно в 20 раз быстрее, проверено
      arr.reverse().forEach(inx=>{
      	itemsCont.prepend(items.find((el,i,arra)=>{
        	if(el.getAttribute("data-sort") == inx){
          	items.splice(i,1);
            return el;
          }
        }));
      });
  });
 }

Comments

[mardari98]

Не совсем. Я бы мог легко отсортировать лист в питоне ещё до генерации HTML, но фишка в том, что я выбираю метод сортировки через select, и нужно сделать это именно динамично, чтобы страница не перезагружалась. Это реально вообще сделать? Или бросить это дело?

[twobomb]

mardari98, Типа после выбора в селектa загружаются итемы с сервера?

[mardari98]

twobomb, нет, прям на странице переставлять. Пурырьковой сортирвкой и

replacedNode = items.replaceChild(items.children[j], items.children[i]);
insertAfter(replacedNode, items.children[i]);

этими методами я достиг того результата, который мне нужен, но мне нужно именно merge sort.

[twobomb]

mardari98, а почему именно merge sort? И что там сотни тысяч элементов?

[mardari98]

twobomb, Ну можно и quick sort, но не думаю что это что-то изменит. Нет, там не миллион элементов, но это для университета, и я не могу использовать пузырьковую сортировку (хотите чтобы меня высмеяли? :D ) или стандартные функции сортировки.

[mardari98]

twobomb, Ваше решение работает. Спасибо огромное!