Tag Archives: PHP

Computer Algorithms: Radix Sort

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

Introduction

Algorithms always depend on the input. We saw that general purpose sorting algorithms as insertion sort, bubble sort and quicksort can be very efficient in some cases and inefficient in other. Indeed insertion and bubble sort are considered slow, with best-case complexity of O(n2), but they are quite effective when the input is fairly sorted. Thus when you have a sorted array and you add some “new” values to the array you can sort it quite effectively with insertion sort. On the other hand quicksort is considered one of the best general purpose sorting algorithms, but while it’s a great algorithm when the data is randomized it’s practically as slow as bubble sort when the input is almost or fully sorted.

Now we see that depending on the input algorithms may be effective or not. For almost sorted input insertion sort may be preferred instead of quicksort, which in general is a faster algorithm.

Just because the input is so important for an algorithm efficiency we may ask are there any sorting algorithms that are faster than O(n.log(n)), which is the average-case complexity for merge sort and quicksort. And the answer is yes there are faster, linear complexity algorithms, that can sort data faster than quicksort, merge sort and heapsort. But there are some constraints!

Everything sounds great but the thing is that we can’t sort any particular data with linear complexity, so the question is what rules the input must follow in order to be sorted in linear time.

Such an algorithm that is capable of sorting data in linear O(n) time is radix sort and the domain of the input is restricted – it must consist only of integers.

Overview

Let’s say we have an array of integers which is not sorted. Just because it consists only of integers and because array keys are integers in programming languages we can implement radix sort.

First for each value of the input array we put the value of “1” on the key-th place of the temporary array as explained on the following diagram.

Radix sort first pass
Radix sort first pass
Continue reading Computer Algorithms: Radix Sort →

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: Merge Sort

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

Introduction

Basically sorting algorithms can be divided into two main groups. Such based on comparisons and such that are not. I already posted about some of the algorithms of the first group. Insertion sort, bubble sort and Shell sort are based on the comparison model. The problem with these three algorithms is that their complexity is O(n2) so they are very slow.

So is it possible to sort a list of items by comparing their items faster than O(n2)? The answer is yes and here’s how we can do it.

The nature of those three algorithms mentioned above is that we almost compared each two items from initial list.

Insertion sort and bubble sort make too many comparisons, exactly what merge sort tries to overcome!
Insertion sort and bubble sort make too many comparisons, exactly what merge sort tries to overcome!

This, of course, is not the best approach and we don’t need to do that. Instead we can try to divide the list into smaller lists and then sort them. After sorting the smaller lists, which is supposed to be easier than sorting the entire initial list, we can try to merge the result into one sorted list. This technique is typically known as “divide and conquer”.

Normally if a problem is too difficult to solve, we can try to break it apart into smaller sub-sets of this problem and try to solve them. Then somehow we can merge the results of the solved problems.

If it's too difficult to sort a large list of items, we can break it apart into smaller sub-lists and try to sort them!
If it's too difficult to sort a large list of items, we can break it apart into smaller sub-lists and try to sort them!

Continue reading Computer Algorithms: Merge Sort →

5 Tips on How to Spot a Bad Developer and Team Member

web development, , ,

1. He hates libraries, framworks and cutting edge technologies

He always hates newest technologies and considers that pure programming with no libraries and frameworks is the masterpiece of coding and only way to show his greatness. Any mention of a library name results in something like “blah, this sucks” with no explanation why. However most often the reason is “because it’s slow” with no examples of how slow actually this library is – he does not make any performance tests at all. Always prefers to write his own pure “javascript” or “php” based code/library because he thinks this is the cutting edge of modern technology.

2. He hates helping and talking to clients

Always after a phone call with a client he’s angry, because “the sutpid client” doesn’t understand his way of brilliant thinking. He thinks that a project must exists just to show what a “good” developer he is and how much he knows, not because the product will be someday, somehow used by poor clients.

3. He loves to see how others make mistakes

Bugs by other developers are always accepted with a smile with some words like “I told you”. He doesn’t think bugs will be comited if he were the developer. However bugs in his code are always accepted and explained as misconseption of the client!

4. Always negative at meetings

Whatever solution is proposed on a meeting he’s negative. But he doesn’t propose his own solution. Typically a bad team member is always trying to say “whatever solution you get I’m telling you that there are some pitfalls”.

5. He hates interviews

Because he thinks he’s the best programmer in the world, he hates going to interviews. His behaviour on interviews is always like “you know less than me and I don’t know why I’m here”. However once he gets the job he behaves with his boss like “I’m making you a favor to receive a salary from you!”

Advice: To avoid working with such jerks try to spot them on the interview. If he tells you that your choice of library and technology sucks you should better get another candidate.