File SequenceAlgorithms.h

↰ Parent directory (ADS/sequence)

Algorithms on a SEQUENCE [see File ADT.h], beyond the book, through its positions only, so that they work on a List and on an ArraySequence:

Definition (ADS/sequence/SequenceAlgorithms.h)

Detailed Description

  • search(), the place of an item counted from 0, or -( n + 1 ) after n comparisons, and searchOrdered() on a sorted sequence, which stops at the first larger item and gives -( comparisons ) when it misses;

  • lowerBound(), the position of the first item not smaller than v in a sorted sequence, i.e., where v goes to keep it sorted, and whether v is there, so that a search and an insertion share the same scan;

  • sublist(), the items from a position to another one, the empty sequence being a sublist of every sequence;

  • order(), which tells whether a sequence is empty, constant, strictly or weakly increasing or decreasing, or none of them;

  • bubbleSort(), :math:` O( n^2 ) ` swaps of adjacent items by read() and write();

  • naturalMergeSort(), the natural merge sort: the maximal sorted runs are distributed alternately to two sequences and merged in pairs back, until a single run is left, in :math:` O( n log r ) ` time for r runs and O( n ) on a sorted sequence;

  • mergeSorted(), the merge of two sorted sequences that keeps the repeated items, and removeDuplicates(), which keeps the first copy of each item in :math:` O( n^2 ) `.

The contracts [see File Contract.h]: searchOrdered() and mergeSorted() need sorted sequences, and the sorts, the merge and removeDuplicates() ensure a sorted result, or one without repetitions, of the right length; all of them cost O( n ) or more, and are audits, whose comparisons a comparator that counts its calls can skip [see checkingContract()]. The algorithms are defined in SequenceAlgorithms.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, sections 3.2.1 and 12.2, https://algoritmicamente.it/materiali/libro/capitoli/cap12.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Enums

Functions