Saturday, 18 June 2011

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.

0 comments:

Post a comment