3

Given an array which is having elements which are in increasing order till a max value and then numbers in decreasing order. 

Eg. int a[] = { 10, 12, 14, 16, 15, 13, 11}.

How can this array be sorted efficiently?

The array needs to be sorted in-place.

Толя
  • 2,839
  • 15
  • 23
user1225752
  • 77
  • 1
  • 8

3 Answers3

8

Find the maximum value and then reverse the array up to that value. Then apply a merge on the two subarrays - first one that contains the maximum value and than the remaining array. This will have linear computational complexity and will require linear additional memory.

In your case:

a[] = { 10, 12, 14, 16, 15, 13, 11} => {10,12,14,16}, {15,13,11}

=> reverse(linear, in-place) =>

{16,14,12,10}, {15,13,11}

=> merge(linear, additional linear memory) =>

{16,15,14,13,12,11,10}

EDIT: For how to merge two arrays in place with no additional memory have a look at this answer

Community
  • 1
  • 1
Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
  • I gave a similar approach to do the sort. But I was asked to do in place. Can you please tell me how can we sort this array in-place. – user1225752 Jan 23 '13 at 13:47
  • i=4, { 10, 11, 12, 14, 15, 13, 16} this is right? Why swapped 14 instead of 13? – Толя Jan 23 '13 at 14:28
  • @Толя I only consider the last number. I don't say that I perform minimal number of operations, just that this should work. – Ivaylo Strandjev Jan 23 '13 at 14:29
  • @Толя try to figure out for yourself. Easiest way to prove its correctness is to prove something that always holds true. In this case prove that on each step the array up to i is sorted and that the array [i, size-1] is still sorted according to the statement. – Ivaylo Strandjev Jan 23 '13 at 14:38
  • @Ivaylo: Good solution. But for i=4 it does fail. I think we can handle this by doing the following change:if i crosses the index where pivot element is there then we must first decrement right index and then compare the element at index with it and follow the process till we reach right index. – user1225752 Jan 23 '13 at 14:43
  • @user1225752 I have added another edit please take a look at it. You need two phases - one where you shrink the array from the left and one - from the right. – Ivaylo Strandjev Jan 23 '13 at 14:44
  • @Ivalyo : I think the solution fails for this array a[]= {10, 11,12,13,9,8,7,0} – user1225752 Jan 23 '13 at 14:52
  • @user1225752 it seems the future is not so bright: http://stackoverflow.com/a/2571104/812912 What I try to do is essentially a merge that is in place and it seems I underestimate its complexity. I will add another final edit of my answer and remove my wrong solution. Sorry for that and for all the false positives. – Ivaylo Strandjev Jan 23 '13 at 14:58
6

My solution:

  1. Take 2 pointers start of array and end of array.

  2. Into result array write a min(or max if you need sort in descending) value from both pointers, and shift pointer to 1 position (start pointer +1 position and end pointer -1 position

  3. Repeat till start pointer will be placed after end pointer.

Complexity of solution is O(N). Required memory is O(N)

Pseudocode:

function Sort(a)
{
  startPointer = 0;
  endPointer = a.length-1;
  result = new Array of size a.length
  while (startPointer <= endPointer)
  {
    var newValue;
    if (a[startPointer] < a[endPointer])
    {
      newValue = a[startPointer];
      startPointer +1
    }
    else
    {
      newValue = a[endPointer];
      endPointer -1
    }
    result[a.length - startPointer - endPointer] = newValue;
  }

  return result;
}

Solution for updated question:

As solution usde partil sorting of first part of array.

Pointers on (10 and 11) {10, 12, 14, 16, 15, 13, 11}

Pointers on (12 and 11) Swap 12 and 11 {10, 11, 14, 16, 15, 13, 12}

Pointers on (14 and 12) Swap 14 and 12 {10, 11, 12, 16, 15, 13, 14} // Move pointer from 14 to 13 a it lesser.

Now we have sorted {10, 11, 12} and sub problem for {16, 15, 13, 14} (N for sub problem decreased twicely)

Complexity for this algorithm is: O(N) + (N/2) + O(N/4) + ... totally is O(N)

Image for better illustration:

enter image description here

Толя
  • 2,839
  • 15
  • 23
  • Have you tested this algorithm to see if it works?. I don't think this is the right solution. I believe you would need to divide the array into sorted subarrays and merge those subarrays to get the sorted array. This could be done with O(nLog(k)) complexity if merge sort is used to merge the 'K' sorted subarrays. – Gautham Honnavara Feb 16 '19 at 20:38
2

Use the property of the question.

You need not sort the array that is already sorted. Find the point where the slope changes and then use a suitable algorithm to get a complete sorted array.

You could consider implementing a bitonic sorter which uses this property efficiently.

sr01853
  • 6,043
  • 1
  • 19
  • 39