Search

This paper presents some commonly used algorithms and data structures using the Lisp language, functional programming style, and recursive thinking. Insertion sort, selection sort, quick sort, binary search tree, search, insertion, and deletion operations are presented. The algorithms are written in purely functional and recursive style using Lisp. Only a small subset of Lisp is used to write the algorithms. Various factors related to learning, teaching, and the curriculum are pointed out.

Sorting is one of the most common and important computing operations. In analyzing and comparing sorting algorithms, we consider their execution times, as indicated by the number of operations they execute as they sort n elements. The simplest algorithms have times that grow approximately as n 2 , while more complex algorithms offer times that grow approximately as n log n . This paper pursues a contrary goal: a sorting algorithm whose time grows more quickly than that of the well-known algorithms. The paper exhibits and analyzes such an algorithm.