Palestras (54 Berkeley) CS61B – Estrutura de Dados Usando Java – Aula 29: Sorting I | Programação

Por Daniel Cardoso Tavares

Neste vídeo, o professor Jonathan Shewchuk, que dá o curso de Estrutura de Dados, fala sobre:

• Insertion sort;
• Invariante: S está ordenada;
• O(n²)
• Se S for linked list, leva-se O(n) como pior tempo de execução para encontrar a posição correta;
• Se S for array: O(n) como pior tempo de execução;
• Se S for array, a insertion sort é in-place(pouco uso de memória adicional para o procedimento);
• Caminho reverso para inserir na nova posição;
• Se for uma BST, e O(n log n) <- não é utilizado por ser lento;
• Selection sort;
• Se S for array o lista encadeada, o tempo é O(n²) até no melhor caso;
• In-place também pode ser utilizado em selection sort;
• Heapsort: uma selection sort onde I é o heap;
• Heapsort roda em O(n log n);
• Heapsort também aceita in-place; é bom para arrays e ruim para listas encadeadas;
• Mergesort: oposto de heapsort: unir duas sortedlists em uma única;

Inicia-se com lista s & lista desorganizada I de n itens;
 
for(each item x em I)
{
	insert x em S, de forma ordenada.
}
 
 
for(i = 0; i < n; i++)
{	
	x <- item em I com a menor key;
	remove-se x de I;
	adicina-se x ao final de S; 
}
 
h.bottomUpHeap();
for(i=0; i<n ; pre >< } Q. de final o para atual lista da 2 e 1 item do menor mova item2="w2.front();" item1="q1.front();" { empty) is Q2 nor Q1 while(neither S; ao x="h.removeMin();" Adiciona i++)></n>

Acompanhe pelo Facebook: Profissionais de Jogos