Stack is one of the basic data structure which Implements ordering principle LIFO or last-in first-out. In real life we can meet this principle in magazines:
Monthly Archives: October 2014
Knuth–Morris–Pratt algorithm
Very effective string searching algorithm (also known as KMP) with O (m+n) complexity, where m is length of pattern and n is length of text. Unlike the brute-force algorithm we can skip some of the comparisons in the case when a mismatch occurs. The algorithm was discovered by these gentelmens:
in 1974.
Quicksort
Quicksort is one of the fastest known algorithms for sorting arrays (in average it requires O (n log n) exchanges to order n elements). The algorithm was developed by Tony Hoare in 1960 during his work at Moscow State University. As it counterpart merge sort, it uses divide and conquer paradigm.
Merge sort
The maxim “Divide et impera” or divide and conquer took root in the Greek kingdom of Macedon. In times of Philip II of Macedon (359–336 BC) who was the father of Alexander the Great.
It seems that initially this rule was used in politics, warfare and in tactical maneuvers. But nowadays, we can also meet this principle in economics, computer science, usually we can solve a complex problem using divide and conquer technique. The main idea behind this is to take something big and divide it into small pieces, farther, we can easy work with small piece.
Insertion sort
Imagine you have a bookshelf with books and you are going to arrange these books in alphabetical order. If amount of books is not big then insertion sort is one of the possible way to sort them.
