An Alternating Sort of the set {1, 2, 3, ..., n} is an arrangement of those numb
ID: 656727 • Letter: A
Question
An Alternating Sort of the set {1, 2, 3, ..., n} is an arrangement of those numbers into an order c1, ..., cn such that no element ci is between ci - 1 and ci + 1 for any value of i, and c1< c2. In other words, ci < ci+ 1 if i is odd and ci > ci+ 1 if i is even. For example, there is only one alternating sorts of {1}: 1 For example, there is only one alternating sorts of {1,2}. 1,2 For example, there are two alternating sorts of {1,2,3}: 1<3>2, 2<3>1
For example, the five alternating sorts of {1, 2, 3, 4} are:
1, 3, 2, 4 because 1 < 3 > 2 <4
1, 4, 2, 3 because 1 < 4 > 2 < 3
2, 3, 1, 4 because 2 < 3 > 1 < 4
2, 4, 1, 3 because 2 < 4 > 1 < 3
3, 4, 1, 2 because 3 < 4 > 1 < 2
For n=
1
2
3
4
5
6
7
8
9
10
Total # of
Alternating Sorts
1
1
2
5
16
61
272
1385
7936
50521
Please provide computer program in any programming language for Alternating Sort:
For a given n (n<11), get the total number of the alternating sorts on set {1,2,...,n}.
For n=
1
2
3
4
5
6
7
8
9
10
Total # of
Alternating Sorts
1
1
2
5
16
61
272
1385
7936
50521
Explanation / Answer
Algorithm for Alternative Sort:
procedure AlternatingSort(A : list of elements)
n=length(A)
count =0 // to count the number of alternating sorts done
for i=0 to n
if i and 1 // checks position i is odd
for j=2 to n increment by 2
count =count +1
if A[j] < A[j-1] then
count =count +1
call swap(A[j-1],A[j]);
endif
endfor
else // means position i is even
for j=1 to n increment by 2
count =count +1
if A[j] < A[j-1] then
count =count +1
call swap(A[j-1],A[j]);
endif
endfor
end procedure
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.