Bubble sort
O módulo oferece duas funções importadas. bubbleSort(values) retorna uma cópia crescente para uso direto, enquanto bubbleSortInfo(values) retorna snapshots independentes da entrada e da saída e contadores semânticos para estudar o algoritmo. Nenhuma função altera o array de entrada.
Execução direta
| Assinatura | Retorno | Complexidade |
|---|---|---|
bubbleSort(values: i32[]) | i32[] | O(n²) no pior caso e no caso médio, O(n) no melhor caso |
import { bubbleSort } from "tyrus:algorithm";
const sorted: i32[] = bubbleSort([2, 4, 1, 3]);
print(sorted); // [1, 2, 3, 4]Resultado de estudo
| Export | Tipo | Finalidade |
|---|---|---|
bubbleSortInfo(values: i32[]) | Função | Retorna um BubbleSortInfo sem alterar values |
BubbleSortInfo | Interface de dados | Mantém os snapshots e todas as métricas do Bubble Sort |
interface BubbleSortInfo {
originalValues: i32[];
sortedValues: i32[];
comparisonCount: usize;
swapCount: usize;
passCount: usize;
}BubbleSortInfo expõe originalValues: i32[], sortedValues: i32[], comparisonCount: usize, swapCount: usize e passCount: usize. Os arrays são snapshots independentes da entrada e da saída ordenada.
import { BubbleSortInfo, bubbleSortInfo } from "tyrus:algorithm";
const input: i32[] = [4, 1, 3, 2];
const info: BubbleSortInfo = bubbleSortInfo(input);
print(input); // [4, 1, 3, 2]
print(info.originalValues); // [4, 1, 3, 2]
print(info.sortedValues); // [1, 2, 3, 4]
print(info.comparisonCount); // 6
print(info.swapCount); // 4
print(info.passCount); // 3Definições das métricas
comparisonCountincrementa uma vez para cada par adjacente avaliado pelo laço interno.swapCountincrementa uma vez quando uma comparação adjacente troca dois valores.passCountincrementa após cada percurso concluído pelo prefixo ainda não ordenado, incluindo o percurso final que não faz troca e encerra antecipadamente.- Entradas vazias ou com um elemento executam zero comparações, trocas e passagens.
O Bubble Sort é estável porque valores iguais nunca são trocados. A variante instrumentada tem o mesmo tempo O(n²) no pior caso e O(n) no melhor caso da função direta, além de O(n) de armazenamento no resultado para os snapshots original e ordenado. Características estáticas como estabilidade e complexidade permanecem nesta documentação em vez de serem repetidas em cada resultado. A API atual aceita intencionalmente apenas i32[].
