edit-article
Home
Up
Delete
Article Name:
Article Description:
] LIST - algorithms, SCR=wikipedia,
Chapter ID/Name:
Status:
Write
Writing
Written
Add Photo:
Owner ID:
Content:
use HTML
Edit Content
<h1 style="text-align: center;">LIST - algorithms</h1> <h2>[WHAT]</h2> <ol> <li>] by Don Sagrott, founder @ sospep.com - a listing of various algorithms, with type ( search, sorting, graph, ...) and a brief description </li> </ol> <h2>[WHY]</h2> <ol> <li>] </li> </ol> <h2>[WHERE]</h2> <ol> <li><strong>] READ THE FULL ARTICLE</strong></li> <ol> <li>] </li> </ol></ol> <h2>[WHEN]</h2> <ol> <li>] 2017-01-27 EDIT moved from contents book</li> </ol> <h2>[EXAMPLE]</h2> <ol> <li><strong>[sequence search]</strong></li> <li><a title="Linear search" href="http://en.wikipedia.org/wiki/Linear_search" target="_blank">Linear search</a>: finds an item in an unsorted sequence</li> <li><a title="Selection algorithm" href="http://en.wikipedia.org/wiki/Selection_algorithm" target="_blank">Selection algorithm</a>: finds the <em>k</em>th largest item in a sequence</li> <li><a title="Ternary search" href="http://en.wikipedia.org/wiki/Ternary_search" target="_blank">Ternary search</a>: a technique for finding the minimum or maximum of a function that is either strictly increasing and then strictly decreasing or vice versa</li> <li><a title="Sorted list" href="http://en.wikipedia.org/wiki/Sorted_list" target="_blank">Sorted lists</a></li> <ol> <li><a title="Binary search algorithm" href="http://en.wikipedia.org/wiki/Binary_search_algorithm" target="_blank">Binary search algorithm</a>: locates an item in a sorted sequence</li> <li><a title="Fibonacci search technique" href="http://en.wikipedia.org/wiki/Fibonacci_search_technique" target="_blank">Fibonacci search technique</a>: search a sorted sequence using a divide and conquer algorithm that narrows down possible locations with the aid of <a class="mw-redirect" title="Fibonacci numbers" href="http://en.wikipedia.org/wiki/Fibonacci_numbers">Fibonacci numbers</a></li> <li><a title="Jump search" href="http://en.wikipedia.org/wiki/Jump_search" target="_blank">Jump search</a> (or block search): linear search on a smaller subset of the sequence</li> <li><a title="Interpolation search" href="http://en.wikipedia.org/wiki/Interpolation_search" target="_blank">Predictive search</a>: binary-like search which factors in <a title="Magnitude (mathematics)" href="http://en.wikipedia.org/wiki/Magnitude_(mathematics)">magnitude</a> of search term versus the high and low values in the search. Sometimes called dictionary search or interpolated search.</li> <li><a title="Uniform binary search" href="http://en.wikipedia.org/wiki/Uniform_binary_search" target="_blank">Uniform binary search</a>: an optimization of the classic binary search algorithm</li> </ol> <li><strong>[sorting] Exchange Sorts</strong></li> <ol> <li><a title="Bubble sort" href="http://en.wikipedia.org/wiki/Bubble_sort" target="_blank">Bubble sort</a>: for each pair of indices, swap the items if out of order</li> <li><a title="Cocktail sort" href="http://en.wikipedia.org/wiki/Cocktail_sort" target="_blank">Cocktail sort</a></li> <li><a title="Comb sort" href="http://en.wikipedia.org/wiki/Comb_sort" target="_blank">Comb sort</a></li> <li><a title="Gnome sort" href="http://en.wikipedia.org/wiki/Gnome_sort" target="_blank">Gnome sort</a></li> <li><a title="Odd-even sort" href="http://en.wikipedia.org/wiki/Odd-even_sort" target="_blank">Odd-even sort</a></li> <li><a title="Quicksort" href="http://en.wikipedia.org/wiki/Quicksort" target="_blank">Quicksort</a>: 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</li> </ol> <li><strong>Humorous or ineffective</strong></li> <ol> <li><a title="Bogosort" href="http://en.wikipedia.org/wiki/Bogosort" target="_blank">Bogosort</a></li> <li><a title="Stooge sort" href="http://en.wikipedia.org/wiki/Stooge_sort" target="_blank">Stooge sort</a></li> </ol> <li><strong>Hybrid</strong></li> <ol> <li><a title="Flashsort" href="http://en.wikipedia.org/wiki/Flashsort" target="_blank">Flashsort</a></li> <li><a title="Introsort" href="http://en.wikipedia.org/wiki/Introsort" target="_blank">Introsort</a>: begin with quicksort and switch to heapsort when the recursion depth exceeds a certain level</li> <li><a title="Timsort" href="http://en.wikipedia.org/wiki/Timsort" target="_blank">Timsort</a>: adaptative algorithm derived from merge sort and insertion sort. Used in Python 2.3 and up, and Java SE 7.</li> </ol> <li><strong>Insertion sorts</strong></li> <ol> <li><a title="Insertion sort" href="http://en.wikipedia.org/wiki/Insertion_sort" target="_blank">Insertion sort</a>: determine where the current item belongs in the list of sorted ones, and insert it there</li> <li><a title="Library sort" href="http://en.wikipedia.org/wiki/Library_sort" target="_blank">Library sort</a></li> <li><a title="Patience sorting" href="http://en.wikipedia.org/wiki/Patience_sorting" target="_blank">Patience sorting</a></li> <li><a title="Shell sort" href="http://en.wikipedia.org/wiki/Shell_sort" target="_blank">Shell sort</a>: an attempt to improve insertion sort</li> <li><a title="Tree sort" href="http://en.wikipedia.org/wiki/Tree_sort" target="_blank">Tree sort</a> (binary tree sort): build binary tree, then traverse it to create sorted list</li> <li><a title="Cycle sort" href="http://en.wikipedia.org/wiki/Cycle_sort" target="_blank">Cycle sort</a>: in-place with theoretically optimal number of writes</li> </ol> <li><strong>Merge sorts</strong></li> <ol> <li><a title="Merge sort" href="http://en.wikipedia.org/wiki/Merge_sort" target="_blank">Merge sort</a>: sort the first and second half of the list separately, then merge the sorted lists</li> <li><a title="Strand sort" href="http://en.wikipedia.org/wiki/Strand_sort" target="_blank">Strand sort</a></li> </ol> <li><strong>Non-comparison sorts</strong></li> <ol> <li><a title="Bead sort" href="http://en.wikipedia.org/wiki/Bead_sort" target="_blank">Bead sort</a></li> <li><a title="Bucket sort" href="http://en.wikipedia.org/wiki/Bucket_sort" target="_blank">Bucket sort</a></li> <li><a title="Burstsort" href="http://en.wikipedia.org/wiki/Burstsort" target="_blank">Burstsort</a>: build a compact, cache efficient <a class="new" title="Burst trie (page does not exist)" href="http://en.wikipedia.org/w/index.php?title=Burst_trie&action=edit&redlink=1">burst trie</a> and then traverse it to create sorted output</li> <li><a title="Counting sort" href="http://en.wikipedia.org/wiki/Counting_sort" target="_blank">Counting sort</a></li> <li><a title="Pigeonhole sort" href="http://en.wikipedia.org/wiki/Pigeonhole_sort" target="_blank">Pigeonhole sort</a></li> <li><a title="Postman sort" href="http://en.wikipedia.org/wiki/Postman_sort" target="_blank">Postman sort</a>: variant of Bucket sort which takes advantage of hierarchical structure</li> <li><a title="Radix sort" href="http://en.wikipedia.org/wiki/Radix_sort" target="_blank">Radix sort</a>: sorts strings letter by letter</li> </ol> <li><strong>Selection sorts</strong></li> <ol> <li><a title="Heapsort" href="http://en.wikipedia.org/wiki/Heapsort" target="_blank">Heapsort</a>: convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list</li> <li><a title="Selection sort" href="http://en.wikipedia.org/wiki/Selection_sort" target="_blank">Selection sort</a>: pick the smallest of the remaining elements, add it to the end of the sorted list</li> <li><a title="Smoothsort" href="http://en.wikipedia.org/wiki/Smoothsort" target="_blank">Smoothsort</a> </li> </ol> <li><strong>Other</strong></li> <ol> <li><a title="Bitonic sorter" href="http://en.wikipedia.org/wiki/Bitonic_sorter" target="_blank">Bitonic sorter</a> </li> <li><a title="Pancake sorting" href="http://en.wikipedia.org/wiki/Pancake_sorting" target="_blank">Pancake sorting</a> </li> <li><a title="Topological sorting" href="http://en.wikipedia.org/wiki/Topological_sorting" target="_blank">Topological sort</a> </li> </ol> <li><strong>Unknown class</strong></li> <ol> <li><a title="Samplesort" href="http://en.wikipedia.org/wiki/Samplesort" target="_blank">Samplesort</a></li> </ol> <li> <div><strong>[ Graph Algorithms ]</strong></div> </li> <ol> <li> <div><a class="mw-redirect" title="Coloring algorithm" href="http://en.wikipedia.org/wiki/Coloring_algorithm">Coloring algorithm</a>: Graph coloring algorithm.</div> </li> <li> <div><a title="Hopcroft–Karp algorithm" href="http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm" target="_blank">Hopcroft–Karp algorithm</a>: convert a bipartite graph to a <a class="mw-redirect" title="Maximum cardinality matching" href="http://en.wikipedia.org/wiki/Maximum_cardinality_matching">maximum cardinality matching</a> </div> </li> <li> <div><a title="Hungarian algorithm" href="http://en.wikipedia.org/wiki/Hungarian_algorithm" target="_blank">Hungarian algorithm</a>: algorithm for finding a <a class="mw-redirect" title="Perfect matching" href="http://en.wikipedia.org/wiki/Perfect_matching">perfect matching</a> </div> </li> <li> <div><a title="Prüfer sequence" href="http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence" target="_blank">Prüfer coding</a>: conversion between a labeled tree and its <a title="Prüfer sequence" href="http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence">Prüfer sequence</a> </div> </li> <li> <div><a title="Tarjan's off-line least common ancestors algorithm" href="http://en.wikipedia.org/wiki/Tarjan%27s_off-line_least_common_ancestors_algorithm" target="_blank">Tarjan's off-line least common ancestors algorithm</a>: compute <a title="Lowest common ancestor" href="http://en.wikipedia.org/wiki/Lowest_common_ancestor">lowest common ancestors</a> for pairs of nodes in a tree</div> </li> <li> <div><a title="Topological sorting" href="http://en.wikipedia.org/wiki/Topological_sorting" target="_blank">Topological sort</a>: finds linear order of nodes (e.g. jobs) based on their dependencies</div> </li> </ol></ol> <h2>[HOW-TO]</h2> <ol> <li>]</li> </ol> <h2>[REFERENCE]</h2> <ol style="font-size: 10px; font-weight: normal; text-align: start;"> <li>] LIST - algorithms - <a href="http://en.wikipedia.org/wiki/List_of_algorithms">http://en.wikipedia.org/wiki/List_of_algorithms</a> </li> </ol> <h1 style="text-align: center;"> </h1>