Olá, TelmaSofia!
O bubble sort não exige a utilização de dois iteradores, vindo das extremidades um contra o outro. Como dá pra notar nesse pseudocódigo que você postou, ele consiste em fazer com que os maiores elementos venham a “emergir” na lista, tal qual bolhas dentro da água, daí o nome.
Esse método de ordenação percorre várias vezes a lista, sempre a partir do primiro elemento. Em cada “passada”, o algoritmo avança uma posição por vez. Em cada posição, ele analisa se a posição atual é maior que a posição seguinte. Se isto for verdade, o algoritmo traca os valores entre as posições atual e seguinte, fazendo com que o valor da posição atual seja menor que o valor da posição seguinte. E isto vai se repitindo até chegar à penultima posição, pois não tem sentido ir até a última, uma vez que a última posição já vai ser comparada com a penúltima. Depois disso, o algoritmo repete tudo novamente, deeeeeesde o início, e vai repetindo até que a lista esteja de fato ordenada.
Por exemplo, vou utilizar o Bubble Sort aqui para ordenar a seguinte lista:
[color=darkblue] 5 25 -63 52 3 0[/color]
Bom, vamos percorrer uma primeira vez esta lista e ir “borbulhando” o maior elemento pra frente:
[color=darkblue]
:arrow: 5 25 -63 52 3 0 -> Analisando posição 0: 5 < 25, então não mexe.
Fica :arrow: 5 25 -63 52 3 0 -> Analisando posição 1: 25 > -63, então troca.
Fica :arrow: 5 -63 25 52 3 0 -> Analisando posição 2: 25 < 52, então não mexe.
Fica :arrow: 5 -63 25 52 3 0 -> Analisando posição 3: 52 > 3, então troca.
Fica :arrow: 5 -63 25 3 52 0 -> Analisando posição 4(penúltima): 52 > 0, então troca.
Fica :arrow: 5 -63 25 3 0 52 -> Fim da primeira iteração.
[/color]
Perceba que nesta primeira passada, o maior elemento de todos foi parar na última posição, mas a lista continua desordenada. Então, é necessário que o buble sort percorra mais uma vez a lista:
[color=darkblue]
:arrow: 5 -63 25 3 0 52
:arrow: -63 5 25 3 0 52
:arrow: -63 5 25 3 0 52
:arrow: -63 5 3 25 0 52
:arrow: -63 5 3 0 25 52
:arrow: -63 5 3 0 25 52
[/color]
Veja que interessante: Agora, o segundo maior elemento de toda a lista, acabou indo para o fim da lista, ficando atrás apenas, evidentemente, do último elemento, que é ainda o maior de todos.
Creio que agora com mais duas passadas do algoritmo, a lista estará ordenada:
[color=darkblue]
:arrow: -63 5 3 0 25 52
:arrow: -63 5 3 0 25 52
:arrow: -63 3 5 0 25 52
:arrow: -63 3 0 5 25 52
:arrow: -63 3 0 5 25 52
:arrow: -63 3 0 5 25 52
:arrow: -63 3 0 5 25 52
:arrow: -63 0 3 5 25 52
:arrow: -63 0 3 5 25 52
:arrow: -63 0 3 5 25 52
:arrow: -63 0 3 5 25 52
[/color]
Note como o algoritmo Bubble sort faz os maiores elementos emergirem, “borbulharem” para o topo(fim) da lista.
Agora, analisando essa dinâmica, vemos que não há a necessidade de dois iteradores. Basta apenas um! Vemos também que devemos criar algum mecanismo para detectarmos que a lista já está ordenada por completo.
Olhando o pseudocódigo postado por você, podemos identificar nele alguns “personagens” desta esplicação até aqui:
:arrow: O laço do-while representa as passadas pela lista;
:arrow: O laço for representa a análise de cada um dos elementos da lista com o elemento seguinte
:arrow: A variável swapped é o mecanismo utilizado para verificar se a lista já está devidamente ordenada.
Este pseudocódigo acaba passando uma vez a mais na lista, sempre. Esta percorrida adicional (sempre a última) serve apenas para manter a variável swapped com o valor false, indicando que nenhum elemento da lista foi trocado, indicando por sua vez que a lista já está ordenada por completo.
Vamos ver como seria a dinâmica da ordenação, juntamente com o estado de swapped, ao ordenarmos nossa lista acima com o pseudocódigo apresentado:
[color=darkblue]
//1a. passada
:arrow: swapped <- false
:arrow: 5 25 -63 52 3 0
:arrow: 5 25 -63 52 3 0
:arrow: swapped <- true
:arrow: 5 -63 25 52 3 0
:arrow: 5 -63 25 52 3 0
:arrow: swapped <- true
:arrow: 5 -63 25 3 52 0
:arrow: swapped <- true
//2a. passada
:arrow: swapped <- false
:arrow: 5 -63 25 3 0 52
:arrow: swapped <- true
:arrow: -63 5 25 3 0 52
:arrow: -63 5 25 3 0 52
:arrow: swapped <- true
:arrow: -63 5 3 25 0 52
:arrow: swapped <- true
:arrow: -63 5 3 0 25 52
//3a. passada
:arrow: swapped <- false
:arrow: -63 5 3 0 25 52
:arrow: -63 5 3 0 25 52
:arrow: swapped <- true
:arrow: -63 3 5 0 25 52
:arrow: -63 3 0 5 25 52
:arrow: swapped <- true
:arrow: -63 3 0 5 25 52
//4a. passada
:arrow: swapped <- false
:arrow: -63 3 0 5 25 52
:arrow: -63 3 0 5 25 52
:arrow: swapped <- true
:arrow: -63 0 3 5 25 52
:arrow: -63 0 3 5 25 52
:arrow: -63 0 3 5 25 52
:arrow: -63 0 3 5 25 52
//5a. passada - Note que a lista já está ordenada…
:arrow: -63 0 3 5 25 52
:arrow: -63 0 3 5 25 52
:arrow: -63 0 3 5 25 52
:arrow: -63 0 3 5 25 52
:arrow: -63 0 3 5 25 52
//Como swapped se manteve com o valor false, o laço do-while é interrompido
FIM!!!
[/color]
Há formas de otimizar esse algoritmo, mas isso fica por sua conta, ok?
Agora, pra implementar isso utilizando sua lista, vai depender de como funciona essa sua lista. Vamos supor que ela seja algo assim:
public class SimpleHeadedLinkedList {
private Head head = new Head();
/*
* Métodos add, contains, remove, size, etc...
*/
private class Head{
private Node first = null;
private int size = 0;
public Node getFirst() {
return first;
}
public int getSize() {
return size;
}
public void setFirst(Node first) {
this.first = first;
}
public void setSize(int size) {
this.size = size;
}
}
public class Node implements Comparable<Node>{
private int value;
private Node next;
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
public Node getNext() {
return next;
}
public int getValue() {
return value;
}
public void setNext(Node next) {
this.next = next;
}
public void setValue(int value) {
this.value = value;
}
public int compareTo(Node other) {
if(other == null)
throw new ClassCastException("Can't compare with the given Node.");
return this.value - other.value;
}
}
}
Você pode agora criar dentro da classe SimpleHeadedLinkedList um método bubblesort que faça a ordenação da lista. A cada percorrida, você obtém o primeiro nó(Node) através da cabeça(Head), e então vai analisando se o nó atual - currentNode, digamos - é maior que o nó seguinte - currentNode.getNext(). Algo do estilo currentNode.compareTo(currentNode().getNext()) > 0. Aí, é só seguir o algoritmo.
Tente fazer agora. Qualquer dúvida, torne a postar, ok?
Divirta-se!
