Tag Archives: Recursion

Computer Algorithms: Quicksort

algorithms, , , , , , , , , , , , , , , , ,

Introduction

When it comes to sorting items by comparing them merge sort is one very natural approach. It is natural, because simply divides the list into two equal sub-lists then sort these two partitions applying the same rule. That is a typical divide and conquer algorithm and it just follows the intuitive approach of speeding up the sorting process by reducing the number of comparisons. However there are other “divide and conquer” sorting algorithms that do not follow the merge sort scheme, while they have practically the same success. Such an algorithm is quicksort.

Overview

Back in 1960 C. A. R. Hoare comes with a brilliant sorting algorithm. In general quicksort consists of some very simple steps. First we’ve to choose an element from the list (called a pivot) then we must put all the elements with value less than the pivot on the left side of the pivot and all the items with value greater than the pivot on its right side. After that we must repeat these steps for the left and the right sub-lists. That is quicksort! Simple and elegant!

Quicksort
Continue reading Computer Algorithms: Quicksort →

Computer Algorithms: Binary Search

algorithms, PHP, , , , , , , , , , , , , , , , , , , , ,

Overview

The binary search is perhaps the most famous and best suitable search algorithm for sorted arrays. Indeed when the array is sorted it is useless to check every single item against the desired value. Of course a better approach is to jump straight to the middle item of the array and if the item’s value is greater than the desired one, we can jump back again to the middle of the interval. Thus the new interval is half the size of the initial one.

Binary search basic implementation
Basic implementation of binary search

If the searched value is greater than the one placed at the middle of the sorted array, we can jump forward. Again on each step the considered list is getting half as long as the list on the previous step, as shown on the image bellow.

Binary search - basic implementation
Binary search - basic implementation

Implementation

Here’s a sample implementation of this algorithm on PHP. Obviously the nature of this approach is guiding us to a recursive implementation, but as we know, sometimes recursion can be dangerous. That’s why here we can see either the recursive and iterative solution. Continue reading Computer Algorithms: Binary Search →