Uma lista ordenada pode ser usada como um mecanismo de ordenação. Suponha que haja um vetor de itens de dados não ordenados.
Se os itens do vetor forem removidos e inseridos em uma lista ordenada, eles serão colocados em ordem classificada automaticamente. Se, então, forem removidos da lista e colocados de volta no vetor, o vetor estará ordenado.
A listagem abaixo apresenta a implementação de uma lista ordenada que pode ser utilizada para ordenar vetores. Considere a existência de uma parte do código, ainda não implementada, que está delimitada por comentários.
class linkElement {
public int number;
public linkElement next;
public linkElement (int number)
{ this.number = number;}
}
class SortedList {
private linkElement first;
public SortedList()
{ first = null; }
public SortedList(linkElement[] arr)
{
first = null;
for (int j = 0; j < arr.length; j++)
insert(arr[j]);
}
public void insert(linkElement lE)
{
linkElement previous = null;
linkElement current = first;
while (current != null && lE.number > current.number)
{
previous = current;
current = current.next;
}
//Inserir código não implementado.
}
public linkElement remove()
{
linkElement aux = first;
first = first.next;
return aux;
}
}
public class ListApp {
public static void main(String[] args)
{
int size = 10;
linkElement[] arr = new linkElement[size];
System.out.println("Vetor utilizado para testar o algoritmo");
arr[0] = new linkElement(5); arr[1] = new linkElement(2);
arr[2] = new linkElement(3); arr[3] = new linkElement(1);
arr[4] = new linkElement(6); arr[5] = new linkElement(4);
arr[6] = new linkElement(10); arr[7] = new linkElement(9);
arr[8] = new linkElement(8); arr[9] = new linkElement(7);
System.out.println("Vetor não ordenado:");
for(int j = 0; j < size; j++)
System.out.print(arr[j].number + " ");
System.out.println("");
SortedList sL = new SortedList(arr);
for(int j = 0; j < size; j++)
arr[j] = sL.remove();
System.out.println("Vetor ordenado:");
for(int j = 0; j < size; j++)
System.out.print(arr[j].number + " ");
}
}
Para que o código acima implemente corretamente o algoritmo como descrito no local determinado pelo comentário, deve ser incluído:
