Форум

kogenate · #1 (**permalink**) 08.06.2016, 00:30

Есть скрипт выполняющий сортировку массива методом быстрой сортировки. Не могу разобраться, как реализовать
подсчет и вывод количества сравнений после сортировки.... Помогите пожалуйста!

<!DOCTYPE html> 
<html><head>
<title>Метод "Быстрая сортировка"</title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />

<style>

body  { margin-top:0; }

h2 { padding:0; margin-bottom:0 }
ul  { list-style-type: none;padding:12px 0px; }
ul  li { border:1px solid gray; display:inline-block; width:30px; text-align:center; margin-left:-1px; position:relative} 
 
.info { margin-top: 12px; margin-right:8px;padding-right:10px; border:1px solid gray; 
        float:left; background-color: black; color:white; min-width:72px; text-align:center;}
.pivot { color:red; opacity:0.8}
label {  width:100px; margin-top:8px;}

button { margin-top:26px; margin-left:16px; padding:2px 8px; height:28px;}
 
#arr0 , #arr1 { position:absolute; top:-1.5em; left:10px;  padding:0; margin:0;  } 

#arr0 { color: blue; }
#arr1 { color: red; } 

.finalarray { padding:6px 4px; border:1px solid red; margin:0; display:inline-block; }
   

</style>

</head>
<body>
<h2>Метод "Быстрая сортировка"</h2>

<div>
<label>Одномерный массив длинной N = 7</label>
</div> 
<div>
<label>Массив [4,9,7,6,2,3,8]</label>
</div>
<div>
<button onclick="ExecuteQS()">СОРТИРОВАТЬ</button>
</div> 

<div  id="OutDiv" > 
</div>

<script>


var A;
var paramStack;

var prevleft,prevright;
   
var arr0 = "<span id='arr0' >&darr;</span>";
var arr1 = "<span id='arr1' >&darr;</span>";

var Speed;

var newRow;
var gelem1, gelem2;
 
var lo,  hi;
var left,right; 
var Timer1= null;
var dispLeft,dispRight;
 
var gLeftIndx, gRightIndx;
var pivotLoc;
var cmp;

function compare()
{
  ++cmp;
  return cmp;
}

function ExecuteQS() 
{ 
  if (Timer1) clearInterval(Timer1);
  Timer1 = null; 

  OutDiv.innerHTML = "";
  Speed = 10;
  var n = 7;
  cmp = 0;
  A = new Array();
  A = [0,4,9,7,6,2,3,8];

  paramStack=[];
  var B = A.slice();
  Quicksort(A,1,A.length-1,compare);

  A = B.slice();
  ProcessStack(); 
  
}

function Quicksort( A, lo, hi) 
{
  if (lo < hi) 
  {  
    var mid = Partition(A,lo,hi);
    Quicksort(A,lo,mid-1);
    Quicksort(A,mid+1,hi);
  } 
} 

function Partition( A, lo, hi)
{

  paramStack.push([-lo,hi]);
  var pivot = A[lo];   
  var left = lo+1; 
  var right = hi;

  while (left <= right)
  {  
    while ((left <= right) && (A[left] <= pivot)) 
    {
      left++; ++cmp; 
    }
    while ((left <= right) && (A[right] > pivot)) 
    {
      right--;
    }	
    
    if (left < right)
    {  
      paramStack.push([left,right]);
      var t = A[left]; 
      A[left] = A[right]; 
      A[right] = t; 
      left++; 
      right--; 
    }

  }

  A[lo] = A[right]; 
  A[right] = pivot;
  paramStack.push([lo,right]); 

  return right;
}


function ProcessStack()
{  
  var elem = document.getElementById("arr0");
  if (elem) elem.parentNode.removeChild(elem); 
  elem = document.getElementById("arr1");
  if (elem) elem.parentNode.removeChild(elem); 

  if (paramStack.length==0)  
  { 
    PrintArray(A,-1,0); return; 
  }

  gelem1 = null; 
  gelem2 = null;
  newRow = false;
  var param = paramStack.shift(); 

  left = param[0]; 
  right = param[1]; 

  if (left < 0)  
  {  
    newRow =true;
    lo = -left;  
    hi = right; 
   
    prevleft = lo; 
    prevright = hi;

    param = paramStack.shift();  
   
    left = param[0]; 
    right = param[1]; 
  } 
     
  dispLeft = left-prevleft; 
  dispRight = prevright-right; 

  if (left==lo) dispLeft = right - prevleft;

  PrintArray(A, prevleft, prevright);

  prevright = right; 
  prevleft = left;

  var t = A[left]; 
  A[left] = A[right]; 
  A[right] = t; 

  if (!Timer1) Timer1 = setInterval(AnimateArrow,Speed); 
} 


function PrintArray(A, prevleft, prevright)
{  
  var finish = (prevleft==-1);
  if (finish) 
  { 
    lo=0; 
    hi=0; 
    newRow=true;
  }

  var x =  "";

  for(var i= 1; i < A.length ; i++)
  {  
    var st = ""; 
    if ( (i>=lo)  &&  (i <=hi)) st = "style='background-color:lightgray'";

    var ext ="";

    if (i==prevleft ) 
    {  
      ext = arr0; gLeftIndx = i; st = "style='background-color:white'";   
    }
  
    if (i==prevright )
    { 
      ext = arr1; gRightIndx = i; st  = "style='background-color:white'";  
    }

    if (i==lo) st += " class ='pivot'"; 
    x += "<li " + st + ">" + A[i] + ext + "</li>"; 
  } 

  var Info = ""; 

  OutDiv.innerHTML += Info + "<ul>"  + x + "</ul>"; 

  if (lo==left) pivotLoc = right;

  if (finish)
  {   
    elems = document.getElementsByTagName("ul");
    elem = elems[elems.length-1];
    elem.className = "finalarray";
    
    console.log(cmp);

  } 
   
}
  
 
function AnimateArrow()
{ 
  if (( dispLeft < -1) && ( dispRight < -1))  
  {  
    clearInterval(Timer1); Timer1 = null; 
    ProcessStack(); 
    return; 
  }

  var elems = document.getElementsByTagName("ul");
  var lastList = elems[elems.length-1];

  if (( dispLeft == -1) && ( dispRight == -1))
  {   
    lastList.getElementsByTagName("li")[left-1].style.backgroundColor="yellow"; 
    dispLeft = -2; 
    dispRight = -2;
    return;
  }

  arr_elem = document.getElementById("arr0");
  styleInfo = window.getComputedStyle(arr_elem);
  pos = parseInt(styleInfo.left); 

  pos = pos + 31;
  if ( dispLeft > 0) 
  {  
    dispLeft--;  
    if (gelem1) gelem1.style.backgroundColor="lightgray";  
      else lastList.getElementsByTagName("li")[gLeftIndx-1].style.backgroundColor="lightgray";  
    gelem1 = lastList.getElementsByTagName("li")[gLeftIndx];
    if (gLeftIndx  < right ) 
      if (gelem1.style.backgroundColor!="yellow") gelem1.style.backgroundColor="white"; 
    arr_elem.style.left = pos  + "px";  
    gLeftIndx++; 
  }
  else  if (dispLeft==0) 
  {   
    lastList.getElementsByTagName("li")[gLeftIndx-1].style.backgroundColor="yellow"; 
    dispLeft =-1;
  } 

  arr_elem  = document.getElementById("arr1");
  styleInfo = window.getComputedStyle(arr_elem);
  pos = parseInt(styleInfo.left);
  pos = pos - 31;

  if (dispRight > 0)
  {   
    dispRight--; 
      
    if (gelem2)  gelem2.style.backgroundColor="lightgray";  
     else lastList.getElementsByTagName("li")[gRightIndx-1].style.backgroundColor="lightgray";  

    gelem2 = lastList.getElementsByTagName("li")[right+dispRight-1];

    if (gelem2.style.backgroundColor!="yellow")  gelem2.style.backgroundColor="white";

    if ((right - gLeftIndx <= 2) && (dispRight<=1))  pos +=2; // to avoid blue/red arrows overlapping
    arr_elem.style.left = pos  + "px";    
  } 
  else if  (dispRight==0) 
  {   
    lastList.getElementsByTagName("li")[right-1].style.backgroundColor="yellow";   
    dispRight =-1;
       
  }   
    
}

</script>
</body>
</html>

рони · #2 (**permalink**) 08.06.2016, 09:02

Сообщение от Rise

вроде работает

это только частный случай, нужна функция сортировки

kogenate · #3 (**permalink**) 08.06.2016, 13:00

Сообщение от Rise

kogenate, немного оптимизировал код вроде работает:

alert([4,9,7,6,2,3,8].sort())

Оптимизация, увы, не выполняет требование поставленной задачи, необходимо продемонстрировать работу данной сортировки + подсчитать количество сравнений.
На Си++ все элементарно реализуется: кол-во сравнений равно 13, а тут не могу разобраться, выходит всего 7мь сравнений, счетчик ставлю в те же циклы, что и на Си++.

pureJS · #4 (**permalink**) 11.06.2016, 17:06

kogenate,

Сообщение от kogenate

Есть скрипт выполняющий сортировку массива методом быстрой сортировки. Не могу разобраться, как реализовать
подсчет и вывод количества сравнений после сортировки.... Помогите пожалуйста!

Надеюсь , что я правильно понял:

var arr = [0,4,9,7,6,2,3,5,11,55,-3],
count = 0,
result = arr.slice().sort(function(c, d)
{
	//подсчёт вхождений:
	count++;

	if(c < d) return -1;
	else if(c > d) return 1;

	return 0
});

alert('изменённый порядок: ' + result); //-3,0,2,3,4,5,6,7,9,11,55
alert('всего сравнений было: ' + count); //26

рони · #5 (**permalink**) 11.06.2016, 18:21

pureJS,
если цифры досточно вернуть разницу сравниваемых элементов

var arr = [0,4,9,7,6,2,3,5,11,55,-3],
count = 0,
result = arr.slice().sort(function(c, d)
{
	//подсчёт вхождений:
	count++;

   return c - d
});

alert('изменённый порядок: ' + result); //-3,0,2,3,4,5,6,7,9,11,55
alert('всего сравнений было: ' + count); //26

pureJS · #6 (**permalink**) 11.06.2016, 18:33

Сообщение от рони

pureJS,
если цифры досточно вернуть разницу сравниваемых элементов

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

Форум

Справочник

Discord чат

Курсы javascript