Heapsort is one of the general sorting algorithms that performs in O(n.log(n)) in the worst-case, just like merge sort and quicksort, but sorts in place – as quicksort. Although quicksort’s worst-case sorting time is O(n2) it’s often considered that it beats other sorting algorithms in practice. Thus in practice quicksort is “faster” than heapsort. In the same time developers tend to consider heapsort as more difficult to implement than other n.log(n) sorting algorithms.
In the other hand heapsort uses a special data structure, called heap, in order to sort items in place and this data structure is quite useful in some specific cases. Thus to understand heapsort we first need to understand what is a heap.
So first let’s take a look at what is a heap.
A heap is a complete binary tree, where all the parents are greater than their children (max heap). If all the children are greater than their parents it is considered to call the heap a min-heap. But first what is a complete binary tree? Well, this is a binary tree, where all the levels are full, except the last one, where all the items are placed on the left (just like on the image below).
The binary search tree is a very useful data structure, where searching can be significantly faster than searching into a linked list. However in some cases searching into a binary tree can be as slow as searching into a linked list and this mainly depends on the input sequence. Indeed in case the input is sorted the binary tree will seem much like a linked list and the search will be slow.
To overcome this we must change a bit the data structure in order to stay well balanced. It’s intuitively clear that the searching process will be better if the tree is well branched. This is when finding an item will become faster with minimal effort.
Since we know how to construct a binary search tree the only thing left is to keep it balanced. Obviously we will need to re-balance the tree on each insert and delete, which will make this data structure more difficult to maintain compared to non-balanced search trees, but searching into it will be significantly faster. Continue reading Computer Algorithms: Balancing a Binary Search Tree→
Although you can do this in PHP, that is completely wrong. The code becomes more difficult to read and understand. In the second place you can miss a $ sign in front of a variable declaration and thus the PHP interpreter will assume this is a string. So disable error reporting isn’t so great sometimes.
Have you ever asked yourself which is the algorithm used to find a word after clicking Ctrl+F and typing something? Well I guess you know the answer from the title, but in this article you’ll find out how exactly this is done.
In the other hand the Morris-Pratt algorithm is a very good improvement of the brute force string searching, but the question remains. Is there any algorithm that is faster than Morris-Pratt – is there any way to skip more comparisons and to move the pattern faster.
It’s clear that if we have to find whether a single character is contained into a text we need at least “n” steps, where n is the length of the text. Once we have to find whether a pattern with the length of “m” is contained into a text with length of “n” the case is getting a little more complex.
However the answer is that there is such algorithm that is faster and more suitable than Morris-Pratt. This is the Boyer-Moore string searching.
Boyer-Moore is an algorithm that improves the performance of pattern searching into a text by considering some observations. It is defined in 1977 by Robert S. Boyer and J Strother Moore and it consist of some specific features.
First of all this algorithm starts comparing the pattern from the leftmost part of text and moves it to the right, as on the picture below.
String matching is something crucial for database development and text processing software. Fortunately every modern programming language and library is full of functions for string processing that help us in our everyday work. However is great to understand their principles.
String algorithms can be mainly divided into several categories. One of these categories is string matching.
When we come to string matching the most basic approach is what is known as brute force, which means just to check every single character from the text to match against the pattern. In general we have a text and a pattern (most commonly shorter than the text). What we need to do is to answer the question whether this pattern appears into the text.
The principles of brute force string matching are quite simple. We must check for a match between the first characters of the pattern with the first character of the text as on the picture bellow.