Algorithms – Fastest Algorithm for Dividing Array into Positive and Negative Numbers

algorithmsarraysorting

Given array of integers I am trying to design the fastest algorithm that swaps the elements such that at the end : all negative elements are on the left and then the positive elements, for example, final output might me [-5,-1,-3,10,11,2], Of course, direct sorting with n*lgn gives the desired answer but I am looking for faster algorithm if possible, any suggestions?

Best Answer

That task is simple:

Iterate from start and end at the same time, and swap the element if needed.

A = index_first
B = index_last
while A < B
    while A < B and v[A] < 0
        A++
    while A < B and not v[B] < 0
        B--
    if A < B
        swap(v[A], v[B])

You get N comparisons (once for each element) and at most N/2 swaps (if the elements were all at the wrong end, and half should be at the front/end), which is the bare minimum.

Related Solutions

C++ Algorithms – Fastest String Search Algorithm

It depends on the kind of search you want to perform. Each of the algorithms performs particularly well for certain types of a search, but you have not stated the context of your searches.

Here are some typical thoughts on search types:

Boyer-Moore: works by pre-analyzing the pattern and comparing from right-to-left. If a mismatch occurs, the initial analysis is used to determine how far the pattern can be shifted w.r.t. the text being searched. This works particularly well for long search patterns. In particular, it can be sub-linear, as you do not need to read every single character of your text.
Knuth-Morris-Pratt: also pre-analyzes the pattern, but tries to re-use whatever was already matched in the initial part of the pattern to avoid having to rematch that. This can work quite well, if your alphabet is small (f.ex. DNA bases), as you get a higher chance that your search patterns contain reuseable subpatterns.
Aho-Corasick: Needs a lot of preprocessing, but does so for a number of patterns. If you know you will be looking for the same search patterns over and over again, then this is much better than the other, because you need to analyse patterns only once, not once per search.

Hence, as usual in CS, there is no definite answer to the overall best. It is rather a matter of choosing the right tool for the job at hand.

Another note on your worst-case reasoning: Do consider the kinds of searches required to create that worst-case and think thoroughly about whether these are really relevant in your case. For example, the O(mn) worst-case complexity of the Boyer-Moore algorithm stems from a search pattern and a text that each use only one character (like finding aaa in aaaaaaaaaaaaaaaaaaaaa) - do you really need to be fast for searches like that?

Algorithms – How to Sort an Array of Numbers with Decimals

Your problem is that your "numbers" don't have decimal places. You have a string which consists of two integers which are separated by .. Parse them as two integers and write a custom comparer. The sorting algorithm can remain the same, you just need to pass in the comparer.

In C# such a comparer could look similar to this:

void Test()
{
    var data=new string[]{ "1.34", "1.15", "1.1", "1.2", "1.26", "1.10", "1.20", "1.17" };
    Array.Sort(data, VersionComparer);
    data.Dump();
}

static int VersionComparer(string s1, string s2)
{
    List<int> parts1 = s1.Split('.').Select(int.Parse).ToList();
    List<int> parts2 = s2.Split('.').Select(int.Parse).ToList();

    while(parts1.Count < parts2.Count)
        parts1.Add(0);
    while(parts2.Count < parts1.Count)
        parts2.Add(0);

    for(int i = 0; i < parts1.Count; i++)
    {
         if(parts1[i] < parts2[i])
             return -1;
         if(parts1[i] > parts2[i])
             return +1;
    }
    return 0;
}

Best Answer

Related Solutions

C++ Algorithms – Fastest String Search Algorithm

Algorithms – How to Sort an Array of Numbers with Decimals

Related Topic