2

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?

8

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.

  • +1, but note that if “positive” actually means “non-negative”, the inner loop should test v[B] >= 0 – otherwise we'd get an infinite loop if the input contains two zeroes. – amon May 12 '17 at 11:53
  • +1 Instead of while true and a conditional break you could write while A < B and do the swapping conditionally. – COME FROM May 12 '17 at 12:07
  • 2
    maybe add some explanation and show why its the fastest possible – Ewan May 12 '17 at 13:05
  • @Ewan added some when you asked. – Deduplicator May 12 '17 at 19:40
3

This can be done in linear time.

  1. Allocate an array of the same size. Store the index for the first unfilled element and the last unfilled element.
  2. Iterate through the input. For each item:

    • if it is negative, add it to the output array at the first unfilled element, and increment that index.
    • if it is positive, add it to the output array at the last unfilled element, and decrement that index.

This can also be done in-place, but doing so correctly is slightly more difficult. We then have a left pointer and a right pointer. We move the left pointer forwards while it points to negative numbers, and the right pointer backwards while it points to positive numbers. If the pointers have passed each other, the algorithm is finished. Otherwise, we swap the items under the pointers, and continue.

If your algorithm is very performance critical to the point that you want to make optimal use of caching effects, it may not be best to fill the positive numbers backwards. In that case, it may be better to write the positive numbers to a small cache-friendly buffer first, and copy the buffer to the end of the output array when it is full.

1

You use the quicksort algorithm, but only the very first pass with a pivot of 0. If you don't know how the quicksort algorithm works, take this as an opportunity to look it up.

  • But what if we don't have 0 in the array? – user271261 May 12 '17 at 12:30
  • @user271261 We can still use 0 as pivot even if the element is not in the array. – Amit Jul 13 '18 at 14:31
0

You can try using something like that: iterate over the whole array, a build an list with in the head the negative numbers, and in the back the positives. so you can get a complexity of N+list-toarrayconversion

  • Yeah clearly it is O(n) but we use a new array with n memory, is it possible to do it with O(n) but don't use additional memory? – user271261 May 12 '17 at 11:37
0

all negative elements are on the left and then the positive elements

If that's all you need then Bucket sort is what you want. You basically create two buckets, one for array[i] < 0 and one for array[i] >= 0.

That would be the fastest without swapping elements in the array. Another advantage is you can get fastest execution too because without manipulating the same array you can distribute the work to different CPUs

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.