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.
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.
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
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