PRG29003: A implementação da lista

Próxima aula

Conforme visto na etapa 1, uma lista encadeada é uma estrutura de dados em que os dados são armazenados dinamicamente em memória, de forma a se organizarem em uma sequência. Internamente, cada dado é armazenado em um elemento da lista denominado nodo, que funciona como uma caixa onde se guarda esse dado. Assim, para cada dado armazenado na lista existe um nodo. Cada nodo possui uma referência ao próximo nodo da lista, formando uma sequência parecida com os vagões de um trem. A figura abaixo ilustra uma lista encadeada:

Para se acessar uma lista, basta conhecer a referência para seu primeiro nodo (contida em seus atributos, como mostrado na figura acima). A partir do primeiro nodo pode-se percorrer a lista, seguindo as referências para os nodos subsequentes. Com isso, qualquer nodo da lista pode ser acessado.

Uma lista possui algumas propriedades:

• Os nodos são criados dinamicamente, à medida que for necessário. Assim, a quantidade total de memória usada para a lista depende da quantidade de dados nela armazenados (compare isso com um vetor ou matriz).
• A lista não precisa ocupar uma área de memória contígua: como nodos são alocados dinamicamente, eles podem ocupar áreas de memória arbitrárias, e não há nenhuma relação entre a localização dos nodos em memória e sua ordem na lista (novamente compare isso com um vetor ou matriz).
• Não é possível indexar os nodos, por isso para acessar um nodo deve-se obrigatoriamente procurá-lo a partir do início da lista, seguindo cada nodo até chegar àquele procurado.
• Para adicionar um nodo, basta modificar a referência do nodo que o antecede na lista. Assim, não é necessário "empurrar" os nodos seguintes para frente (como seria o caso de um vetor).
• Para remover um nodo é a mesma coisa: basta modificar a referência de seu nodo antecessor. Assim, não é necessário "deslocar pra trás" os nodos seguintes (como seria o caso de um vetor).

Listas simplesmente encadeadas

Um primeiro tipo de lista se chama simplesmente encadeada. Como diz seu nome, os nodos são encadeados de forma unidirecional. Pode-se percorrer a lista do primeiro em direção ao último nodo, mas não em direção contrária. A explicação apresentada na seção anterior focou nesse tipo de lista. Sua implementação no geral é mais simples.

Com base no que foi introduzido, a estrutura de dados lista pode ser definida da seguinte forma:

• atributos: pelo menos referências ao primeiro e ao último nodo
• operações: ao menos operações para adicionar, obter e remover dados da lista; mais especificamente:
  • anexa: adiciona um dado ao final da lista
  • insere: adiciona um dado em uma determinada posição da lista
  • remove: remove um dado de uma determinada posição da lista
  • obtem: obtém um dado de uma determinada posição da lista

A tradução dessa definição para a linguagem C++ pode ser vista a seguir:

Declaração e implementação da lista como uma classe template

template <typename T> class lista { public: //construtor: não precisa de parâmetros para criar uma nova lista lista(); // construtor de cópia lista(const lista &outra); // destrutor ~lista(); // insere "algo" no inicio da lista void insere(const T & algo); // adiciona "algo" no final da lista void anexa(const T & algo); // insere "algo" em uma posição específica da lista void insere(const T & algo, int posicao); void insereOrdenado(const T & algo); // remove o dado que está na "posicao" na lista, e retorna // uma cópia desse dado T remove(int posicao); // remove todos os dados que forem equivalentes a "algo" void retira(const T & algo); // estas duas operações são idênticas: retorna // uma referência ao dado que está na "posicao" na lista T& obtem(int posicao) const; T& operator[](int pos) const; // atribuição: torna esta lista idêntica à outra lista virtual lista& operator=(const lista<T> & outra); // compara duas listas: são iguais se tiverem mesmo comprimento // E todos os dados armazenados forem iguais e na mesma ordem bool operator==(const lista<T> & outra) const; // Retorna uma referência a um dado que seja equivalente a "algo" T& procura(const T &algo) const; // Procura todos os dados equivalentes a "algo", e os // anexa a "lista". Retorna uma referência a "lista". std::shared_ptr<lista<T>> procuraMuitos(const T &algo) const; lista<T> & procuraMuitos(const T &algo, lista<T> & lista) const; // retorna a quantidade de dados armazenados na lista int comprimento() const; // retorna true se lista estiver vazia bool vazia() const; // Esvazia a lista void esvazia(); // apresenta o conteúdo da lista no stream "out" void escrevaSe(std::ostream & out) const; void escrevaSe(std::ostream & out, const std::string & delim) const; // ordena a lista void ordena(); // iteração void inicia(); void iniciaPeloFim(); bool fim() const; bool inicio() const; T & proximo(); T & anterior(); // inverte a ordem dos dados da lista void inverte(); // embaralha os dados de uma lista void embaralha(); // obtém uma sublista lista<T> * sublista(unsigned int pos1, unsigned int pos2) const; lista<T> & sublista(unsigned int pos1, unsigned int pos2, lista<T> & outra) const; private: // declaração do tipo Nodo: privativa, porque // é de uso exclusivo da lista // Este Nodo visa uma lista duplamente encadeada struct Nodo { Nodo * proximo, * anterior; T dado; // construtor do Nodo: prático para uso nos métodos // da lista Nodo(const T & algo) { dado = algo; proximo = nullptr; anterior = nullptr; } }; // ponteiros para primeiro e último nodos Nodo * primeiro, * ultimo; // ponteiro para nodo atual da iteração Nodo * atual; // comprimento da lista long len; }; Arquivo libs/lista.h

OBS: a implementação dos métodos da lista está em libs/lista-impl.h.

Uma vez implementada essa lista básica, ela pode ser testada com este programa:

Programa para testar a lista
#include <iostream> #include <string> #include <prglib.h> using prglib::lista; using namespace std; int main() { lista<string> list; list.anexa("Uma"); list.anexa("coisa"); list.anexa("legal"); cout << "Comprimento: " << list.comprimento() << endl; for (int pos=0; pos < list.comprimento(); pos++) { cout << "Posicao " << pos; cout << ": " << list.obtem(pos) << endl; } }

Outros modelos de listas

Listas encadeadas podem ser implementadas com algumas variações. Duas delas bem conhecidas são:

• Lista duplamente encadeada: cada nodo aponta seu sucessor e antecessor. Esse tipo de lista facilita operações de inserção e remoção de nodos.

• Lista com guardas: guardas são nodos que não contém dados, mas servem para marcar lugares de interesse da lista. O caso mais comum é usar guardas no início e fim da lista, o que facilita a implementação de operações de inserção e remoção de nodos, pois essas operações não precisam tratar os casos último nodo ou primeiro nodo. Esse tipo de lista pode ser simplesmente ou duplamente encadeada.

CURIOSIDADE: como um processo usa a memória

Um processo, que é um programa em execução, usa memória para guardar tanto seus dados (variáveis e constantes) quanto suas instruções (o programa em si). A forma com que cada processo ocupa a memória depende do sistema operacional. No caso do Linux, o diagrama abaixo mostra de forma simplificada como um processo se organiza em memória (maiores detalhes no link abaixo da figura, e nas disciplina de Sistemas Operacionais da 5a fase ... e Microprocessadores da 4a fase também ajuda a entender essa questão).

Anatomia de um processo em memória
(obtido de http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory/)

Segundo esse diagrama, um processo aloca regiões de memória para diferentes finalidades. Por exemplo, as instruções de programa ficam no segmento Text, as variáveis dinâmicas alocadas com malloc (linguagem C) ou operador new (C++) ficam no segmento heap, e as variáveis locais e argumentos de função ficam em stack.

Experimento: alocação de memória

Compile e use os dois programas a seguir para comparar as limitações na alocação de memória na pilha e no heap.

• Alocação na pilha
• Alocação no heap

Atividade

Implemente as operações da lista necessárias para que o programa de teste funcione.

• Arquivo do Netbeans com a Prglib

Operações que acrescentam e removem conteúdo

Como visto na etapa 1, existem operações que acrescentam ou removem dados da lista. Uma delas já foi vista na introdução, que acrescenta um novo dado ao final da lista (operação anexa). Outras operações desse tipo comumente usadas são:

• insere: insere um dado no início ou em uma posição qualquer
• remove: remove um dado de uma posição qualquer
• esvazia: esvazia a lista

Um exemplo de uso de insere pode ser visto neste pequeno programa:

#include <iostream>
#include <string>
#include <prglib.h>
 
using prglib::lista;
 
using namespace std;
 
int main() {
  lista<string> list;
 
  list.anexa("Uma");
  list.anexa("coisa");
  list.anexa("legal");
  list.insere("Mais");

  cout << "Comprimento: " << list.comprimento() << endl;
  for (int pos=0; pos < list.comprimento(); pos++) {
    cout << "Posicao " << pos;
    cout << ": " << list.obtem(pos) << endl;
  }
 
}

Outro programa de teste para a lista: anexa, insere, obtem, remove, esvazia

#include <iostream> #include <string> #include <prglib.h> using prglib::lista; using namespace std; void mostraLista(lista<string> & l) { int len = l.comprimento(); cout << "Comprimento: " << len << endl; int pos = 0; while (pos < len) { string algo = l.remove(0); l.anexa(algo); cout << "Posicao " << pos; cout << ": " << algo << endl; pos++; } } int main() { lista<string> l; l.anexa("coisa"); l.anexa("legal"); l.insere("Uma"); mostraLista(l); cout << endl; l.insere("muito", 2); mostraLista(l); cout << endl; string palavra = l.remove(2); cout << "Removeu: " << palavra << endl; mostraLista(l); cout << endl; l.esvazia(); cout << "Após esvaziar: " << endl; mostraLista(l); cout << endl; return 0; }

Atividade

Implemente as operações insere, remove e esvazia, de forma que os programas de teste funcionem.

Operações que percorrem os dados da lista

Apresentação do conteúdo de uma lista

No programa de teste da seção anterior, foi adicionada uma função void mostraLista(lista<string> & l). Essa função simplesmente apresenta cada dado da lista em uma linha. Tal tipo de necessidade deve ser comum a diferentes programas que usam listas, portanto poderia se tornar uma operação da lista. Além disso, faz sentido que uma lista saiba se apresentar na tela ou gravar-se em um arquivo. Essa operação poderia ser definida como os seguintes métodos da classe lista:

// escreve em "out" o conteúdo da lista (um dado por linha)
void escrevaSe(ostream & out);

// escreve em "out" o conteúdo da lista (dados separados por "delimitador")
void escrevaSe(ostream & out, const string & delimitador);

... sendo o parâmetro ostream& out um arquivo aberto em modo escrita (cout serviria, por exemplo).

OBS: pode ser útil saber como funciona a sobrecarga de operadores em C++, uma vez que o operador << para objetos ostream (tais como cout e arquivos abertos para escrita) deve ser definido para tipos de dados e classes criados pelo usuário. Do contrário, escrevaSe não funcionará para esses tipos de dados.

Exercícios

1. Implemente o método escrevaSe
2. Modifique o programa de teste para que use o método escrevaSe

Iterador da lista

A iteração é uma forma de percorrer sucessivamente os dados de uma lista. A iteração inicia com o acesso ao primeiro dado, e próximas iterações retornam os dados seguintes, na ordem em que estão armazenados na lista. Isso é feito por meio de três operações da lista:

• inicia: inicia a iteração.
• proximo: retorna uma referência ao dado contido no nodo atual, e avança para o próximo nodo. Caso não exista nodo atual (i.e. seja o fim da lista), deve-se gerar uma exceção.
• fim: informa se a iteração chegou ao fim e, portanto, não há mais dados para retornar.

Para fazer a iteração, além de possuir essas novas operações a lista deve lembrar em que nodo a iteração está a cada momento. O atributo atual da classe lista serve exatamente para isso. Abaixo pode-se ver a classe lista, destacando-se somente os métodos e atributos usados na interação.

template <class T> class lista {
 public:
  // operações da lista

  // métodos envolvidos na iteração:

  // inicia uma iteração
  void inicia();

  // retorna uma referência ao próximo dado da iteração
  // se não houver mais dados, gera uma exceção
  T& proximo();

  // retorna verdadeiro se a iteração terminou (chegou ao fim da lista)
  bool fim() const;

 private: 
  // o nodo atual da iteração: este novo atributo torna possível
  // que a lista lembre em que nodo a iteração está a cada momento
  Nodo * atual;
  // demais atributos da lista
};

Note que a iteração implica fazer com que o novo atributo atual aponte sucessivamente os nodos da lista. Isso deve funcionar assim:

• após inicia() , o nodo atual é o primeiro nodo.
• se for executado proximo() em seguida, obtém-se uma referência ao dado contido no nodo atual (primeiro nodo), e ao final de sua execução atual aponta o segundo nodo da lista.
• se for executado proximo() novamente, obtém-se uma referência ao dado contido no nodo atual (segundo nodo), e ao final de sua execução, atual aponta o terceiro nodo da lista.
• ... e assim por diante.

Com isso, ao final a operação proximo() deve retornar uma referência ao dado guardado no nodo apontado por atual.

Uma vez existindo o iterador, podem-se percorrer os dados da lista como mostrado neste exemplo:

// encontra a menor string (por ordem alfabética)
string minimo(lista<string> & l) {
  if (l.comprimento() < 1) throw -1; // erro: lista vazia !

  l.inicia();
  string menor = l.proximo();
  
  while (not l.fim()) {
    string & dado = l.proximo();
    if (dado < menor) menor = dado;
  }
  return menor;
}

Outro exemplo usa o iterador para mostrar os dados da lista (com resultado igual ao do método escrevaSe):

void mostraLista(lista<string> & l, ostream & out) {
  l.inicia();
  
  while (not l.fim()) {
    string & dado = l.proximo();
    out << dado << endl;
  }  
}

Exercícios

1. Implemente o iterador da lista
2. Teste o iterador da lista com os programa exemplo mostrados nesta seção
3. Implemente o iterador reverso da lista, que itera os dados do fim para o início da lista. Os métodos envolvidos são: iniciaPeloFim, anterior e inicio (ver lista.h)

Algoritmos de ordenamento

Listas armazenam conjuntos de dados e, usualmente, existe a necessidade de ordená-los. O ordenamento de uma lista pode ser realizado de diferentes maneiras, sendo apresentados aqui dois algoritmos elementares, porém ineficientes, e um terceiro algoritmo não tão simples, porém bastante eficiente.

Escolhendo a estratégia de ordenamento

• Um sumário de algoritmos de ordenamento na Wikipedia

Uma lista pode ser ordenada de mais de uma forma. Aqui veremos três formas de ordenamento (e existem outras):

• Algoritmo bubble-sort: aplica-se a uma lista já existente, e não requer memória adicional para ordená-la.
• Algoritmo selection-sort: parecido com bubble sort, porém com uma pequena melhoria que reduz um pouco o tempo de ordenamento.
• Algoritmo merge-sort: usa uma estratégia do tipo dividir-e-conquistar para acelerar o tempo de ordenamento. Divide uma lista ao meio sucessivamente, até que se gerem sublistas com apenas um dado. Em seguida, funde essas sublistas de forma ordenada.

Algoritmo de ordenamento bolha (bubble sort)

O algoritmo bubble sort usa a seguinte estratégia para ordenar uma lista (ou vetor):

• Desloca o maior valor em direção ao último nodo da lista
• Desloca o 2o maior valor em direção ao penúltimo nodo da lista
• Desloca o 3o maior valor em direção ao antepenúltimo nodo da lista
• ... e assim por diante

Uma animação do algoritmo, obtida no verbete Bubble Sort na Wikipedia

Esse algoritmo pode ser representado pelo seguinte pseudo-programa:

para j do fim da lista até o segundo nodo da lista
  para k do inicio da lista até o antecessor do nodo j
    se nodo k+1 < nodo k então troca os valores dos nodos k e k+1
  fim para
fim para

Exemplo que demonstra o bubble sort em C++, aplicado a um vetor de strings
#include <iostream> #include <string> using namespace std; int main() { string v[5] = {"zebra", "mamute", "leao", "tatu", "tainha"}; int j, k; for (j=4; j > 0; j--) { for (k=0; k < j; k++) { if (v[k+1] < v[k]) { // troca ! string aux = v[k]; v[k] = v[k+1]; v[k+1] = aux; } } } // mostrar o resultado for (j=0; j < 5; j++) cout << "v[" << j << "] = " << v[j] << endl; return 0; }

Bubble-sort é uma das forma mais simples de ordenar uma lista ou vetor (mas não a mais eficiente).

Algoritmo de ordenamento por seleção (selection sort)

O ordenamento por seleção se apresenta como uma variação do bubble sort. Ele usa esta abordagem:

• Identifica o menor valor a partir da 1a posição da lista e coloca-o na 1a posição
• Identifica o menor valor a partir da 2a posição da lista e coloca-o na 2a posição
• Identifica o menor valor a partir da 3a posição da lista e coloca-o na 3a posição
• Identifica o menor valor a partir da n-ésima posição da lista e coloca-o na n-ésima posição

Esse algoritmo poderia ser implementado de acordo com este pseudo-código:

para j do inicio da lista até o penúltimo nodo da lista
  menor = nodo na posição j
  para k da posicao j+1 até o fim da lista
    se valor do nodo k < valor do nodo menor então menor = nodo k
  fim para
  troca valores dos nodos j e menor
fim para

Exemplo que demonstra o ordenamento por seleção em C++, aplicado a um vetor de strings

#include <iostream> #include <string> using namespace std; int main() { string v[5] = {"zebra", "mamute", "leao", "tatu", "tainha"}; int j, k; for (j=0; j < 4; j++) { int menor = j; for (k=j+1; k < 5; k++) { if (v[menor] > v[k]) menor = k; } if (menor != j) { string aux = v[j]; v[j] = v[menor]; v[menor] = aux; } } // mostrar o resultado for (j=0; j < 5; j++) cout << "v[" << j << "] = " << v[j] << endl; return 0; }

Ele pode ser exemplificado pela figura abaixo, que mostra o ordenamento de uma lista ou vetor contendo 4 valores. As posições verdes correspondem à parte da lista que já está ordenada, e as posições vermelhas são os valores que estão sendo comparados; as setas entre posições vermelhas indicam quando deve ser feita uma operação de troca de valores.

Algoritmo de ordenamento por fusão (merge sort)

O algoritmo de ordenamento por fusão usa uma estratégia de dividir e conquistar da seguinte forma:

1. Subdivide-se uma lista em duas sublistas sucessivamente, até que se obtenha um conjunto de sublistas de comprimento 1.
2. Os pares de sublistas são fundidos sucessivamente, cuidando-se para que, após cada fusão, a sublista resultante esteja ordenada
3. Quando todas as sublistas tiverem sido fundidas, a lista resultante estará ordenada.

Este algoritmo pode ser implementado eficientemente para listas. A versão mostrada como exemplo a seguir se aplica a vetores. A versão adequada para listas pode ser bem melhor, explorando as ligações entre nodos e assim evitando cópias dos dados.

Exemplo de implementação em C++ para ordenar um vetor de string

#include <iostream> #include <string> using namespace std; // m: posicao inicial, n: posicao final void merge(string * v, int m, int n) { int meio; // descomente se quiser ver o inicio e fim de cada sublista //cout << m << "," << n << endl; // se fatia tem um elemento, retorna if (n == m) return; // divide em duas fatias. Observe que isso implica // chamar merge recursivamente meio = (n-m)/2; merge(v, m, m+meio); merge(v, m+meio+1, n); // funde as fatias, que estao ordenadas // a fusao eh feita em um vetor auxiliar // e depois copiada para o vetor principal string aux[n-m+1]; // k: indexa o vetor auxiliar, i: indexa a primeira fatia, // j: indexa a segunda fatia int i, j, k; for (k=0, i=m, j=m+meio+1; i <= m+meio and j <= n; k++) { if (v[i] < v[j]) { aux[k] = v[i]; i++; } else { aux[k] = v[j]; j++; } } // sobras da fusao devem ser anexadas ao vetor auxiliar for (; i <= m+meio; i++, k++) aux[k] = v[i]; for (; j <= n; j++, k++) aux[k] = v[j]; // copia o vetor auxiliar para o vetor principal for (k=0; k < (n-m+1); k++) v[m+k] = aux[k]; } int main() { string v[9] = {"zebra", "mamute", "leao", "tatu", "tainha", "anta", "anchova", "burro","gamba"}; int j, k; merge(v, 0, 8); // mostrar o resultado for (j=0; j < 9; j++) cout << "v[" << j << "] = " << v[j] << endl; return 0; }

Implementação dos ordenamentos na lista encadeada

A lista encadeada criada até o momento não possui todas as funcionalidades necessárias para que possa ser ordenada. Dependendo do algoritmo de ordenamento, algumas operações precisam ser implementadas.

Bubble Sort

O ordenamento bubble sort ordena uma lista já existente. Para implementá-lo, torna-se necessária a operação ordenaBolha, que efetua o ordenamento de uma lista. Essa operação pode ser declarada da seguinte forma:

// Método ordenaBolha: faz o ordenamento de uma lista usando bubble sort
void ordenaBolha();

Selection Sort

O ordenamento selection sort ordena uma lista já existente. Para implementá-lo, torna-se necessária a operação ordenaSelecao, que efetua o ordenamento de uma lista. Essa operação pode ser declarada da seguinte forma:

// Método ordenaSelecao: faz o ordenamento de uma lista usando bubble sort
void ordenaSelecao();

Merge Sort

No caso de Merge Sort, torna-se necessária um método privativo da lista para realizar a subdivisão e subsequente fusão de um trecho da lista. Sendo um método privativo, ele pode explorar os nodos para realizar a fusão.

// n1: nodo inicial do trecho a ser ordenado
// n2: nodo final do trecho a ser ordenado
// n: comprimento do trecho da lista a ser ordenado
void merge(Nodo * n1, Nodo * n2, int n);

O método público ordena_fusao deve ser invocado para ordenar a lista. Esse método nada mais faz que chamar o método merge apropriadamente para de fato realizar o ordenamento.

void ordenaFusao() {
  if (len < 2) return;

  merge(primeiro, ultimo, len);
}

Atividade

1. Implemente os três algoritmos de ordenamento. Teste-os com este programa (modifique-o para cada um dos algoritmos de ordenamento):

   #include <iostream>
   #include <string>
   #include <prglib.h>
   
   using prglib::lista;
   
   using namespace std;
   
   int main() {
     lista<int> l1;
     lista<string> l2;
   
     l1.anexa(67);
     l1.anexa(2343);
     l1.anexa(112);
     l1.anexa(83725);
     l1.anexa(459);
     l1.anexa(23856);
   
     l1.ordena();
     l1.escrevaSe(cout);
   
     cout << endl;
   
     l2.anexa("um");
     l2.anexa("teste");
     l2.anexa("do");
     l2.anexa("ordenamento");
     l2.anexa("seilaqual");
     l2.anexa("da");
     l2.anexa("lista");
   
     l2.ordena();
     l2.escrevaSe(cout);
     cout << endl;
   }
   

2. Compare os três ordenamentos quanto ao tempo que demoram para ordenar uma lista. Você pode criar uma lista de inteiros gerados aleatoriamente, ou uma lista de strings onde se guardam palavras de um arquivo. Crie listas com ao menos 50 mil dados ...

Abaixo segue um exemplo de comparação. O algoritmo merge-sort é utilizado para ordenar listas na linguagem Python:

Comparação entre os ordenamentos para listas contendo entre 5 mil e 120 mil dados aleatórios.

Comparação entre os ordenamentos feitos com merge-sort em C++ (prglib), e com uma lista na linguagem Python (nesse caso, usou-se o ordenamento já existente para essa lista), e list e vector C++ (implementados na STL).

Outras operações

Inversão

A operação de inversão reverte a sequência dos dados na lista: o primeiro se torna o último e vice-versa, o segundo o penúltimo e vice-versa, e assim por diante. Essa operação é implementada pelo método void inverte(), e possui baixa complexidade. Ela pode ser implementada em tempo linear (custo computacional $\theta (n)$), e não precisa de memória adicional (quer dizer, criar outra lista). Ela pode ser facilmente realizada tanto com listas simplesmente encadeadas quanto duplamente encadeadas.

Embaralhamento

A lista possui uma operação que mistura aleatoriamente seus dados. Essa operação é implementada pelo método void embaralha(). Cada vez que esse método é executado, a sequência dos dados na lista é modificada de forma randômica.

Há mais de uma forma de embaralhar uma lista. Uma primeira abordagem é o algoritmo Fisher-Yates (também chamado de Knuth), de razoável simplicidade porém com custo de tempo computacional $\theta (n^{2})$ (ver também esta boa discussão sobre custos desses algoritmos). Outra abordagem se baseia no algoritmo de ordenamento merge sort, porém trocando a posição dos valores aleatoriamente ao invés de compará-los. Esse outro algoritmo é mais facilmente implementado em listas duplamente encadeadas, e tem custo computacional $\theta (n~log~n)$, bem inferior ao Knuth. Sobre isso, no artigo sobre comparação de algoritmos de embaralhamento há esta explicação:

One simple O(n log n) shuffle algorithm is an adapted merge sort: shuffle the left half, then the right half, then merge them by randomly selecting from the two lists. To ensure all permutations are equally likely, elements should be selected according to the Gilbert–Shannon–Reeds model probabilities. While the recursive version of this takes O(log n) space due to stack usage, the iterative version is just O(1) space (thanks Mark Gordon for pointing this out). For an actual implementation, see my answer on stackoverflow.com.