Como implementar um algorítimo de ordenação por inserção e de ordenação por mistura de uma lista simplesmente encadeada em java?
Iterator.java
package br.com.estruturadedados.utilitario.colecao;
public interface Iterator<E> extends java.util.Iterator<E> {
@Override
public boolean hasNext();
public boolean hasPrevious();
@Override
public E next();
public E previous();
}
Iterable.java
package br.com.estruturadedados.utilitario.colecao;
public interface Iterable<E> extends java.lang.Iterable<E> {
@Override
public Iterator<E> iterator();
}
Colecao.java
package br.com.estruturadedados.utilitario.colecao;
public interface Colecao<E extends Comparable<E>> extends Iterable<E> {
public void adiciona(E elemento, int posicao) throws Exception;
public void adicionaInicio(E elemento);
public void adicionaFim(E elemento);
public E recupera(int posicao) throws Exception;
public boolean vazio();
public void remove(int posicao) throws Exception;
public void removeInicio() throws Exception;
public void removeFim() throws Exception;
public int tamanho();
public void limpa() throws Exception;
@Override
public Iterator<E> iterator();
}
Lista.java
package br.com.estruturadedados.utilitario.lista;
public interface Lista<E extends Comparable<E>> extends Colecao<E> {
@Override
public void adiciona(E elemento, int posicao) throws Exception;
@Override
public void adicionaInicio(E elemento);
@Override
public void adicionaFim(E elemento);
@Override
public E recupera(int posicao) throws Exception;
@Override
public boolean vazio();
@Override
public void remove(int posicao) throws Exception;
@Override
public void removeInicio() throws Exception;
@Override
public void removeFim() throws Exception;
@Override
public int tamanho();
@Override
public void limpa() throws Exception;
@Override
public Iterator<E> iterator();
}
Celula.java
package br.com.estruturadedados.utilitario.lista.encadeada.simplismente;
public class Celula<E extends Comparable<E>> {
private Celula<E> proxima;
private E elemento;
public Celula(E elemento) {
this.elemento = elemento;
}
public Celula(Celula<E> proxima, E elemento) {
this.proxima = proxima;
this.elemento = elemento;
}
public Celula<E> getProxima() {
return proxima;
}
public void setProxima(Celula<E> proxima) {
this.proxima = proxima;
}
public E getElemento() {
return elemento;
}
public void setElemento(E elemento) {
this.elemento = elemento;
}
}
Iterador.java
package br.com.estruturadedados.utilitario.lista.encadeada.simplismente;
public class Iterador<E extends Comparable<E>> implements Iterator<E> {
private Celula<E> primeira;
private Celula<E> ultima;
private E elemento;
public Iterador(Celula<E> primeira, Celula<E> ultima) {
this.primeira = primeira;
this.ultima = ultima;
}
@Override
public boolean hasNext() {
return this.primeira != null;
}
@Override
@Deprecated
public boolean hasPrevious() {
return this.ultima != null;
}
@Override
public E next() {
this.elemento = this.primeira.getElemento();
this.primeira = primeira.getProxima();
return this.elemento;
}
@Override
@Deprecated
public E previous() {
this.elemento = this.ultima.getElemento();
this.ultima = ultima.getProxima();
return this.elemento;
}
}
ListaSimplesmenteEncadeada.java
package br.com.estruturadedados.utilitario.lista.encadeada.simplismente;
public class ListaSimplismenteEncadeada<E extends Comparable<E>> implements Lista<E> {
private Celula<E> primeira;
private Celula<E> ultima;
private int tamanho;
public ListaSimplismenteEncadeada() {
this.primeira = null;
this.ultima = null;
this.tamanho = 0;
}
@Override
public void adiciona(E elemento, int posicao) throws Exception {
this.validarPosicao(posicao);
this.verificarPosicaoOcupada(posicao);
if (posicao == 0) {
this.adicionaInicio(elemento);
} else {
if (posicao == this.tamanho) {
this.adicionaFim(elemento);
} else {
Celula<E> anterior = this.recuperaCelulaRecursivo((Celula<E>) this.primeira, posicao - 1, 0);
Celula<E> nova = new Celula<>(anterior.getProxima(), elemento);
anterior.setProxima(nova);
this.tamanho += 1;
}
}
}
@Override
public void adicionaInicio(E elemento) {
Celula<E> nova = new Celula<>((Celula<E>) this.primeira, elemento);
this.primeira = nova;
if (this.vazio()) {
this.ultima = this.primeira;
}
this.tamanho += 1;
}
@Override
public void adicionaFim(E elemento) {
if (this.vazio()) {
this.adicionaInicio(elemento);
} else {
Celula<E> nova = new Celula<>(elemento);
this.ultima.setProxima(nova);
this.ultima = nova;
this.tamanho += 1;
}
}
@Override
public E recupera(int posicao) throws Exception {
this.validarPosicao(posicao);
this.verificarSeEstaVazio();
this.verificarPosicaoLivre(posicao);
Celula<E> celulaRecuperada = this.recuperaCelulaRecursivo((Celula<E>) this.primeira, posicao, 0);
E elementoRecuperado = (E) celulaRecuperada.getElemento();
return elementoRecuperado;
}
@Override
public boolean vazio() {
return this.tamanho == 0;
}
@Override
public void remove(int posicao) throws Exception {
this.validarPosicao(posicao);
this.verificarSeEstaVazio();
this.verificarPosicaoLivre(posicao);
if (this.vazio()) {
this.removeInicio();
} else {
if (posicao == this.tamanho - 1) {
this.removeFim();
} else {
Celula<E> anterior = this.recuperaCelulaRecursivo((Celula<E>) this.primeira, posicao - 1, 0);
Celula<E> atual = anterior.getProxima();
Celula<E> proxima = atual.getProxima();
anterior.setProxima(proxima);
proxima.setElemento(anterior.getProxima().getElemento());
this.tamanho -= 1;
}
}
}
@Override
public void removeInicio() throws Exception {
this.verificarSeEstaVazio();
this.primeira = this.primeira.getProxima();
this.tamanho -= 1;
if (this.vazio()) {
this.ultima = null;
}
}
@Override
public void removeFim() throws Exception {
this.verificarSeEstaVazio();
Celula<E> celulaAuxiliar = (Celula<E>) this.primeira;
Celula<E> celulaAnterior = null;
while (celulaAuxiliar.getProxima() != null) {
celulaAnterior = celulaAuxiliar;
celulaAuxiliar = celulaAuxiliar.getProxima();
}
celulaAnterior.setProxima(null);
this.ultima = celulaAnterior;
this.tamanho -= 1;
}
@Override
public int tamanho() {
return this.tamanho;
}
@Override
public void limpa() throws Exception {
this.verificarSeEstaVazio();
this.primeira = null;
this.ultima = null;
}
@Override
public Iterator<E> iterator() {
Iterator<E> iterator = new Iterador<>((Celula<E>) this.primeira, (Celula<E>) this.ultima);
return iterator;
}
private Celula<E> recuperaCelulaIterativa(int posicao) throws Exception {
this.validarPosicao(posicao);
this.verificarSeEstaVazio();
this.verificarPosicaoLivre(posicao);
Celula atual = this.primeira;
for (int i = 0; i < posicao; i++) {
atual = atual.getProxima();
}
return atual;
}
private Celula<E> recuperaCelulaRecursivo(Celula<E> celula, int posicao, int posicaoAtual) throws Exception {
this.validarPosicao(posicao);
this.verificarSeEstaVazio();
this.verificarPosicaoLivre(posicao);
return celula == null ? null : posicao == 0 ? celula : posicaoAtual < posicao ? this.recuperaCelulaRecursivo(celula.getProxima(), posicao, posicaoAtual + 1) : celula;
}
private void validarPosicao(int posicao) throws Exception {
if (posicao < 0 && posicao >= this.tamanho) {
Exception exception = new Exception("Posição inválida.");
throw exception;
}
}
private void verificarPosicaoOcupada(int posicao) throws Exception {
if (posicao >= 0 && posicao < this.tamanho) {
Exception exception = new Exception("Posição ocupada.");
throw exception;
}
}
private void verificarPosicaoLivre(int posicao) throws Exception {
if (!(posicao >= 0 && posicao < this.tamanho)) {
Exception exception = new Exception("Posição desoculpada.");
throw exception;
}
}
private void verificarSeEstaVazio() throws Exception {
if (this.vazio()) {
Exception exception = new Exception("Está vazio.");
throw exception;
}
}
public Celula<E> getPrimeira() {
return primeira;
}
public void setPrimeira(Celula<E> primeira) {
this.primeira = primeira;
}
public Celula<E> getUltima() {
return ultima;
}
public void setUltima(Celula<E> ultima) {
this.ultima = ultima;
}
}
Ordenador.java
package br.com.estruturadedados.utilitario.ordenador;
public interface Ordenador<E extends Comparable<E>> {
public void bubbleSort();
public void insertionSort();
public void mergeSort();
}
OrdenadorListaSimplesmenteEncadeada.java
package br.com.estruturadedados.utilitario.ordenador;
public class OrdenadorListaSimplesmenteEncadeada<E extends Comparable<E>> implements Ordenador<E> {
private ListaSimplismenteEncadeada<E> lista;
private Celula<Integer> pirmeira;
private int tamanho;
public OrdenadorListaSimplesmenteEncadeada(Lista<E> lista) {
this.lista = (ListaSimplismenteEncadeada<E>) lista;
this.pirmeira = (Celula<Integer>) this.lista.getPrimeira();
this.tamanho = this.lista.tamanho();
}
@Override
public void bubbleSort() {
Celula<Integer> celulaAtual = this.pirmeira;
while (celulaAtual != null) {
Celula<Integer> proximaCelula = celulaAtual.getProxima();
while (proximaCelula != null) {
if (celulaAtual.getElemento() > proximaCelula.getElemento()) {
Integer elementoTemporario = celulaAtual.getElemento();
celulaAtual.setElemento(proximaCelula.getElemento());
proximaCelula.setElemento(elementoTemporario);
}
proximaCelula = proximaCelula.getProxima();
}
celulaAtual = celulaAtual.getProxima();
}
}
@Override
public void insertionSort() {
}
@Override
public void mergeSort() {
}
}
EstruturaDeDados.java
package br.com.estruturadedados;
public class EstruturaDeDados {
public static void main(String[] args) {
Lista<Integer> lista = new ListaSimplismenteEncadeada<>();
Random random = new Random();
int qtd = 100000;
for (int i = 0; i < qtd; i++) {
lista.adicionaInicio(random.nextInt(qtd * 10));
}
for (Integer i : lista) {
System.out.println(i);
}
Ordenador<Integer> ordenador = new OrdenadorListaSimplesmenteEncadeada<>(lista);
ordenador.insertionSort();
System.out.println("");
for (Integer i : lista) {
System.out.println(i);
}
}
}