Atividade - Estrutura de Dados 2

Prévia do material em texto

CURSO: Análise e desenvolvimento de sistemas 
POLO DE APOIO PRESENCIAL: Higienópolis 
SEMESTRE: 3° semestre 
COMPONENTE CURRICULAR / TEMA: ESTRUTURA DE DADOS 
NOME COMPLETO DO ALUNO: Maria Beatriz da Silva Souza 
TIA: 22516042 
NOME DO PROFESSOR: THIAGO DONIZETTI DOS SANTOS 
 
Algoritmo de Ordenação: Quick Sort 
 
O Quick Sort é um algoritmo de ordenação que utiliza a estratégia de "divisão e conquista" para ordenar 
elementos em uma lista ou array. Ele é um dos algoritmos de ordenação mais eficientes e é amplamente 
utilizado em aplicações reais devido à sua velocidade e eficiência. 
 
Funcionamento: 
 
 Escolha do Pivô: O primeiro passo do Quick Sort envolve a escolha de um elemento como pivô. O 
pivô é um elemento da lista que será usado para dividir a lista em duas partes menores. A escolha 
do pivô pode afetar o desempenho do algoritmo, e existem várias estratégias para selecionar o pivô, 
sendo a escolha do pivô médio uma delas. 
 
 Partição: Após a escolha do pivô, o algoritmo particiona a lista em duas partes: uma contendo 
elementos menores que o pivô e outra contendo elementos maiores. Isso é feito movendo os 
elementos menores para a esquerda do pivô e os elementos maiores para a direita. O pivô agora 
está na posição correta na lista ordenada. 
 
 Recursão: O passo de particionamento divide a lista original em duas sublistas menores. O Quick 
Sort é então aplicado recursivamente a cada uma dessas sublistas. Ou seja, o algoritmo é chamado 
 
novamente para ordenar as sublistas menores. Esse processo é repetido até que todas as sublistas 
tenham apenas um elemento, o que significa que a lista inteira está ordenada. 
 
 Combinação: À medida que as chamadas recursivas retornam e as sublistas são ordenadas, o 
Quick Sort combina essas sublistas em uma lista única, agora ordenada. Isso é feito concatenando 
as sublistas menores de forma apropriada. 
 
Pseudocódigo: 
função quickSort(lista): 
 se o tamanho da lista for menor ou igual a 1: 
 retorne a lista 
 senão: 
 escolha um elemento como pivô 
 particione a lista em elementos menores e maiores que o pivô 
 retorne quickSort(elementos menores) + pivô + quickSort(elementos maiores) 
 
Complexidade de Tempo/ Classe de complexidade assintótica: 
O Quick Sort possui um desempenho médio muito bom, com uma complexidade de tempo médio de O(n log 
n), onde "n" é o número de elementos na lista. No entanto, em seu pior caso, quando o pivô é sempre 
escolhido como o elemento mínimo ou máximo, a complexidade de tempo pode ser O(n^2). No entanto, o 
Quick Sort é frequentemente mais rápido na prática do que outros algoritmos de ordenação devido à sua 
natureza eficiente de divisão e conquista. 
 
Vantagens: 
 Eficiente na maioria dos casos. 
 Não requer armazenamento de elementos adicionais. 
 Adequado para ordenar grandes conjuntos de dados. 
 
Desvantagens: 
 Pode ter um desempenho ruim no pior caso. 
 Não é estável (a ordem relativa de elementos iguais pode não ser preservada). 
 
 
Código java: 
public class QuickSort { 
 
 public static void quickSort(int[] arr, int left, int right) { 
 if (left < right) { 
 int pivotIndex = partition(arr, left, right); 
 
 quickSort(arr, left, pivotIndex - 1); 
 quickSort(arr, pivotIndex + 1, right); 
 } 
 } 
 
 public static int partition(int[] arr, int left, int right) { 
 int pivot = arr[right]; 
 int i = left - 1; 
 
 for (int j = left; j < right; j++) { 
 if (arr[j] < pivot) { 
 i++; 
 swap(arr, i, j); 
 } 
 } 
 
 swap(arr, i + 1, right); 
 return i + 1; 
 } 
 
 public static void swap(int[] arr, int i, int j) { 
 
 int temp = arr[i]; 
 arr[i] = arr[j]; 
 arr[j] = temp; 
 } 
 
 public static void printArray(int[] arr) { 
 for (int num : arr) { 
 System.out.print(num + " "); 
 } 
 System.out.println(); 
 } 
 
 public static void main(String[] args) { 
 int[] arr = {12, 11, 13, 5, 6, 7}; 
 System.out.println("Array antes da ordenação:"); 
 printArray(arr); 
 
 quickSort(arr, 0, arr.length - 1); 
 
 System.out.println("Array depois da ordenação:"); 
 printArray(arr); 
 } 
}