Ordenação Utilizando Filas de Prioridade

Implemente os algoritmos Insertion-Sort e Selection-Sort utilizando um TAD Fila de Prioridade que também deve ser desenvolvido.

Classes:

Fila:

import java.util.ArrayList;

abstract class Fila{

private ArrayList<Item> Array = new ArrayList<Item>();

public Fila(){
}

abstract public void InsereItem(int Chave, Object Elemento);

abstract public Item RemoveMin();

abstract public int MinKey();

abstract public Object MinElement();

public int Size(){
return Array.size();
}

public boolean IsEmpty(){
return Array.isEmpty();
}

}

Item:

public class Item {

private int Chave;
private Object Elemento;

public Item(int Chave, Object Elemento){
this.Chave = Chave;
this.Elemento = Elemento;
}

public void setChave(int Chave){
this.Chave = Chave;
}

public void setElemento(int Elemento){
this.Elemento = Elemento;
}

public int getChave(){
return Chave;
}

public Object getElemento(){
return Elemento;
}

}

Sort:

import java.util.ArrayList;

public class Sort {

private Fila fila;
private ArrayList<Item> Array;

public Sort(ArrayList<Item> Array, Fila fila){
this.Array = Array;
this.fila = fila;
}

public ArrayList<Item> SortList(){
ArrayList<Item> ArrayOrdenado = new ArrayList<Item>();

for(int i = 0; i < Array.size(); i++)
fila.InsereItem(Array.get(i).getChave(), Array.get(i).getElemento());

int Tamanho = fila.Size();

for(int i = 0; i < Tamanho; i++)
ArrayOrdenado.add(fila.RemoveMin());

return ArrayOrdenado;
}

}

Selection-Sort:

import java.util.ArrayList;

public class SelectionSort extends Fila{

private ArrayList<Item> Array = new ArrayList<Item>();

public SelectionSort(){
}

public void InsereItem(int Chave, Object Elemento){
Array.add(new Item(Chave, Elemento));
}

public Item RemoveMin(){
Item menor = Array.get(0);
for(int i = 0; i < Array.size(); i++){
if(Array.get(i).getChave() < menor.getChave())
menor = Array.get(i);
}
Array.remove(menor);
return menor;
}

public int MinKey(){
Item menor = Array.get(0);
for(int i = 0; i < Array.size(); i++){
if(Array.get(i).getChave() < menor.getChave())
menor = Array.get(i);
}
return menor.getChave();
}

public Object MinElement(){
Item menor = Array.get(0);
for(int i = 0; i < Array.size(); i++){
if(Array.get(i).getChave() < menor.getChave())
menor = Array.get(i);
}
return menor.getElemento();
}

public int Size(){
return Array.size();
}

public boolean IsEmpty(){
return Array.isEmpty();
}

}

Insertion-Sort:

import java.util.ArrayList;

public class InsertionSort extends Fila{

private ArrayList<Item> Array = new ArrayList<Item>();

public InsertionSort(){
}

public void InsereItem(int Chave, Object Elemento){
Array.add(new Item(Chave, Elemento));

int posicao = 1;
if(Array.size() >= 1){
while(posicao < Array.size()){
for(int i = posicao; i > 0; i--){
if(Array.get(i).getChave() < Array.get(i - 1).getChave())
SwapElements(Array.get(i), Array.get(i - 1));
}
posicao++;
}
}
}

public Item RemoveMin(){
Item temp = Array.get(0);
Array.remove(temp);
return temp;
}

public int MinKey(){
return Array.get(0).getChave();
}

public Object MinElement(){
return Array.get(0).getElemento();
}

private void SwapElements(Item Elemento1, Item Elemento2){
int index1 = Array.indexOf(Elemento1);
int index2 = Array.indexOf(Elemento2);

Array.set(index1, Elemento2);
Array.set(index2, Elemento1);
}

public int Size(){
return Array.size();
}

public boolean IsEmpty(){
return Array.isEmpty();
}

}

Main:

import java.util.ArrayList;


public class Main {

public static void main(String Args[]){

SelectionSort Sel = new SelectionSort();
InsertionSort Ins = new InsertionSort();

ArrayList<Item> ArraySel = new ArrayList<Item>();

ArraySel.add(new Item(5, "Elemento 5"));
ArraySel.add(new Item(4, "Elemento 4"));
ArraySel.add(new Item(2, "Elemento 2"));
ArraySel.add(new Item(3, "Elemento 3"));
ArraySel.add(new Item(1, "Elemento 1"));

Sort SelSort = new Sort(ArraySel, Sel);

ArrayList<Item> ArrayIns = new ArrayList<Item>();

ArrayIns.add(new Item(10, "Elemento 10"));
ArrayIns.add(new Item(9, "Elemento 9"));
ArrayIns.add(new Item(8, "Elemento 8"));
ArrayIns.add(new Item(7, "Elemento 7"));
ArrayIns.add(new Item(6, "Elemento 6"));

Sort InsSort = new Sort(ArrayIns, Ins);

ArrayList<Item> ArrayRetornoSel = SelSort.SortList();

for(int i = 0; i < ArrayRetornoSel.size(); i++)
System.out.printf("%d ", ArrayRetornoSel.get(i).getChave());

System.out.printf("\n");

ArrayList<Item> ArrayRetornoIns = InsSort.SortList();

for(int i = 0; i < ArrayRetornoIns.size(); i++)
System.out.printf("%d ", ArrayRetornoIns.get(i).getChave());

}

}