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.
@Author: M.Lakshmikar Reddy
No comments:
Post a Comment