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?
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.
This can be done in linear time.
- Allocate an array of the same size. Store the index for the first unfilled element and the last unfilled element.
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.