Lists, arrays and trees

Searching

• Dictionary search. See predictive search.
• Selection algorithm. Finds the kth largest item in a list.
• Binary search algorithm. Locates an item in a sorted list.
• Breadth-first search. Traverses a graph level by level.
• Depth-first search. Traverses a graph branch by branch.
• Disjoint-set data structure and algorithm. With for application, building a maze.
• Best-first search. Traverses a graph in the order of likely importance using a priority queue.
• A* tree search. Special case of best-first search that uses heuristics to improve speed.
• Uniform-cost search. A tree search that finds the lowest cost route where costs vary.
• Predictive search. Binary like search which factors in magnitude of search term versus the high and low values in the search.
• Hash table. Associate keys to items in an unsorted collection, to retrieve them in a linear time.
• Interpolated search. See predictive search.
• Skip list. Structure composed of linked lists for a quicker access, and algorithm or search/insertion.

Sorting

• Binary tree sort. Sort of a binary tree, incremental, similar to insertion sort.
• Bogosort. Inefficient random sort of a desk card.
• Bubble sort. For each pair of indices, swap the items if out of order.
• Bucket sort. Split a list in buckets and sort them individually. Generalizes pigeonhole sort.
• Cocktail sort (or bidirectional bubble, shaker, ripple, shuttle, happy hour sort). Variation of bubble sort that sorts in both directions each pass through the list.
• Comb sort. Efficient variation of bubble sort that eliminates "turtles", the small values near the end of the list and makes use of gaps bewteen values.
• Counting sort. It uses the range of numbers in the list A to create an array B of this length. Indexes in B are used to count how many elements in A have a value less than i.
• Gnome sort. Similar to insertion sort except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort.
• Heapsort. Convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list.
• Insertion sort. Determine where the current item belongs in the list of sorted ones, and insert it there.
• Introsort. Or introspective sort. It begins in quicksort and switches to heapsort at certain recursion level.
• Merge sort. Sort the first and second half of the list separately, then merge the sorted lists.
• Pancake sort. Reverse elements of some prefix of a sequence.
• Pigeonhole sort. Fill an empty array with all elements of an array to be sorted, in order.
• Postman sort. Hierarchical variant of bucket sort, used by post offices.
• Quicksort. Divide list into two, with all items on the first list coming before all items on the second list.; then sort the two lists. Often the method of choice.
• Radix sort. Sorts keys associated to items, or integer by processing digits.
• Selection sort. Pick the smallest of the remaining elements, add it to the end of the sorted list.
• Shell sort. Improves insertion sort with use of gaps between values.
• Smoothsort. See heapsort.
• Stochastic sort. See bogosort.

Merging

• Simple Merge. Merge n sorted streams into one output stream. All the stream heads are compared, and the head with the least key is removed and written to the output.
• k-way Merge sort (or p-way. A merge sort that sorts a data stream using repeated merges.

Logic programming

• Davis–Putnam algorithm. Checks the validity of a first-order formula.

Posted in: Algorithm