É um fato bem estabelecido que a classificação por mesclagem é executada mais rapidamente do que a classificação por inserção. Usando análise assintótica . podemos provar que a classificação por mesclagem é executada em tempo O (nlogn) e a classificação por inserção leva O (n ^ 2). É óbvio porque a classificação por mesclagem usa uma abordagem de dividir e conquistar, resolvendo recursivamente os problemas onde a classificação por inserção segue uma abordagem incremental. Se examinarmos ainda mais a análise de complexidade de tempo, saberemos que a classificação por inserção não é tão ruim o suficiente. Surpreendentemente, a classificação por inserção é melhor que a classificação por mesclagem em tamanhos de entrada menores. Isso ocorre porque existem poucas constantes que ignoramos ao deduzir a complexidade do tempo. Em tamanhos de entrada maiores, da ordem 10^4, isso não influencia o comportamento de nossa função. Mas quando os tamanhos de entrada caem abaixo de, digamos, menos de 40, então as constantes na equação dominam o tamanho de entrada ‘n’. Até agora tudo bem. Mas não fiquei satisfeito com essa análise matemática. Como estudantes de ciência da computação, devemos acreditar em escrever código. Escrevi um programa em C para ter uma ideia de como os algoritmos competem entre si por vários tamanhos de entrada. E também por que uma análise matemática tão rigorosa é feita para estabelecer as complexidades do tempo de execução desses algoritmos de classificação.
ovos de páscoa no android
Implementação:
CPP#include
import java.util.Scanner; import java.util.Arrays; import java.util.Random; public class SortingAlgorithms { // Maximum element in array static final int MAX_ELEMENT_IN_ARRAY = 1000000001; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); for (int i = 0; i < t; i++) { int size = scanner.nextInt(); int num_of_times = scanner.nextInt(); testSortingRuntimes(size num_of_times); } scanner.close(); } static int[] generateRandomArray(int n) { // Generate an array of n random integers. int[] arr = new int[n]; Random random = new Random(); for (int i = 0; i < n; i++) { arr[i] = random.nextInt(MAX_ELEMENT_IN_ARRAY); } return arr; } static void insertionSortAsc(int[] a int start int end) { // Perform an in-place insertion sort on a from start to end. for (int i = start + 1; i <= end; i++) { int key = a[i]; int j = i - 1; while (j >= start && a[j] > key) { a[j + 1] = a[j]; j--; } a[j + 1] = key; } } static void merge(int[] a int start int end int mid) { // Merge two sorted sublists of a. // The first sublist is a[start:mid+1] and the second sublist is a[mid+1:end+1]. int[] aux = new int[end - start + 1]; int i = start j = mid + 1 k = 0; while (i <= mid && j <= end) { if (a[i] <= a[j]) { aux[k++] = a[i++]; } else { aux[k++] = a[j++]; } } while (i <= mid) { aux[k++] = a[i++]; } while (j <= end) { aux[k++] = a[j++]; } System.arraycopy(aux 0 a start aux.length); } static void mergeSort(int[] a) { // Perform an in-place merge sort on a. mergeSortHelper(a 0 a.length - 1); } static void mergeSortHelper(int[] a int start int end) { // Recursive merge sort function. if (start < end) { int mid = start + (end - start) / 2; mergeSortHelper(a start mid); mergeSortHelper(a mid + 1 end); merge(a start end mid); } } static void insertionAndMergeSortCombine(int[] a int start int end int k) { /* Perform an in-place sort on a from start to end. If the size of the list is less than or equal to k use insertion sort. Otherwise use merge sort. */ if (start < end) { int size = end - start + 1; if (size <= k) { insertionSortAsc(a start end); } else { int mid = start + (end - start) / 2; insertionAndMergeSortCombine(a start mid k); insertionAndMergeSortCombine(a mid + 1 end k); merge(a start end mid); } } } static void testSortingRuntimes(int size int num_of_times) { // Test the runtime of the sorting algorithms. double insertionSortTime = 0; double mergeSortTime = 0; double mergeSortAndInsertionSortMixTime = 0; double qsortTime = 0; for (int i = 0; i < num_of_times; i++) { int[] a = generateRandomArray(size); int[] b = Arrays.copyOf(a a.length); long start = System.currentTimeMillis(); insertionSortAsc(b 0 b.length - 1); long end = System.currentTimeMillis(); insertionSortTime += end - start; int[] c = Arrays.copyOf(a a.length); start = System.currentTimeMillis(); mergeSort(c); end = System.currentTimeMillis(); mergeSortTime += end - start; int[] d = Arrays.copyOf(a a.length); start = System.currentTimeMillis(); insertionAndMergeSortCombine(d 0 d.length - 1 40); end = System.currentTimeMillis(); mergeSortAndInsertionSortMixTime += end - start; int[] e = Arrays.copyOf(a a.length); start = System.currentTimeMillis(); Arrays.sort(e); end = System.currentTimeMillis(); qsortTime += end - start; } insertionSortTime /= num_of_times; mergeSortTime /= num_of_times; mergeSortAndInsertionSortMixTime /= num_of_times; qsortTime /= num_of_times; System.out.println('nTime taken to sort:n' + '(i) Insertion sort: ' + insertionSortTime + 'n' + '(ii) Merge sort: ' + mergeSortTime + 'n' + '(iii) Insertion-mergesort-hybrid: ' + mergeSortAndInsertionSortMixTime + 'n' + '(iv) Qsort library function: ' + qsortTime + 'n'); } }
import time import random import copy from typing import List # Maximum element in array MAX_ELEMENT_IN_ARRAY = 1000000001 def generate_random_array(n: int) -> List[int]: #Generate a list of n random integers. return [random.randint(0 MAX_ELEMENT_IN_ARRAY) for _ in range(n)] def insertion_sort_asc(a: List[int] start: int end: int) -> None: #Perform an in-place insertion sort on a from start to end. for i in range(start + 1 end + 1): key = a[i] j = i - 1 while j >= start and a[j] > key: a[j + 1] = a[j] j -= 1 a[j + 1] = key def merge(a: List[int] start: int end: int mid: int) -> None: #Merge two sorted sublists of a. #The first sublist is a[start:mid+1] and the second sublist is a[mid+1:end+1]. aux = [] i = start j = mid + 1 while i <= mid and j <= end: if a[i] <= a[j]: aux.append(a[i]) i += 1 else: aux.append(a[j]) j += 1 while i <= mid: aux.append(a[i]) i += 1 while j <= end: aux.append(a[j]) j += 1 a[start:end+1] = aux def _merge_sort(a: List[int] start: int end: int) -> None: #Recursive merge sort function. if start < end: mid = start + (end - start) // 2 _merge_sort(a start mid) _merge_sort(a mid + 1 end) merge(a start end mid) def merge_sort(a: List[int]) -> None: #Perform an in-place merge sort on a. _merge_sort(a 0 len(a) - 1) def insertion_and_merge_sort_combine(a: List[int] start: int end: int k: int) -> None: ''' Perform an in-place sort on a from start to end. If the size of the list is less than or equal to k use insertion sort. Otherwise use merge sort. ''' if start < end: size = end - start + 1 if size <= k: insertion_sort_asc(a start end) else: mid = start + (end - start) // 2 insertion_and_merge_sort_combine(a start mid k) insertion_and_merge_sort_combine(a mid + 1 end k) merge(a start end mid) def test_sorting_runtimes(size: int num_of_times: int) -> None: #Test the runtime of the sorting algorithms. insertion_sort_time = 0 merge_sort_time = 0 merge_sort_and_insertion_sort_mix_time = 0 qsort_time = 0 for _ in range(num_of_times): a = generate_random_array(size) b = copy.deepcopy(a) start = time.time() insertion_sort_asc(b 0 len(b) - 1) end = time.time() insertion_sort_time += end - start c = copy.deepcopy(a) start = time.time() merge_sort(c) end = time.time() merge_sort_time += end - start d = copy.deepcopy(a) start = time.time() insertion_and_merge_sort_combine(d 0 len(d) - 1 40) end = time.time() merge_sort_and_insertion_sort_mix_time += end - start start = time.time() a.sort() end = time.time() qsort_time += end - start insertion_sort_time /= num_of_times merge_sort_time /= num_of_times merge_sort_and_insertion_sort_mix_time /= num_of_times qsort_time /= num_of_times print(f'nTime taken to sort:n' f'(i)Insertion sort: {insertion_sort_time}n' f'(ii)Merge sort: {merge_sort_time}n' f'(iii)Insertion-mergesort-hybrid: {merge_sort_and_insertion_sort_mix_time}n' f'(iv)Qsort library function: {qsort_time}n') def main() -> None: t = int(input()) for _ in range(t): size num_of_times = map(int input().split()) test_sorting_runtimes(size num_of_times) if __name__ == '__main__': main()
// Importing required modules const { performance } = require('perf_hooks'); // Maximum element in array const MAX_ELEMENT_IN_ARRAY = 1000000001; // Function to generate a list of n random integers function generateRandomArray(n) { return Array.from({length: n} () => Math.floor(Math.random() * MAX_ELEMENT_IN_ARRAY)); } // Function to perform an in-place insertion sort on a from start to end function insertionSortAsc(a start end) { for (let i = start + 1; i <= end; i++) { let key = a[i]; let j = i - 1; while (j >= start && a[j] > key) { a[j + 1] = a[j]; j -= 1; } a[j + 1] = key; } } // Function to merge two sorted sublists of a function merge(a start end mid) { let aux = []; let i = start; let j = mid + 1; while (i <= mid && j <= end) { if (a[i] <= a[j]) { aux.push(a[i]); i += 1; } else { aux.push(a[j]); j += 1; } } while (i <= mid) { aux.push(a[i]); i += 1; } while (j <= end) { aux.push(a[j]); j += 1; } for (let i = start; i <= end; i++) { a[i] = aux[i - start]; } } // Recursive merge sort function function _mergeSort(a start end) { if (start < end) { let mid = start + Math.floor((end - start) / 2); _mergeSort(a start mid); _mergeSort(a mid + 1 end); merge(a start end mid); } } // Function to perform an in-place merge sort on a function mergeSort(a) { _mergeSort(a 0 a.length - 1); } // Function to perform an in-place sort on a from start to end function insertionAndMergeSortCombine(a start end k) { if (start < end) { let size = end - start + 1; if (size <= k) { insertionSortAsc(a start end); } else { let mid = start + Math.floor((end - start) / 2); insertionAndMergeSortCombine(a start mid k); insertionAndMergeSortCombine(a mid + 1 end k); merge(a start end mid); } } } // Function to test the runtime of the sorting algorithms function testSortingRuntimes(size numOfTimes) { let insertionSortTime = 0; let mergeSortTime = 0; let mergeSortAndInsertionSortMixTime = 0; let qsortTime = 0; for (let _ = 0; _ < numOfTimes; _++) { let a = generateRandomArray(size); let b = [...a]; let start = performance.now(); insertionSortAsc(b 0 b.length - 1); let end = performance.now(); insertionSortTime += end - start; let c = [...a]; start = performance.now(); mergeSort(c); end = performance.now(); mergeSortTime += end - start; let d = [...a]; start = performance.now(); insertionAndMergeSortCombine(d 0 d.length - 1 40); end = performance.now(); mergeSortAndInsertionSortMixTime += end - start; start = performance.now(); a.sort((a b) => a - b); end = performance.now(); qsortTime += end - start; } insertionSortTime /= numOfTimes; mergeSortTime /= numOfTimes; mergeSortAndInsertionSortMixTime /= numOfTimes; qsortTime /= numOfTimes; console.log(`nTime taken to sort:n(i)Insertion sort: ${insertionSortTime}n(ii)Merge sort: ${mergeSortTime}n(iii)Insertion-mergesort-hybrid: ${mergeSortAndInsertionSortMixTime}n(iv)Qsort library function: ${qsortTime}n`); } // Main function function main() { let t = parseInt(prompt('Enter the number of test cases: ')); for (let _ = 0; _ < t; _++) { let size = parseInt(prompt('Enter the size of the array: ')); let numOfTimes = parseInt(prompt('Enter the number of times to run the test: ')); testSortingRuntimes(size numOfTimes); } } // Call the main function main();
Comparei os tempos de execução dos seguintes algoritmos:
loop do e while em java
- Classificação de inserção : O algoritmo tradicional sem modificações/otimização. Ele funciona muito bem para tamanhos de entrada menores. E sim, supera a classificação por mesclagem
- Vai o destino : Segue a abordagem de dividir para conquistar. Para tamanhos de entrada da ordem 10 ^ 5, este algoritmo é a escolha certa. Isso torna a classificação por inserção impraticável para tamanhos de entrada tão grandes.
- Versão combinada de classificação por inserção e classificação por mesclagem: Ajustei um pouco a lógica da classificação por mesclagem para obter um tempo de execução consideravelmente melhor para tamanhos de entrada menores. Como sabemos, o merge sort divide sua entrada em duas metades até que seja trivial o suficiente para classificar os elementos. Mas aqui, quando o tamanho da entrada cai abaixo de um limite como 'n'< 40 then this hybrid algorithm makes a call to traditional insertion sort procedure. From the fact that insertion sort runs faster on smaller inputs and merge sort runs faster on larger inputs this algorithm makes best use both the worlds.
- Classificação rápida: Eu não implementei este procedimento. Esta é a função da biblioteca qsort() que está disponível em . Considerei esse algoritmo para saber a importância da implementação. É necessário muito conhecimento de programação para minimizar o número de etapas e fazer uso máximo das primitivas da linguagem subjacente para implementar um algoritmo da melhor maneira possível. Esta é a principal razão pela qual é recomendado o uso de funções de biblioteca. Eles foram escritos para lidar com tudo e qualquer coisa. Eles otimizam ao máximo possível. E antes que eu esqueça da minha análise, qsort() é executado extremamente rápido em praticamente qualquer tamanho de entrada!
A Análise:
- Entrada: O usuário deve fornecer o número de vezes que deseja testar o algoritmo correspondente ao número de casos de teste. Para cada caso de teste, o usuário deve inserir dois números inteiros separados por espaço, denotando o tamanho da entrada 'n' e 'num_of_times', denotando o número de vezes que ele deseja executar a análise e calcular a média. (Esclarecimento: se 'num_of_times' for 10, então cada um dos algoritmos especificados acima é executado 10 vezes e a média é obtida. Isso é feito porque a matriz de entrada é gerada aleatoriamente correspondendo ao tamanho de entrada que você especifica. A matriz de entrada pode ser toda classificada. Nosso pode corresponder ao pior caso, ou seja, ordem decrescente. Para evitar tempos de execução de tais matrizes de entrada. O algoritmo é executado 'num_of_times' e a média é obtida.) rotina clock() e A macro CLOCKS_PER_SEC de é usada para medir o tempo gasto. Compilação: Escrevi o código acima em ambiente Linux (Ubuntu 16.04 LTS). Copie o trecho de código acima. Compile-o usando a chave gcc nas entradas conforme especificado e admire o poder dos algoritmos de classificação!
- Resultados: Como você pode ver para tamanhos de entrada pequenos, a classificação por inserção é melhor que a classificação por mesclagem por 2 * 10 ^ -6 seg. Mas esta diferença de tempo não é tão significativa. Por outro lado, o algoritmo híbrido e a função da biblioteca qsort() têm desempenho tão bom quanto a classificação por inserção.
O tamanho da entrada agora aumentou aproximadamente 100 vezes de n = 30 para n = 1000. A diferença agora é tangível. A classificação por mesclagem é 10 vezes mais rápida que a classificação por inserção. Há novamente um empate entre o desempenho do algoritmo híbrido e a rotina qsort(). Isso sugere que qsort() é implementado de uma forma que é mais ou menos semelhante ao nosso algoritmo híbrido, ou seja, alternando entre diferentes algoritmos para tirar o melhor proveito deles.
Finalmente, o tamanho da entrada é aumentado para 10 ^ 5 (1 Lakh!), Que é provavelmente o tamanho ideal usado em cenários práticos. Em comparação com a entrada anterior n = 1000, onde a classificação por mesclagem superou a classificação por inserção executando 10 vezes mais rápido, aqui a diferença é ainda mais significativa. A classificação por mesclagem supera a classificação por inserção em 100 vezes! O algoritmo híbrido que escrevemos, na verdade, supera a classificação por mesclagem tradicional, executando 0,01 segundo mais rápido. E, por último, qsort() a função da biblioteca finalmente nos prova que a implementação também desempenha um papel crucial ao medir meticulosamente os tempos de execução, executando 3 milissegundos mais rápido! :D
Nota: Não execute o programa acima com n >= 10^6, pois isso exigirá muito poder de computação. Obrigado e boa codificação! :)
Criar questionário