0
$\begingroup$

Suppose there is an array $A[1..n]$.$A$ contains a permutation of $\{1,2,3,\dots,n\}$.

We run the following algorithm $m$ times to sort $A$:

  • for each odd index of $A$ from left to right ,respectively, put $A[i]$ be the minimum of its and right adjacent (if exists). Also we store index of larger number for $A[i]$.

  • for each even index of $A$ from left to right ,respectively, put $A[i]$ be the minimum of it and right adjacent (if exists).Also we store index of larger number for $A[i]$.

I guess after $ \lceil \frac{n}{2}\rceil $ the algorithm sort number in increasing order. To prove my guess I try to use induction as follow:

For $n=1$ obviously the algorithm works correctly. Suppose it work for $n=k$ now to extend this assumption to $n=k+1$ I found a observation that after at most $ \lceil \frac{k+1}{2}\rceil $ largest and smallest elements will be in their correct place, now how I can conclude that all elements also be in their correct place after $ \lceil \frac{n}{2}\rceil $ repeating of the algorithm?

$\endgroup$
6
  • $\begingroup$ "I found a observation" is not a sufficient argument. You must justify. $\endgroup$
    – user16034
    Commented Feb 10, 2023 at 9:30
  • $\begingroup$ "Also we augment index of larger number to $A[i]$": no idea what this means. $\endgroup$
    – user16034
    Commented Feb 10, 2023 at 9:31
  • $\begingroup$ The global argument does not seem correct. When you apply the algorithm to $n=k+1$, we don't know where the additional element goes, and that can break the sort of the $k$ first elements and induction is not granted. $\endgroup$
    – user16034
    Commented Feb 10, 2023 at 9:33
  • $\begingroup$ @Mohammad.Rostami Could you show how you algorithm works for example on array $[9,6,8,7]$? How does it output the sorted array? $\endgroup$
    – John L.
    Commented Feb 10, 2023 at 16:14
  • $\begingroup$ At the first iteration we have $[6,7,9,8]$ and array with be sort. $\endgroup$
    – ErroR
    Commented Feb 11, 2023 at 17:10

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.