Questões de Algoritmos e Estrutura de Dados - Algoritmos de Ordenação para Concurso

Medir a complexidade dos métodos de ordenação é fundamental para entender o desempenho desses algoritmos e poder fazer escolhas adequadas dependendo do contexto do problema. Qual método de ordenação o pior caso tem a mesma complexidade do método Quick Sort no pior caso?

Seja um array de inteiros de 32 bits com 10.000 elementos, gerados e posicionados aleatoriamente nesse array.
Nessas condições, qual algoritmo irá ordenar esse array com um consumo de tempo, em seu caso médio, proporcional ao consumo de tempo do pior caso do Quick sort?

Qual é o método de ordenação que percorre a lista de elementos, comparando os adjacentes (pares consecutivos) e trocando-os de posição, caso não estejam em ordem?

Considerando os algoritmos de ordenação, qual deles é considerado de ordenação popular e que funciona permutando repetidamente elementos adjacentes que estão fora de ordem? 

Relacione adequadamente as colunas a seguir sobre os métodos de ordenação à sua descrição correspondente.
1. Bubble Sort. 2. Merge Sort. 3. Quick Sort. 4. Selection Sort. 5. Insertion Sort.
( ) Divide a lista em sublistas menores; ordena essas sublistas e as mescla para obter a lista ordenada.
( ) Algoritmo de comparação que percorre repetidamente a lista; compara elementos adjacentes e troca-os se estiverem na ordem errada.
( ) Divide a lista em duas partes; ordena-as individualmente e combina-as para obter a lista ordenada.
( ) Algoritmo que seleciona iterativamente o elemento mínimo da lista e coloca-o na posição correta.
( ) Algoritmo de comparação que escolhe um elemento como pivô; divide a lista em dois subconjuntos e ordena-os recursivamente.
A sequência está correta em