Exercício 06.07

Desenvolva uma solução de ordenação de vetor onde cada thread é responsável pela ordenação de uma fração deste vetor. O número de threads e o tamanho do vetor devem ser passados por parâmetro para o programa. A função de ordenação deve ser genérica o suficiente para ser associada a cada thread. Tal função de ordenação deve receber por parâmetro uma identificação, bem como o intervalo de operação sobre o vetor. Ao final da ordenação de todas as frações, o processo pai deverá refazer a ordenação, agora sobre todo o vetor de ordenação.

Implementação na Linguagem de Programação Java

Arquivo MergeSort.java

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.poo.tutorial06.exercicio07;

import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;

/**
 * Classe responsavel pela ordenacao de uma lista de elementos,
 * utilizando o metodo de ordenacao mergeSort
 *
 * @param <T> tipo dos elementos a serem ordenados
 */
public class MergeSort<T extends Comparable<T>> implements Runnable
{
  /**
   * Lista de elementos a serem ordenados
   */
  private Queue<T> list;

  /**
   * Construtor responsavel pela inicializacao da lista de elementos a
   * serem ordenados
   *
   * @param list lista de elementos a serem ordenados
   */
  public MergeSort(Queue<T> list)
  {
    this.list = list;
  }

  /* (non-Javadoc)
   * @see java.lang.Runnable#run()
   */
  @Override
  public void run()
  {
    if(list.size() > 2)
    {
      Queue<T> list1 = new ConcurrentLinkedQueue<>();
      Queue<T> list2 = new ConcurrentLinkedQueue<>();

      int middle = list.size() / 2;

      for(T element: list)
      {
        if(middle > 0)
        {
          list1.add(element);
        }
        else
        {
          list2.add(element);
        }

        middle = middle - 1;
      }

      Thread thread1 = new Thread(new MergeSort<>(list1));
      Thread thread2 = new Thread(new MergeSort<>(list2));

      thread1.start();
      thread2.start();

      try
      {
        thread1.join();
        thread2.join();
      }
      catch(Exception exception)
      {
        exception.printStackTrace();
      }

      list.clear();

      T aux1 = null;

      T aux2 = null;

      while((!(list1.isEmpty() && list2.isEmpty())) ||
            (aux1 != null) || (aux2 != null))
      {
        if((aux1 == null) && (list1.size() > 0))
        {
          aux1 = list1.remove();
        }

        if((aux2 == null) && (list2.size() > 0))
        {
          aux2 = list2.remove();
        }

        if((aux1 != null) && (aux2 != null))
        {
          if(aux1.compareTo(aux2) > 0)
          {
            list.add(aux2);

            aux2 = null;
          }
          else
          {
            list.add(aux1);

            aux1 = null;
          }
        }
        else if(aux1 != null)
        {
          list.add(aux1);

          aux1 = null;
        }
        else if(aux2 != null)
        {
          list.add(aux2);

          aux2 = null;
        }
      }
    }
    else if(list.size() == 2)
    {
      T aux1 = list.poll();

      T aux2 = list.poll();

      if(aux1.compareTo(aux2) > 0)
      {
        list.add(aux2);
        list.add(aux1);
      }
      else
      {
        list.add(aux1);
        list.add(aux2);
      }
    }
  }
}

Arquivo Application.java

/*************************************************************************
 * Copyright (C) 2009/2024 - Cristiano Lehrer (cristiano@ybadoo.com.br)  *
 *                  Ybadoo - Solucoes em Software Livre (ybadoo.com.br)  *
 *                                                                       *
 * Permission is granted to copy, distribute and/or modify this document *
 * under the terms of the GNU Free Documentation License, Version 1.3 or *
 * any later version published by the  Free Software Foundation; with no *
 * Invariant Sections,  no Front-Cover Texts, and no Back-Cover Texts. A *
 * A copy of the  license is included in  the section entitled "GNU Free *
 * Documentation License".                                               *
 *                                                                       *
 * Ubuntu 16.10 (GNU/Linux 4.8.0-39-generic)                             *
 * OpenJDK Version "1.8.0_121"                                           *
 * OpenJDK 64-Bit Server VM (build 25.121-b13, mixed mode)               *
 *************************************************************************/

package com.ybadoo.tutoriais.poo.tutorial06.exercicio07;

import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;

/**
 * Classe responsavel pela execucao da solucao
 */
public class Application
{
  /**
   * Construtor para inicializar a execucao da solucao
   */
  private Application()
  {

  }

  /**
   * Metodo principal da linguagem de programacao Java
   *
   * @param args argumentos da linha de comando (nao utilizado)
   */
  public static void main(String[] args)
  {
    Queue<Integer> list = new ConcurrentLinkedQueue<>();

    list.add(3);
    list.add(10);
    list.add(6);
    list.add(1);
    list.add(5);
    list.add(7);
    list.add(9);
    list.add(2);
    list.add(8);
    list.add(4);

    for(Integer value: list)
    {
      System.out.print(value + " ");
    }

    System.out.println();

    MergeSort<Integer> sort = new MergeSort<>(list);

    sort.run();

    for(Integer value: list)
    {
      System.out.print(value + " ");
    }
  }
}

Tutoriais - Programação Orientada a ObjetosTutoriaisProgramação Orientada a Objetos

Implementação na Linguagem de Programação Java

Arquivo MergeSort.java

Arquivo Application.java

Tutoriais - Programação Orientada a Objetos
Tutoriais
Programação Orientada a Objetos