Skip to content

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 ​

AssinaturaRetornoComplexidade
bubbleSort(values: i32[])i32[]O(n²) no pior caso e no caso médio, O(n) no melhor caso
tyrus
import { bubbleSort } from "tyrus:algorithm";
const sorted: i32[] = bubbleSort([2, 4, 1, 3]);
print(sorted); // [1, 2, 3, 4]

Resultado de estudo ​

ExportTipoFinalidade
bubbleSortInfo(values: i32[])FunçãoRetorna um BubbleSortInfo sem alterar values
BubbleSortInfoInterface de dadosMantém os snapshots e todas as métricas do Bubble Sort
tyrus
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.

tyrus
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); // 3

Definições das métricas ​

  • comparisonCount incrementa uma vez para cada par adjacente avaliado pelo laço interno.
  • swapCount incrementa uma vez quando uma comparação adjacente troca dois valores.
  • passCount incrementa 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[].