Given an array of n elements, you need to sort these elements in an array so that first even and even odd ones follow.

Closed due to the fact that the issue is too general for Kromster , fori1ton , Vladyslav Matviienko , Vladimir Martyanov , Regent September 8, '15 at 12:08 .

Please correct the question so that it describes the specific problem with sufficient detail to determine the appropriate answer. Do not ask a few questions at once. See “How to ask a good question?” For clarification. If the question can be reformulated according to the rules set out in the certificate , edit it .

  • @cheremushkin, if C ++, then what didn’t suit the standard sort with a comparator? - avp
  • What language? And yet, you for one view of the array and in place? Otherwise, use any suitable sorting, when comparing even to odd, consider that even is smaller. - avp

1 answer 1

Enter the index i , set it to the number of the last element and decrease it until the element at this index becomes even. (If you come to the beginning, the algorithm is over.) Walk through the array from beginning to end to index i . If you see an odd element, exchange it with the element at index i , and decrease i until you find an even element. Everything.

Thus, one view is enough, the running time is O(длина массива) .

  • "O time (array length)" For the first time I see this treatment with the O (n) notation. - Kromster
  • @Kromster: and that seems to be self-evident and correct :) - VladD
  • Something I do not remember that O notation describes the time complexity in prime numbers. - Kromster