insertion_sort_Rcpp: Insertion Sort Algorithm (C++ Implementation)

In vrunge/M2algorithmique: Example of an Rcpp package for M2 Data Science students

Insertion Sort Algorithm (C++ Implementation)

Description

This function implements the Insertion Sort algorithm in C++ and is exported to R using Rcpp. Insertion Sort is a simple sorting algorithm that builds the sorted sequence one element at a time by inserting each new element into its correct position within the sorted part of the vector.

The algorithm works by iterating through the input vector and shifting larger elements to the right before inserting the current element (key) into its proper position.

Usage

insertion_sort_Rcpp(v)

Arguments

v	A numeric vector containing unsorted elements.

Details

• Time Complexity: O(n²) in the worst and average cases, O(n) in the best case (already sorted data).

• Space Complexity: O(1) (in-place sorting, no additional memory used).

• Stable Sorting Algorithm: Maintains the relative order of equal elements.

Value

A numeric vector of the same length as 'v', sorted in ascending order.

Examples

insertion_sort_Rcpp(rnorm(100))
insertion_sort_Rcpp(sample(100))

vrunge/M2algorithmique documentation built on April 5, 2025, 4:06 a.m.