-1

The question is:

Given an unsorted array, sort it in such a way that the first element is the largest, the second element is the smallest, the third element is the second largest, etc.

Follow up: Can you do it without using extra space?

Example:

[2, 4, 3, 5, 1] -> [5, 1, 4, 2, 3]

I want to be able to sort the array without using extra space. What is the most efficient solution? I can only think of an O(n2) solution that loops through the array to find the next largest and next smallest elements. Is there a more efficient solution?

I've looked at the related questions Sorting an array with alternate smallest and largest values and Sorting an array with alternate smallest-largest values but the answers didn't help with my question.

Community
  • 1
  • 1
user7634144
  • 31
  • 1
  • 4
  • Why do the answers to the linked questions not help with your question? The last one provides working code that's O(n) to rearrange the array after it's been sorted. Sorting takes O(n log n), in the general case. Although if you know that the numbers are unique and contiguous, you can do the sort in O(n), as well. – Jim Mischel Apr 11 '17 at 19:29
  • @JimMischel I don't understand the logic behind the code in the last question so asked a new question. – user7634144 Apr 12 '17 at 02:18

1 Answers1

0

precondition : using deque.

1.sorting the array.

loop)

2.pop_back(array) -> insert that element in i*2 position.

example) 1, 2, 3, 4, 5, 6, 7

a) 7 (insert to 0) -> 1 2 3 4 5 6 => 7 1 2 3 4 5 6

b) 6 (insert to 2) -> 7 1 2 3 4 5 => 7 1 6 2 3 4 5

c) 5 (insert to 4) -> 7 1 6 2 3 4 => 7 1 6 2 5 3 4 (finished)

Its complexity maybe O(nlog(n)) + O(n/2)

jingbe
  • 59
  • 6
  • Those inserts are expensive. Inserting 7 to 0 requires moving items 1-6 down a bit. Each insertion is O(n), or some fraction thereof. I think you'll find that your algorithm is O(n log n) + O(((n/2)^2)/2), which would likely be considered O(n^2). – Jim Mischel Apr 11 '17 at 18:26