heap_sort_Rcpp: Heap Sort Algorithm (C++ Implementation)

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

Heap Sort Algorithm (C++ Implementation)

Description

This function implements Heap Sort, an efficient sorting algorithm that first builds a max-heap and then repeatedly extracts the maximum element to produce a sorted sequence.

The algorithm consists of two main steps:

1. Heap Construction: The input vector is reorganized into a max-heap.

2. Sorting: The largest element (root) is swapped with the last element, reducing the heap size and reapplying heapify.

Usage

heap_sort_Rcpp(v)

Arguments

v	A numeric vector containing unsorted elements.

Details

• Time Complexity:

  • Building the heap: O(n)

  • Extracting elements: O(n log n)

  • Overall: O(n log n)

• Space Complexity: O(1) (in-place sorting).

• Unstable Sort: The relative order of equal elements may change.

Value

A numeric vector sorted in ascending order.

Examples

heap_sort_Rcpp(rnorm(100))
heap_sort_Rcpp(sample(100))

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