Data Structures and Algorithms/InsertionSortMiddle
Description
editCategory | Sorting algorithm |
---|---|
Sub category | Insert sort |
Name | InsertionSortMiddle |
Data structure | Array |
Comparations | |
Timing | long for log array (base code need to do lot of moves) |
Spacing | (original array, input is output) |
Stability | Stable algorithm |
How it work? InsertionSortMiddle work as insert sort. Get next value (i+1) and insert to sorted array.
Check possition from middle of sorted array, then middle of part...
Properties: Algoritm not need extra memory. Ist slow for large array (moving a large array takes a lot of time). Have minimal comparation operations of all know algorithms (without counting sorts). Stable.
Statistics from real code execution (average)
editn = 1.024 value-min = 0 value-max = n/2 // 50% of array contain some repeating value ------------------ compares ~ 8.825 (Tim-sort ~8.961) cycles ~ 273.362 (Tim-sort ~16.097) moves ~ 263.514 (Tim-sort ~13.659, Select-sort ~3.054) stability = stable
Schematic of work
edit3 1 2 2 0 3 1 0 // input 3 // is first sorted array, (left = 0), half = 0, mid = 0 + floor(half / 2) (first pos_b), ''' cmp = 0 ''' . 1 // next i = 1, value = array[i] = 1, mid = 0 3-1 // compare 3-1 1 3 // 13 is now output, half = i, mid = 0 + floor(half / 2), ''' cmp + 1 ''' . . 2 // next i, array[i], mid = 0 1---2 // compare(array[i], array[mid]), compare>=0, half = floor(half / 2), left = mid, mid = left + half 3-2 // compare(array[i], array[mid]), compare<0, end (because half = 0, cannot more divide), half = i, mid = 0 + round(half / 2), ''' cmp + 2 ''' 1 2 3 . // ... note: for simplify, i remove lot of repeating text 2 // next i, mid = 1 2---2 // compare>=0, mid = left + half . 3-2 // compare<0, end, ''' cmp + 2 ''' 1 2 2 3 . . 0 // next i, mid = 1 2-----0 // compare<0, mid = left - half 1-------0 // compare<0, end, ''' cmp + 2 ''' 0 1 2 2 3 . 3 // next i, mid = 2 2-----3 // compare>=0, mid = left + half . 2---3 // compare>=0, mid = left + half . 3-3 // compare>=0, end, ''' cmp + 3 ''' 0 1 2 2 3 3 . . 1 // next i, mid = 2 2-------1 // compare<0, mid = left - half 1---------1 // compare>=0, end, ''' cmp + 2 ''' (my alg. code here compute cmp+3, because compare zero) 0 1 1 2 2 3 3 . 0 // next i, mid = 3 2-------0 // compare<0, mid = left - half 1-----------0 // compare<0, mid = left - half 0-------------0 // compare>=0, end, ''' cmp + 3 ''' =============== 0 0 1 1 2 2 3 3 // output, suma(cmp) = 1+2+2+2+3+2+3 = 15
Code (javascript)
edit<div></div>
<script>
// Created by Peter Mlich (2017)
// insert new item into sorted array, check position from middle of array
// note: algorithm code is differend from schema, but simplest
function sortInsertMiddle(cmp, start, end, n)
{
if (o.size<2) {return o.n;}
var i, i_start, i_end, left, right, mid, mid_sub;
i_start = o.start + 1;
i_end = o.end;
i = i_start;
while (i<i_end)
{
glob.cycles++;
// find position
left = o.start - 1;
right = i;
mid_sub = right - left;
while (true)
{
glob.cycles++;
mid = left + (mid_sub>>1);
if (o.fn_cmp(arr[o.n][i], arr[o.n][mid])>=0)
{
left = mid;
mid_sub = right - left;
if (mid_sub<=1) {mid++; break;}
}
else {
right = mid;
mid_sub = right - left;
if (mid_sub<=1) {break;}
}
}
// move to position, shift array
arrShift(arr[o.n], mid, i);
i++;
}
return o.n;
}
// ------
// note: code is not optimalized - draft version from my tester
function sortCompare (a, b)
{
glob.cmps++;
var c = a - b;
return c>0 ? 1 : (c<0 ? -1 : 0);
};
function arrShift(list, a, b) // move last (b) on top (a), alternation: splice or copyWithin
{
if (b<=a || a<0 || b<0) {return;}
var tmp = list[b];
glob.cycles += b - a;
glob.moves += b - a;
while (a<b)
{
list[b] = list[--b];
}
list[a] = tmp;
}
var arr = [null, [7,7,4,3,4,7,6,7,0,1,0,6,7,2,2,4], [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]]
var glob = {moves: 0, cycles: 0, cmps: 0};
var o = {start: 0, end: 16, size: 16 - 0, n: 1, moves: 0, cycles: 0, fn_cmp: sortCompare};
var log = [], i=0, n;
log[i++] = 'array-before ' + JSON.stringify(arr[1])
o.n = sortInsertMiddle(o.fn_cmp, o.start, o.end, o.n);
log[i++] = 'array-after ' + JSON.stringify(arr[o.n])
log[i++] = 'glob ' + JSON.stringify(glob)
log[i++] = 'n ' + JSON.stringify(o.end - o.start)
document.getElementsByTagName('DIV')[0].innerHTML = log.join('<br>')
/*
array-before [7,7,4,3,4,7,6,7,0,1,0,6,7,2,2,4]
array-after [0,0,1,2,2,3,4,4,4,6,6,7,7,7,7,7]
glob {"moves":66,"cycles":125,"cmps":44}
n 16
*/
</script>