APS UNIP 3º E 4º SEMESTRE - COMPUTAÇÃO

Prévia do material em texto

INSTITUTO DE CIÊNCIAS EXATAS E TECNOLOGIA – ICET
CURSO DE CIÊNCIA DA COMPUTAÇÃO
CHRYSTIAN ARTUR RODRIGUES DE ALMEIDA - F246HD7 
FRANCSICO ÁLISSON COSTA LOPES - T05AIE0
“DESENVOLVIMENTO DE SISTEMA PARA ANÁLISE DE PERFORMANCE DE ALGORITMOS DE ORDENAÇÃO DE DADOS
APS – ESTRUTURA DE DADOS
DIEGO RODRIGUES
BRASÍLIA/DF
2021/01
Índice
Índice	2
Objetivo	2
Introdução	2
Algoritmo:	2
Algoritmo de Ordenação:	2
Bubble Sort :	2
Selection Sort:	2
Quick Sort:	2
Insertion sort:	2
Referencial Teórico	2
Desenvolvimento	2
Resultados e Discussão	2
Considerações Finais	2
Referencias Bibliográficas	2
Objetivo
O objetivo do trabalho é desenvolver um sistema computacional utilizando algoritmos que irão ordenar 100 mil imagens de satélites de toda região a cada 24 horas utilizando a linguagem de programação PHP da forma mais eficiente possível levando em consideração a utilização de mais de um método de ordenação. O objetivo é usar e comparar os métodos escolhidos para uma análise mais ampla sobre eles.
Os métodos irão catalogar os dados das imagens capturados pelos satélites, em seguida irá ordenar e comparar os desempenhos de cada um
Introdução
Algoritmo:
O algoritmo é uma forma de pensar em uma resolução de problema. Pode ser feito com qualquer sequência de valores ou objetos que tenham uma lógica infinita como por exemplo: língua portuguesa, linguagem C, linguagem Pascal, uma sequência de números, um conjunto de objetos tais como caneta, lápis, borracha. Ou seja, qualquer sequência que possa fornecer uma sequência lógica.
 Um algoritmo pode ser visto como uma receita culinária, ou seja, algo que pode ser seguido como uma passo-a-passo e com os procedimentos necessários para a resolução de um problema, apesar de alguns algoritmos serem bem mais complexos.
Algoritmo de Ordenação:
	Algoritmo de ordenação é um algoritmo que coloca os elementos de uma dada sequência em uma certa ordem. Em outras palavras faz uma ordenação completa ou parcial. O objetivo de uma ordenação é facilitar a recuperação dos dados de uma lista.
Os algoritmos de ordenação mais utilizados são: Bubble Sort, Selection Sort, Quick Sort e Insertion Sort.
Bubble Sort :
Bubble sort é o algoritmo mais simples, porém o menos eficientes. No algoritmo bubble sort, cada elemento da posição i será comparado com o elemento da posição i + 1, ou seja, um elemento da posição 2 será comparado com o elemento da posição 3. Se o elemento da posição 2 for maior que o da posição 3, eles são trocados de lugar e assim sucessivamente. Por causa dessa forma de execução, o vetor terá que ser percorrido quantas vezes que for necessária, tornando o algoritmo pouco eficiente para listas muito grandes. Seguindo um exemplo teórico a seguir:
Selection Sort:
A selection sort funciona de um dos dois jeitos: ou passa o menor valor do vetor para a primeira posição ou o maior valor do vetor para a última posição, e depois o segundo menor valor para a segunda posição e assim sucessivamente, até os últimos dois elementos ou dois primeiros.
Neste tipo de ordenação é selecionado um número a partir do primeiro, este número que foi selecionado é comparado com os números a partir da sua direita, quando encontra um número menor, o número selecionado passa a ocupar a posição do menor número encontrado. Este número encontrado será o próximo número selecionado para continuar, caso não for encontrado nenhum número menor que este selecionado, ele é colocado na posição do primeiro número selecionado, e o próximo número à sua direita será o escolhido para fazer as comparações. Este processo é repetido até a lista estar ordenada.
De qualquer maneira, essa ordenação é excepcionalmente fácil de implementar e garante que itens imediatamente apareçam na localização final uma vez movidos. Algumas pessoas chamam esse tipo de algoritmo de ordenação de comparação local. Segue o exemplo teórico do algoritmo:
Quick Sort:
Quicksort é o algoritmo mais eficiente na ordenação por comparação. Neste algoritmo é selecionado um elemento chamado de pivô, a partir dele a lista é organizada de forma que todos os números a sua esquerda sejam menores e todos os elementos a sua direita sejam maiores. Ao final desse processo o número pivô já está em sua posição final (neste caso se a ordem for do menor para o maior). 
O tempo médio de ordenação de Quicksort é O(n log n), mas o pior caso de tempo de ordenação é O(n2). Segue o exemplo teórico do algoritmo:
Insertion sort:
O Insertion sort é um algoritmo simples e eficiente quando aplicado em pequenas listas. Neste algoritmo a lista é percorrida da esquerda para a direita, à medida que avança vai deixando os elementos mais à esquerda ordenados.
O algoritmo funciona da mesma forma que as pessoas usam para ordenar cartas em um jogo de baralho como o pôquer.
Uma insertion sort funciona usando um único item como ponto de partida e adicionando itens à sua esquerda ou direita baseada em se esses itens são menores ou maiores que o selecionado. Conforme o número de itens ordenados cresce, o algoritmo verifica novos itens em relação aos ordenados e insere o novo elemento na posição correta na lista. Uma insertion sort tem uma velocidade de melhor caso de ordenação de O(n) e de pior caso de ordenação de O(n2). 
A insertion sort ainda é um método de força bruta para ordenar itens, mas pode exigir menos comparações que uma selection sort. Segue o exemplo teórico do algoritmo:
Referencial Teórico
Quick Sort
Neste primeiro método utilizamos o algoritmo de ordenação Quick Sort, e no código a seguir temos as variáveis para ordenar da esquerda para direita e utilizamos um número como pivô. Que vai ser o elemento chave para a ordenação, ele irá jogar todos os números menores que ele para a esquerda e todos os menos para a direita.
Para definir algumas funções no código usamos as functions quicksort, partition e PrintArray. A função quicksort foi utilizada para definir as variáveis de “direita”, “esquerda“ e a nossa array que é a lista a ser ordenada. A função partition foi utilizada para definir nossa variável pivô e como ela irá ordenar os demais elementos da nossa lista, nesta parte do código foi feita um “FOR” para quando o index dos elementos deve ir para esquerda, ser for menor e quando deve ir para direta, se for maior. A função PrintArray foi criada apenas para mostrar na tela a lista e dentro dela temos um loop para que isso se repita.
Logo no final do código mostramos uma lista com alguns números quaisquer apenas para demonstração.
Bubble Sort
Neste segundo método utilizamos o algoritmo de ordenação Bubble Sort, e no código a seguir temos as variáveis para ordenar comparando um número da primeira posição com o da segunda posição. Utilizando o elemento i + 1 no código e a variável auxiliar para fazer a troca e colocar em ordem. 
Estamos utilizando uma função criada no PHP chamada “bubbleSort” que auxilia na hora de fazer a ordenação dos valores. Dentro da função fizemos um FOR para o algoritmo realizar a repetição assim que acabar de ordenar a cada dois elementos, e só termina quando os elementos do vetor estão totalmente ordenados. Esse método de ordenação não é tão eficaz quando está sendo utilizado uma lista de elementos muito extensa, por isso para fazer os testes usamos uma lista de elementos curta.
Ao final do algoritmo usamos chamamos o vetor para mostrar na tela de forma ordenada.
Heap Sort
Neste terceiro método utilizamos o algoritmo de ordenação Heap Sort, e no código a seguir temos as variáveis para ordenar trocando um elemento da última posição ou na primeira posição dependendo da forma de ordenação. Utilizando o princípio da ordenação por seleção.
Utilizamos a função heapsort que facilita no andamento do algoritmo pois é uma função do próprio PHP. Dentro da função nós chamamos um método que faz a troca de um elemento para última posição e depois outro elemento para a penúltima posição. E isso se repete no loop criado dentro da mesma função até que a ordenação de todos os elementos esteja completa.
Usamos também uma funçãocriada apena para mostrar na tela as listas antes e depois da ordenação. E a última função utilizada foi heapify que define as variáveis direita, esquerda e o max delas (que significa o primeiro e o último).
Desenvolvimento
Começamos o processo geração e obtenção dados usando um arquivo csv (arquivos separados por vírgula) disponibilizado pelo professor da matéria de estrutura de dados, ele nos forneceu o arquivo com os dados todos prontos, então bastava executar as ordenações, mas para fazê-lo tínhamos que descobrir como introduzir o arquivo csv no algoritmo para que pudéssemos fazer a ordenação. Para isso usamos um código da própria documentação do php, chamada “fgetcsv” que serve justamente para incluir um arquivo csv no código php.
E assim conseguimos introduzir o arquivo de metadados no algoritmo para fazer a ordenação. A foto a seguir mostra os primeiros metadados no arquivo csv já não seria possível colocar uma imagem com todos os metadados.
Em seguida colocamos um timer para calcular o tempo de ordenação de cada algoritmo. No começo estávamos usando listas aleatórias para testar os algoritmos de ordenação, já que não daria para testar no arquivo original, pois ele tem cerca de 100000(cem mil) dados para ordenar. Então fizemos assim:
Após usar as listas para teste e os algoritmos darem certos, começamos a testar com o arquivo original, porém não com todos os dados nele ainda. Organizamos alguns dos dados para tentar ver o resultado, já que precisávamos que ele não só ordenasse a coluna, mas também a linha completa.
	E após o teste:
	Após o teste ter dado certo, nós começamos a fazer os testes com o arquivo original em cada algoritmo. Fizemos a introdução no algoritmo de ordenação bubble sort adaptando as variáveis do código. E fizemos comentários no código para o melhor entendimento através das fotos.
	Código de ordenação por “file_size”
Código de ordenação por “date_time”
Tambem fizemos o mesmo processo para o quick sort:
Código de ordenação por “file_size”:
Código de ordenação por “date_time”
Então repetimos o processo para o algoritmo heap sort:
Código de ordenação por “file_size”
Código de ordenação por “date_time”
Resultados e Discussão
Iniciamos os testes com listas pequenas e aleatórias inventadas por nós mesmos já que no início ainda não tínhamos implementado o arquivo metadados csv no código do sistema. A principal desvantagem do bubble sort é sua baixa eficiência em listas grandes, diferentemente do quick sort que a desvantagem é o uso de uma lista muito curta. 
Adicionalmente, o seu desempenho é facilmente influenciado pela ordem inicial dos itens antes do processo de triagem. O Heapsort não é recomendado para vetores de entrada com poucos elementos, devido a complexidade do heap; O Heapsort não é estável. O anel interno do algoritmo é bastante complexo se comparado com o do Quicksort. 
A seguir faremos uma simulação de comparações de eficiência, tempo e movimentações de cada algoritmo nosso e alguns dos algoritmos mais utilizados atualmente.
Vetor de 100
Vetor de 1000
Vetor de 10000
Temos também o nível de complexidade de cada método, onde podemos ver e fazer a comparação de todos os métodos antes citados no trabalho quanto os que foram utilizados para a execução do mesmo:
Considerações Finais
Nós, o grupo como um todo entramos em um consenso que as técnicas escolhidas e implementas deram resultados bastante diferentes uma da outra, e esse foi o principal intuito do nosso grupo, pois queríamos ver resultados divergentes para a que nossa pesquisa tivesse técnicas que se adequassem em diferentes situações. Para que saibamos qual método utilizar dependendo do tipo de ordenação requerido por quem for fazer o sistema. 
Concordamos que há muito mais técnicas eficientes e mais usadas do que as que foram usadas neste documento. Mas escolhemos algumas mais antigas e menos usadas para ver a diferença de performance em cada uma delas.
Apesar de tudo cada técnica escolhida tem seus pontos fortes e fraco que as tornam únicas e utilizadas em diferentes situações. Além disso é possível notar que apenas com estes algoritmos, podemos realizar as ordenações de qualquer metadado informado.
	
Referencias Bibliográficas
https://pt.wikipedia.org/wiki/Quicksort
https://www.devmedia.com.br/algoritmos-de-ordenacao-analise-e-comparacao/28261
https://integrada.minhabiblioteca.com.br/reader/books/9788550809298/pageid/167
https://integrada.minhabiblioteca.com.br/reader/books/9788522126651/pageid/132
https://integrada.minhabiblioteca.com.br/reader/books/9788577804504/pageid/27
https://sorting.at/
https://visualgo.net/en/sorting?slide=1
https://www.php.net/manual-lookup.php?pattern=csv&scope=quickref
https://www.alphacodingskills.com/php/pages/php-program-for-quick-sort.php
https://www.alphacodingskills.com/php/pages/php-program-for-bubble-sort.php
https://www.alphacodingskills.com/php/pages/php-program-for-heap-sort.php
https://estruturadedadosuenp.directorioforuns.com/
https://www.ehow.com.br/
https://homepages.dcc.ufmg.br/
Codigo Fonte
<?php
    //LEITURA DO ARQUIVO CSV
    $csv = 'metadados.csv';
    $fh = fopen($csv, 'r');
    //ARMAZENAMENTO DOS METADADOS DO ARQUIVO CSV EM UMA LISTA (ARRAY)
    while($dados = fgetcsv($fh, 10001, ',')){
        $lista[] = $dados;
    }
    //FUNÇÃO DE ORDENAÇÃO bubbleSort - ORDENANDO PELA COLUNA date_time (ÍNDICE 4)  DO ARQUIVO CSV
    function bubbleSortData($dados){
        for($i = 0; $i < count($dados); $i++){
            for($j = 0; $j < count($dados) - 1; $j++){
                if($dados[$j][4]> $dados[$j + 1][4]){
                    $aux = $dados[$j];
                    $dados[$j] = $dados[$j + 1];
                    $dados[$j + 1] = $aux;
                } 
            }
        }
        return $dados;
    }
    //CÁLCULO DO TEMPO DE EXECUÇÃO DA FUNÇÃO bubbleSortData
    $tempo_inicial = microtime(true);
    $ordenadoSize = bubbleSortData($lista);
    $tempo_final = microtime(true);
    $tempo_execucao = ($tempo_final - $tempo_inicial)/60;
    //var_dump($ordenadoSize);
    //echo ("\n");
    //echo "- linhas: ". count($ordenadoSize);
    //echo ("\n");
    //echo "- colunas: ". count($ordenadoSize[0]);
    echo ("\n");
    //IMPRIMIR NO TERMINAL A LISTA ORDENADA
   /*
   for ($i=0; $i < count($ordenadoSize)-1; $i++) { 
        for ($j=0; $j < count($ordenadoSize[0]); $j++) { 
            echo $ordenadoSize[$i][$j]. ' ';  
        }
        echo ("\n");
    }
    */
    //IMPRESSÃO NO TERMINAL DO TEMPO DE EXECUÇÃO DO ALGORITMO BUBBLE SORT
    echo ("\n");
    echo 'Tempo total de execução para ordenação do código Bubble Sort: '.$tempo_execucao.' minutos';
    echo ("\n");
    //CRIAÇÃO DO ARQUIVO CSV PARA ALIMENTÁ-LO COM OS DADOS ORDENADOS
    $fp = fopen('bubbleSort\\data\\metadadosOrdenadoData.csv', 'w');
    //ESCREVEVENDO A LISTA ORDENADA NO ARQUIVO CSV 
    fputcsv($fp, $ordenadoSize[count($ordenadoSize)-1]);
    $i = 1;
    foreach ($ordenadoSize as $linha) {
        if($i!=count($ordenadoSize)){
            fputcsv($fp, $linha);
        }
        $i++;
    }
?>
<?php
    //LEITURA DO ARQUIVO CSV
    $csv = 'metadados.csv';
    $fh = fopen($csv, 'r');
    //ARMAZENAMENTO DOS METADADOS DO ARQUIVO CSV EM UMA LISTA (ARRAY)
    while($dados = fgetcsv($fh, 10001, ',')){
        $lista[] = $dados;
    }
    //FUNÇÃO DE ORDENAÇÃO bubbleSort - ORDENANDO PELA COLUNA file_size (ÍNDICE 3)  DO ARQUIVO CSV
    function bubbleSortTamanho($dados){
        for($i = 0; $i < count($dados); $i++){
            for($j = 0; $j < count($dados) - 1; $j++){
                if($dados[$j][3]> $dados[$j + 1][3]){
                    $aux = $dados[$j];
                    $dados[$j] = $dados[$j + 1];
                    $dados[$j + 1] = $aux;
                } 
            }
        }
        return $dados;
    }
    //CÁLCULO DO TEMPO DE EXECUÇÃO DA FUNÇÃO bubbleSortTamanho
    $tempo_inicial = microtime(true);
    $ordenadoSize = bubbleSortTamanho($lista);
    $tempo_final = microtime(true);
    $tempo_execucao = ($tempo_final- $tempo_inicial)/60;
    //var_dump($ordenadoSize);
    //echo ("\n");
    //echo "- linhas: ". count($ordenadoSize);
    //echo ("\n");
    //echo "- colunas: ". count($ordenadoSize[0]);
    echo ("\n");
    //IMPRIMIR NO TERMINAL A LISTA ORDENADA
    /* 
   for ($i=0; $i < count($ordenadoSize)-1; $i++) { 
        for ($j=0; $j < count($ordenadoSize[0]); $j++) { 
            echo $ordenadoSize[$i][$j]. ' ';  
        }
        echo ("\n");
    }
    */
    //IMPRESSÃO NO TERMINAL DO TEMPO DE EXECUÇÃO DO ALGORITMO BUBBLE SORT
    echo ("\n");
    echo 'Tempo total de execução para ordenação do código Bubble Sort: '.$tempo_execucao.' minutos';
    echo ("\n");
    //CRIAÇÃO DO ARQUIVO CSV PARA ALIMENTÁ-LO COM OS DADOS ORDENADOS
    $fp = fopen('bubbleSort\\tamanho\\metadadosOrdenadoTamanho.csv', 'w');
    //ESCREVEVENDO A LISTA ORDENADA NO ARQUIVO CSV 
    fputcsv($fp, $ordenadoSize[count($ordenadoSize)-1]);
    $i = 1;
    foreach ($ordenadoSize as $linha) {
        if($i!=count($ordenadoSize)){
            fputcsv($fp, $linha);
        }
        $i++;
    }
?>
<?php
    //LEITURA DO ARQUIVO CSV
    $csv = 'metadados.csv';
    $fh = fopen($csv, 'r');
    //ARMAZENAMENTO DOS METADADOS DO ARQUIVO CSV EM UMA LISTA (ARRAY)
    while($dados = fgetcsv($fh, 10001, ',')){
        $lista[] = $dados;
    }
    
    //FUNÇÃO DE ORDENAÇÃO heapSortData - ORDENANDO PELA COLUNA date_time (ÍNDICE 4)  DO ARQUIVO CSV
    function heapSortData(&$dados, $n) {
      for($i = (int)($n/2); $i >= 0; $i--) {
        heapify($dados, $n-1, $i);
      }
  
      for($i = $n - 1; $i >= 0; $i--) { 
        $temp = $dados[$i];
        $dados[$i] = $dados[0];
        $dados[0] = $temp;
        heapify($dados, $i-1, 0);
      }
    }
  
    //FUNÇÃO AUXILIAR PARA A REALIZAÇÃO DO HEAP SORT
    function heapify(&$dados, $n, $i) {
      $max = $i;
      $left = 2*$i + 1;
      $right = 2*$i + 2;
      if($left <= $n && $dados[$left][4] > $dados[$max][4]) {
        $max = $left;
      }
      if($right <= $n && $dados[$right][4] > $dados[$max][4]) {
        $max = $right;
      }
      if($max != $i) {
        $temp = $dados[$i];
        $dados[$i] = $dados[$max];
        $dados[$max] = $temp;
        heapify($dados, $n, $max); 
      }
    }
    
    //FUNÇÃO PARA IMPRIMIR A LISTA NO TERMINAL
    function PrintArray($dados, $n) { 
      for ($i=0; $i < $n-1; $i++) { 
        for ($j=0; $j < count($dados[0]); $j++) { 
            echo $dados[$i][$j]. ' ';  
        }
        echo ("\n");
      }
    }
    //ARMAZENANDO O TAMANHO DA LISTA
    $n = sizeof($lista); 
    //CÁLCULO DO TEMPO DE EXECUÇÃO DA FUNÇÃO heapSortData
    $tempo_inicial = microtime(true);
    heapSortData($lista, $n);
    $tempo_final = microtime(true);
    $tempo_execucao = ($tempo_final - $tempo_inicial)/60;
    //IMPRIMIR NO TERMINAL A LISTA ORDENADA
    //PrintArray($lista, $n);
    //IMPRESSÃO NO TERMINAL DO TEMPO DE EXECUÇÃO DO ALGORITMO HEAP SORT
    echo ("\n");
    echo 'Tempo total de execução para ordenação do código Heap Sort: '.$tempo_execucao.' minutos';
    echo ("\n");
    //CRIAÇÃO DO ARQUIVO CSV PARA ALIMENTÁ-LO COM OS DADOS ORDENADOS
    $fp = fopen('heapSort\\data\\metadadosOrdenadoData.csv', 'w');
    //ESCREVEVENDO A LISTA ORDENADA NO ARQUIVO CSV 
    fputcsv($fp, $lista[count($lista)-1]);
    $i = 1;
    foreach ($lista as $linha) {
        if($i!=count($lista)){
            fputcsv($fp, $linha);
        }
        $i++;
    }
?>
<?php
    //LEITURA DO ARQUIVO CSV
    $csv = 'metadados.csv';
    $fh = fopen($csv, 'r');
    //ARMAZENAMENTO DOS METADADOS DO ARQUIVO CSV EM UMA LISTA (ARRAY)
    while($dados = fgetcsv($fh, 10001, ',')){
        $lista[] = $dados;
    }
    
    //FUNÇÃO DE ORDENAÇÃO heapSortTamanho - ORDENANDO PELA COLUNA file_size (ÍNDICE 3)  DO ARQUIVO CSV
    function heapSortTamanho(&$dados, $n) {
      for($i = (int)($n/2); $i >= 0; $i--) {
        heapify($dados, $n-1, $i);
      }
  
      for($i = $n - 1; $i >= 0; $i--) { 
        $temp = $dados[$i];
        $dados[$i] = $dados[0];
        $dados[0] = $temp;
        heapify($dados, $i-1, 0);
      }
    }
  
    //FUNÇÃO AUXILIAR PARA A REALIZAÇÃO DO HEAP SORT
    function heapify(&$dados, $n, $i) {
      $max = $i;
      $left = 2*$i + 1;
      $right = 2*$i + 2;
      if($left <= $n && $dados[$left][3] > $dados[$max][3]) {
        $max = $left;
      }
      if($right <= $n && $dados[$right][3] > $dados[$max][3]) {
        $max = $right;
      }
      if($max != $i) {
        $temp = $dados[$i];
        $dados[$i] = $dados[$max];
        $dados[$max] = $temp;
        heapify($dados, $n, $max); 
      }
    }
    
    //FUNÇÃO PARA IMPRIMIR A LISTA NO TERMINAL
    function PrintArray($dados, $n) { 
      for ($i=0; $i < $n-1; $i++) { 
        for ($j=0; $j < count($dados[0]); $j++) { 
            echo $dados[$i][$j]. ' ';  
        }
        echo ("\n");
      }
    }
    //ARMAZENANDO O TAMANHO DA LISTA
    $n = sizeof($lista); 
    //CÁLCULO DO TEMPO DE EXECUÇÃO DA FUNÇÃO heapSortTamanho
    $tempo_inicial = microtime(true);
    heapSortTamanho($lista, $n);
    $tempo_final = microtime(true);
    $tempo_execucao = ($tempo_final - $tempo_inicial)/60;
    //IMPRIMIR NO TERMINAL A LISTA ORDENADA
    //PrintArray($lista, $n);
    //IMPRESSÃO NO TERMINAL DO TEMPO DE EXECUÇÃO DO ALGORITMO HEAP SORT
    echo ("\n");
    echo 'Tempo total de execução para ordenação do código Heap Sort: '.$tempo_execucao.' minutos';
    echo ("\n");
    //CRIAÇÃO DO ARQUIVO CSV PARA ALIMENTÁ-LO COM OS DADOS ORDENADOS
    $fp = fopen('heapSort\\tamanho\\metadadosOrdenadoTamanho.csv', 'w');
    //ESCREVEVENDO A LISTA ORDENADA NO ARQUIVO CSV 
    fputcsv($fp, $lista[count($lista)-1]);
    $i = 1;
    foreach ($lista as $linha) {
        if($i!=count($lista)){
            fputcsv($fp, $linha);
        }
        $i++;
    }
?>
<?php
    //LEITURA DO ARQUIVO CSV
    $csv = 'metadados.csv';
    $fh = fopen($csv, 'r');
    //ARMAZENAMENTO DOS METADADOS DO ARQUIVO CSV EM UMA LISTA (ARRAY)
    while($dados = fgetcsv($fh, 10001, ',')){
        $lista[] = $dados;
    }
    
    //FUNÇÃO DE ORDENAÇÃO quickSortTamanho - ORDENANDO PELA COLUNA date_time (ÍNDICE 4)  DO ARQUIVO CSV
    function quickSortTamanho(&$Array, $left, $right) {
        if ($left < $right) { 
          $pivot = partition($Array, $left, $right);
          quickSortTamanho($Array, $left, $pivot-1);
          quickSortTamanho($Array, $pivot+1, $right);
        }
      }
      
      //FUNÇÃO AUXILIAR PARA A REALIZAÇÃO DO QUICK SORT
      function partition(&$Array, $left, $right) {
        $i = $left;
        $pivot = $Array[$right][4];
        for($j = $left; $j <=$right; $j++) {
          if($Array[$j][4] < $pivot) {
            $temp = $Array[$i];
            $Array[$i] = $Array[$j];
            $Array[$j] = $temp;
            $i++;
          }
        }
        
        $temp = $Array[$right];
        $Array[$right] = $Array[$i];
        $Array[$i] = $temp;
        return $i;
      }
    
    //FUNÇÃO PARA IMPRIMIR A LISTA NO TERMINAL
    function PrintArray($Array, $n) { 
        for ($i=0; $i < $n-1; $i++) { 
          for ($j=0; $j < count($Array[0]); $j++) { 
              echo $Array[$i][$j]. ' ';  
          }
          echo ("\n");
        }
    }
    //ARMAZENANDO O TAMANHO DA LISTA
    $n = sizeof($lista); 
    //CÁLCULO DO TEMPO DE EXECUÇÃO DA FUNÇÃO quickSortData
    $tempo_inicial = microtime(true);
    quickSortTamanho($lista, 0, $n-1);
    $tempo_final = microtime(true);
    $tempo_execucao = ($tempo_final - $tempo_inicial)/60;
    //IMPRIMIR NO TERMINAL A LISTA ORDENADA
    // PrintArray($lista, $n);
    //IMPRESSÃO NO TERMINAL DO TEMPO DE EXECUÇÃO DO ALGORITMO QUICK SORT
    echo ("\n");
    echo 'Tempo total de execução para ordenação do código Quick Sort: '.$tempo_execucao.' minutos';
    echo ("\n");
    //CRIAÇÃO DO ARQUIVO CSV PARA ALIMENTÁ-LO COM OS DADOS ORDENADOS
    $fp = fopen('quickSort\\data\\metadadosOrdenadoData.csv', 'w');
    //ESCREVEVENDO A LISTA ORDENADA NO ARQUIVO CSV 
    fputcsv($fp,$lista[count($lista)-1]);
    $i = 1;
    foreach ($lista as $linha) {
        if($i!=count($lista)){
            fputcsv($fp, $linha);
        }
        $i++;
    }
?>
<?php
    //LEITURA DO ARQUIVO CSV
    $csv = 'metadados.csv';
    $fh = fopen($csv, 'r');
    //ARMAZENAMENTO DOS METADADOS DO ARQUIVO CSV EM UMA LISTA (ARRAY)
    while($dados = fgetcsv($fh, 10001, ',')){
        $lista[] = $dados;
    }
    
    //FUNÇÃO DE ORDENAÇÃO quickSortTamanho - ORDENANDO PELA COLUNA file_size (ÍNDICE 3)  DO ARQUIVO CSV
    function quickSortTamanho(&$Array, $left, $right) {
        if ($left < $right) { 
          $pivot = partition($Array, $left, $right);
          quickSortTamanho($Array, $left, $pivot-1);
          quickSortTamanho($Array, $pivot+1, $right);
        }
      }
      
      //FUNÇÃO AUXILIAR PARA A REALIZAÇÃO DO QUICK SORT
      function partition(&$Array, $left, $right) {
        $i = $left;
        $pivot = $Array[$right][3];
        for($j = $left; $j <=$right; $j++) {
          if($Array[$j][3] < $pivot) {
            $temp = $Array[$i];
            $Array[$i] = $Array[$j];
            $Array[$j] = $temp;
            $i++;
          }
        }
        
        $temp = $Array[$right];
        $Array[$right] = $Array[$i];
        $Array[$i] = $temp;
        return $i;
      }
    
    //FUNÇÃO PARA IMPRIMIR A LISTA NO TERMINAL
    function PrintArray($Array, $n) { 
        for ($i=0; $i < $n-1; $i++) { 
          for ($j=0; $j < count($Array[0]); $j++) { 
              echo $Array[$i][$j]. ' ';  
          }
          echo ("\n");
        }
    }
    //ARMAZENANDO O TAMANHO DA LISTA
    $n = sizeof($lista); 
    //CÁLCULO DO TEMPO DE EXECUÇÃO DA FUNÇÃO quickSortTamanho
    $tempo_inicial = microtime(true);
    quickSortTamanho($lista, 0, $n-1);
    $tempo_final = microtime(true);
    $tempo_execucao = ($tempo_final - $tempo_inicial)/60;
    //IMPRIMIR NO TERMINAL A LISTA ORDENADA
    // PrintArray($lista, $n);
    //IMPRESSÃO NO TERMINAL DO TEMPO DE EXECUÇÃO DO ALGORITMO QUICK SORT
    echo ("\n");
    echo 'Tempo total de execução para ordenação do código Quick Sort: '.$tempo_execucao.' minutos';
    echo ("\n");
    //CRIAÇÃO DO ARQUIVO CSV PARA ALIMENTÁ-LO COM OS DADOS ORDENADOS
    $fp = fopen('quickSort\\tamanho\\metadadosOrdenadoTamanho.csv', 'w');
    //ESCREVEVENDO A LISTA ORDENADA NO ARQUIVO CSV 
    fputcsv($fp, $lista[count($lista)-1]);
    $i = 1;
    foreach ($lista as $linha) {
        if($i!=count($lista)){
            fputcsv($fp, $linha);
        }
        $i++;
    }
?>
2