SW20210512

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Arrays - Procuras, Ordenações</title>
</head>
<body>
<script>
//procuras
function blindSearch(
    pElemento,
    pCol
){
  var bCautela = Array.isArray(pCol);
  if (bCautela){
    var iQuantosElementos = pCol.length;

    for (
      //zona de inits
      var idx=0,
          aOndeFoiEncontradoOElemento = new Array(), //v2
          iQuantasVezesEncontreiOElemento = 0; //v3

      //zona de continuidade
      idx<=iQuantosElementos-1;

      //zona de auto-update
      idx+=1
    )
    {
      var oElementoDoMomento = pCol[idx];
      var bEncontreiOQueProcuro = oElementoDoMomento === pElemento;
      //if (bEncontreiOQueProcuro) return true; //v1 Claude Shannon
      //v2
      if (bEncontreiOQueProcuro){
        aOndeFoiEncontradoOElemento.push(idx);
        iQuantasVezesEncontreiOElemento+=1;
      }
    }
    //return false; //v1
    //return aOndeFoiEncontradoOElemento; //v2
    return {
      "onde" : aOndeFoiEncontradoOElemento,
      "quantas" : iQuantasVezesEncontreiOElemento
    }
  }//if
}//blindSearch

var a = [1, 2, 2, 3, 10, 20, 10];
var oJSON /*acrónimo*/ = blindSearch(
      desejado = 10,
      a
);

//3 informações extraíveis do mesmo algoritmo de procura
var bExiste = oJSON.quantas>0;

/*
if (oJSON.quantas===0)
  bExiste = false;
else
  bExiste = true;
*/

var iQuantasVezes = oJSON.quantas;
var aOndeEstava = oJSON.onde;
document.write
("Encontrei o elemento "+desejado+ " "+iQuantasVezes+" vez(es)<br>");

document.write
("<br>Encontrei o elemento "+desejado+ " nas posições "+aOndeEstava+"<br>");

document.write("<hr>");

//ordenações
//o algoritmo de ordenação +simples q me ocorre (e também o menos eficiente)
//é o "bubble sort"
/*
dada uma coleção (qualquer)
enquanto a coleção NÃO ESTIVER ODENADA
para ordená-la ASCENDENTEMENTE (do menor para o maior dos elementos)
    para ordená-la DESCENDENTE (do maior para o nenor dos elementos)
vamos passear-nos
do primeiro ao PENÚLTIMO elemento da coleção
a cada passo deste passeio, queremos prestar atenção,
ao elemento corrente *e* ao seu vizinho
(idx) (idx+1)
sempre que encontrarmos um elemento concreto que é "maior" >
    sempre que encontrarmos um elemento concreto que é "menor" <
que o seu "vizinho" deveremos
trocá-los
*e*
tomar nota que fizémos trocas

exemplo ilustrado
[3, 2, 1] //não está ordenada asc
0: 3@0 > 2@0+1 => 3>2 true
[2, 3, 1] //fiz trocas
1: 3@1 > 1@1+1 => 3>1 true => trocar os elementos nas posições 1 e 2
[2, 1, 3] //não está ordenada asc
FIM DO PASSEIO #1 : houve trocas? sim (houve duas)
[2, 1, 3]
0: 2@0 > 1@1 true trocar(2@0, 1@1)
[1, 2, 3]
1: 2@1 > 3@2 2>3 false NO trocar
FIM DO PASSEIO #2 : houve trocas? sim (houve uma troca)
[1, 2, 3]
0: 1@0 > 2@1 false NO trocas
1: 2@1 > 3@2 false NO trocas
FIM DO PASSEIO #3 : houve trocas? NÃO (ordenada!)
 */

function bubbleSort(
    pCol
)
{
    var iPrimeiro=0, iPenultimo, bOrdenada=false, bFizTrocas=false;
    var bCautela = Array.isArray(pCol) && pCol.length>0;
    if (bCautela){
        while (!bOrdenada) {
            for (
                iAtual = iPrimeiro,

                    /*
                    em JS, pq os arrays são indexados a partir de zero
                    o index do último elemento de uma coleção com length elementos
                    é length-1
                    e, por isso, o index do penúltimo é o index do último -1
                    ou seja
                    length-1-1
                    exemplo uma coleção com 3 elementos
                    tem o último no index 3-1 = 2
                    tem o penúltimo no index 3-1-1 = 1
                    ou seja, para efeitos do Bubble Sort,
                    haverá q passear de [0 a 1]
                     */
                    iPenultimo = pCol.length - 1 - 1,
                    bFizTrocas = false;

                iAtual <= iPenultimo;

                iAtual += 1
            ) {
                var elementoDoMomento = pCol[iAtual];
                var vizinho = pCol[iAtual + 1];
                var bDevoTrocar = elementoDoMomento > vizinho;
                if (bDevoTrocar) {
                    //trocar(elementoDoMomento, vizinho); //impossível em JS pq não há passagem por referência
                    var temp = pCol[iAtual];
                    pCol[iAtual] = pCol[iAtual+1];
                    pCol[iAtual+1] = temp;
                    bFizTrocas = true;
                }
            }//for
            //***depois*** do passeio
            if (!bFizTrocas) bOrdenada = true; //concluir q a col ficou ordenada
        }//while
    }//if bCautela
}//bubbleSort

function bs2(
    pCol, //a coleção q é para ordenar
    pbAscendente //se true, faz asc; c.c. faz desc
)
{
    pbAscendente = pbAscendente===undefined ? true : pbAscendente;

    var iPrimeiro=0, iPenultimo, bOrdenada=false, bFizTrocas=false;
    var bCautela = Array.isArray(pCol) && pCol.length>0;
    var iTrocas = 0;
    var iPasseios = 0;
    if (bCautela){
        while (!bOrdenada) {
            for (
                iAtual = iPrimeiro,
                iPenultimo = pCol.length - 1 - 1,
                bFizTrocas = false;

                iAtual <= iPenultimo;

                iAtual += 1
            ) {
                var elementoDoMomento = pCol[iAtual];
                var vizinho = pCol[iAtual + 1];

                //var bDevoTrocar = elementoDoMomento > vizinho; //ASC
                //var bDevoTrocar = elementoDoMomento < vizinho; //DESC
                var bDevoTrocar = pbAscendente ?
                    elementoDoMomento > vizinho
                    :
                    elementoDoMomento < vizinho;

                if (bDevoTrocar) {
                    //trocar(elementoDoMomento, vizinho); //impossível em JS pq não há passagem por referência
                    var temp = pCol[iAtual];
                    pCol[iAtual] = pCol[iAtual+1];
                    pCol[iAtual+1] = temp;
                    bFizTrocas = true;
                    iTrocas++;
                }
            }//for
            //***depois*** do passeio
            iPasseios++;
            if (!bFizTrocas) bOrdenada = true; //concluir q a col ficou ordenada
        }//while
    }//if bCautela
    return {
        "trocas":iTrocas,
        "passeios":iPasseios
    };
}//bs2


/*
com passagem por referência isto funcionaria (condicional)
não tem em JS
só temos "por valor"
 */
function trocar(pA, pB){
    var temp = pA;
    pA = pB;
    pB = temp;
}

var col = [30, 20, 10];
document.write ("<br>ANTES de bubble sort:");
document.write(col+"<br>");
bubbleSort(col);
document.write ("<br>DEPOIS de bubble sort:");
document.write(col+"<br>");


var col2 = ["Zélia", "Maria", "Ana"];
document.write ("<br>ANTES de bubble sort:");
document.write(col2+"<br>");
bubbleSort(col2); //só faz ASC
document.write ("<br>DEPOIS de bubble sort:");
document.write(col2+"<br>");

document.write("<hr>");
var col3 = ["Melancias", "Ananazes", "Ameixas", "Kiwis", "Gafanhotos"];
document.write ("<br>ANTES de bs2:");
document.write(col3+"<br>");
bs2(col3 /*, false*/); //só faz DESC
document.write ("<br>DEPOIS de bs2:");
document.write(col3+"<br>");

/*
bs2(col3)

dentro de bs2 é EFETIVAMENTE representado uma cópia de col3
cópia-de-col3
mas os endereços coincidem
um array é apenas o endereço de uma sequência de elementos colecionados
arrumados em deslocações de memória desde "nenhuma" (index 0) até
length-1
....

Pai Natal
cópia(Pólo Norte, casa do Pai Natal)


*/

/*
Escreva, em JS, uma function de nome "bs2" que execute o algoritmo estudado de
"bubble sort" que, recebida uma qualquer coleção e um booleano,
ordena a coleção ascendenentemente se o booleano for true
e descendentemente se for false.
 */

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