Стабильная сортировка

[logg]

Использовал на замену table.sort

единственное поменял # на GetTableSize

использование: stable_sort( массив, параметры)

Параметры вида (можно не указывать по умолчанию указаны ниже):

function (a,  return a < b end

, как в table.sort

т.е. если нужно сортировать по какому-то приоритету в массиве:

function (a,  return a.priority < b.priority end

 

local max_chunk_size = 12 

function insertion_sort( array, first, last, goes_before ) 
  for i = first + 1, last do 
    local k = first 
    local v = array[i] 
    for j = i, first + 1, -1 do 
      if goes_before( v, array[j-1] ) then 
        array[j] = array[j-1] 
      else 
        k = j 
        break 
      end 
    end 
    array[k] = v 
  end 
end 

function merge( array, workspace, low, middle, high, goes_before ) 
  local i, j, k 
  i = 1 
  -- Copy first half of array to auxiliary array 
  for j = low, middle do 
    workspace[ i ] = array[ j ] 
    i = i + 1 
  end 
  i = 1 
  j = middle + 1 
  k = low 
  while true do 
    if (k >= j) or (j > high) then 
      break 
    end 
    if goes_before( array[ j ], workspace[ i ] )  then 
      array[ k ] = array[ j ] 
      j = j + 1 
    else 
      array[ k ] = workspace[ i ] 
      i = i + 1 
    end 
    k = k + 1 
  end 
  -- Copy back any remaining elements of first half 
  for k = k, j-1 do 
    array[ k ] = workspace[ i ] 
    i = i + 1 
  end 
end 


function merge_sort( array, workspace, low, high, goes_before ) 
  if high - low < max_chunk_size then 
    insertion_sort( array, low, high, goes_before ) 
  else 
    local middle = math.floor((low + high)/2) 
    merge_sort( array, workspace, low, middle, goes_before ) 
    merge_sort( array, workspace, middle + 1, high, goes_before ) 
    merge( array, workspace, low, middle, high, goes_before ) 
  end 
end 

function stable_sort( array, goes_before ) 
  local n = GetTableSize(array )
  if n < 2 then  return array  end 
  goes_before = goes_before or 
    function (a,   return a < b  end 
  local workspace = {} 
  --  Allocate some room. 
  workspace[ math.floor( (n+1)/2 ) ] = array[1] 
  merge_sort( array, workspace, 1, n, goes_before ) 
  return array 
end 

Разницы по времени сортировки не заметил, хоть и пытался отловить по mission.GetPlayTimeMs().

И для тех, кто в танке, собственно зачем это нужно: table.sort - нестабильная сортировка, нестабильность заключается в том, что иногда она переставляет равные элементы.

Источник кода http://lua.2524044.n2.nabble.com/A-stable-sort-td7648892.html

[Setras]

Имхо в паблик надо сунуть.

[ramirez]

единственное поменял # на GetTableSize

 

А надо было - на table.getn.

[Mankubus]

А надо было - на table.getn.

Разве в функцию stable_sort() мы передаем массив, а не произвольную таблицу? Я думаю что использование GetTableSize() актуально из-за этого (поправьте, пожалуйста, если ошибаюсь):

table.getn (which you shouldn't be using in Lua 5.1+. Use the length operator #) returns the number of elements in the array part of the table

[ramirez]

Разве в функцию stable_sort() мы передаем массив, а не произвольную таблицу? Я думаю что использование GetTableSize() актуально из-за этого (поправьте, пожалуйста, если ошибаюсь):

 

Сортируются только массивы с целочисленными индексами.

[Mankubus]

Сортируются только массивы с целочисленными индексами.

 

Спасибо.

 

Тест по скорости, при использовании GetTableSize() выборка из 20 испытаний, конфигурация компа одинаковая, тест поочредный с перезагрузкой аддона:

1000 int элементов (рандомно 1-100000):
table.sort() - 4ms
stable_sort() - 8ms

20000 int элементов (рандомно 1-100000):
table.sort() - 107ms
stable_sort() - 113ms

[Lafayette]

Имхо в паблик надо сунуть.

Вынес в паблик. Yes, I'm slow and I know it