Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to rearrange an array in such a way that each element is greater/smaller than its neighbours

For example, if the numbers are:

30, 12, 49, 6, 10, 50, 13

The array will be:

[10, 6, 30, 12, 49, 13, 50]

As you can see:

  • 6 is smaller than both 10 and 30 and
  • 49 is greater than 12 and 13 and so on.

The numbers are all different and real. I need the most efficient algorithm.

like image 682
Peggy Avatar asked May 25 '13 09:05

Peggy


People also ask

How do you order an array from smallest to largest?

The sort() method allows you to sort elements of an array in place. Besides returning the sorted array, the sort() method changes the positions of the elements in the original array. By default, the sort() method sorts the array elements in ascending order with the smallest value first and largest value last.

How do you rearrange elements in an array?

Approach(Naive Approach): Navigate the numbers from 0 to n-1. Now navigate through array. If (i==a[j]) , then replace the element at i position with a[j] position. If there is any element in which -1 is used instead of the number then it will be replaced automatically.

How do you rearrange an array with alternate high and low elements?

The idea is to start from the second array element and increment the index by 2 for each loop's iteration. If the last element is greater than the current element, swap the elements. Similarly, if the next element is greater than the current element, swap both elements.

How do you find the number of elements greater smaller than an element in an array?

The simplest trick is sort the array first and count the number of elements in the array. So for example if you have 10 elements then your first element is less than 9 and likewise the second element is smaller than 8 and so on.


1 Answers

This can be done in O(n):

  1. Find median in O(n) (description is available in Wikipedia
  2. Put every element larger than the median on odd places and every smaller element - on even places

Of course, this assumes that all elements are distinct, otherwise sometimes it will fail.

like image 155
maxim1000 Avatar answered Oct 13 '22 09:10

maxim1000