# Alternative Sorting of an array elements

The problem is to sort the elements of an array in an alternative manner. First, the array should be sorted in ascending order. Then, the sorted array should be converted into an alternating arrangement such that the first element is the maximum element, the second element is the minimum element, the third element is the second maximum element, and so on.

## Example

Consider the array: [1, 6, 9, 4, 3, 7, 8, 2, 10]

After sorting the array in ascending order, it becomes: [1, 2, 3, 4, 6, 7, 8, 9, 10]

After converting the sorted array into an alternating arrangement, it becomes: [10, 1, 9, 2, 8, 3, 7, 4, 6]

## Idea to Solve the Problem

The C program uses the Max Heap approach to sort the array in ascending order. The program then converts the sorted array into an alternating arrangement in-place by swapping elements.

## Algorithm

1. Implement a Max Heap to sort the array in ascending order.
2. Starting from the beginning, for every two elements (except the last one), swap them to form the alternating arrangement.
3. The final array will be in the required alternating order.

## Pseudocode

``````function swap(arr[], i, j):
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp

function compare(arr[], left, right, root, size):
location = -1
if left < size and arr[left] > arr[root]:
if right < size and arr[right] > arr[left]:
swap(arr, right, root)
location = right
else:
swap(arr, left, root)
location = left
else if right < size and arr[right] > arr[root]:
swap(arr, right, root)
location = right
return location

function heap(arr[], size, root):
left = 2 * root + 1
right = 2 * root + 2
next = compare(arr, left, right, root, size)
if next != -1:
heap(arr, size, next)

function sort(arr[], size):
for i from (size/2) - 1 to 0:
heap(arr, size, i)
for i from size-1 to 0:
swap(arr, 0, i)
heap(arr, i, 0)

function max_min(arr[], size, i, location):
if i <= size/2 and location < size:
min = arr[i]
max = arr[size - 1 - i]
max_min(arr, size, i+1, location+2)
if size - 1 - i == i:
arr[location] = arr[i]
else:
arr[location] = max
arr[location + 1] = min``````

## Code Solution

``````//C Program
//Alternative Sorting of an array elements
#include <stdio.h>

//Swap two element in array
void swap(int arr[],int first,int second)
{
int auxiliary=arr[first];

arr[first]=arr[second];

arr[second]=auxiliary;
}
//Check array is form of max heap or not
int compare(int arr[],int left,int right,int root,int size)
{
int location = -1;

if(left < size &&  arr[left] > arr[root] )
{

if(right < size && arr[right] > arr[left])
{
//swap array element
swap(arr,right,root);
location = right;
}
else
{
//swap array element
swap(arr,left,root);
location = left;
}
}
else if(right < size && arr[right] > arr[root])
{
//swap array element
swap(arr,right,root);
location = right;
}
return location;
}

void heap(int arr[],int size,int root)
{
//Get The Location
int left  = 2*root+1;
int right = 2*root+2;

// Check modification of array
int next = compare(arr, left, right, root, size);

if(next != -1)
{
//When array is not form of max heap then its converted
heap(arr,size,next);
}
}
void print_data(int arr[],int size)
{
printf("\n");
for(int i = 0; i < size; i++)
{
printf("%3d",arr[i] );
}
}
//Sort the array element
void sort(int arr[],int size)
{

for (int i = (size/2)-1; i >= 0; i--)
{
heap(arr,size,i);
}
//convert heap into sorted form
for (int i = size-1; i >= 0; i--)
{
swap(arr, 0, i);
heap(arr, i, 0);
}
}
//Convert array into min max form
void max_min(int arr[],int size,int i,int location)
{
if(i <= size/2 && location<size)
{
//Fetch min max data
int min=arr[i];
int max=arr[size-1-i];

//Recursive call
max_min(arr, size, i+1,location+2);

if(size-1-i==i)
{
arr[location] = arr[i];
}
else
{
//Assign min max data
arr[location] = max;
arr[location+1] = min;
}
}
}
int main()
{
//Define array
int arr[] = {1, 6, 9, 4, 3, 7, 8, 2, 10};

//Get the size of array elements
int size = sizeof(arr)/sizeof(arr[0]);

print_data(arr,size);

sort(arr,size);

max_min(arr,size,0,0);

print_data(arr,size);

return 0;
}```
```

#### Output

``````  1  6  9  4  3  7  8  2 10
10  1  9  2  8  3  7  4  6``````
``````/*
C++ Program
Find nth digit of number
From right to left
*/
#include<iostream>

using namespace std;

class MyArray {
public:

//Swap two element in array
void swap(int arr[], int first, int second) {
int auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
//Check array is form of max heap or not
int compare(int arr[], int left, int right, int root, int size) {
int location = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
//swap array element
this->swap(arr, right, root);
location = right;
} else {
//swap array element
this->swap(arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
//swap array element
this->swap(arr, right, root);
location = right;
}
return location;
}
void heap(int arr[], int size, int root) {
//Get The Location
int left = 2 *root + 1;
int right = 2 *root + 2;
// Check modification of array
int next = this->compare(arr, left, right, root, size);
if (next != -1) {
//When array is not form of max heap then its converted
this->heap(arr, size, next);
}
}
void print_data(int arr[], int size) {
cout << "\n";
int i = 0;
while (i < size) {
cout << " " << arr[i];
i++;
}
}
//Sort the array element
void sort(int arr[], int size) {
int i = (size / 2) - 1;
while (i >= 0) {
this->heap(arr, size, i);
i--;
}
//convert heap into sorted form
i = size - 1;
while (i >= 0) {
this->swap(arr, 0, i);
this->heap(arr, i, 0);
i--;
}
}
//Convert array into min max form
void max_min(int arr[], int size, int i, int location) {
if (i <= size / 2 && location < size) {
//Fetch min max data
int min = arr[i];
int max = arr[size - 1 - i];
//Recursive call
this->max_min(arr, size, i + 1, location + 2);
if (size - 1 - i == i) {
arr[location] = arr[i];
} else {
//Assign min max data
arr[location] = max;
arr[location + 1] = min;
}
}
}
};
int main() {
MyArray obj ;
//Define array
int arr[] = {
1,
6,
9,
4,
3,
7,
8,
2,
10
};
//Get the size of array elements
int size = sizeof(arr) / sizeof(arr[0]);
obj.print_data(arr, size);
obj.sort(arr, size);
obj.max_min(arr, size, 0, 0);
cout << "\n Max Min Form";
obj.print_data(arr, size);
return 0;
}```
```

#### Output

`````` 1 6 9 4 3 7 8 2 10
Max Min Form
10 1 9 2 8 3 7 4 6``````
``````/*
Java Program
Find nth digit of number
From right to left
*/
public class MyArray {
//Swap two element in array
public void swap(int []arr,int first,int second)
{
int auxiliary=arr[first];

arr[first]=arr[second];

arr[second]=auxiliary;
}
//Check array is form of max heap or not
public int compare(int []arr,int left,int right,int root,int size)
{
int location = -1;

if(left < size &&  arr[left] > arr[root] )
{

if(right < size && arr[right] > arr[left])
{
//swap array element
swap(arr,right,root);
location = right;
}
else
{
//swap array element
swap(arr,left,root);
location = left;
}
}
else if(right < size && arr[right] > arr[root])
{
//swap array element
swap(arr,right,root);
location = right;
}
return location;
}

public void heap(int []arr,int size,int root)
{
//Get The Location
int left  = 2*root+1;
int right = 2*root+2;

// Check modification of array
int next = compare(arr, left, right, root, size);

if(next != -1)
{
//When array is not form of max heap then its converted
heap(arr,size,next);
}
}
public void print_data(int []arr,int size)
{
System.out.print("\n");
for(int i = 0; i < size; i++)
{
System.out.print(" "+arr[i] );
}
}
//Sort the array element
public void sort(int []arr,int size)
{

for (int i = (size/2)-1; i >= 0; i--)
{
heap(arr,size,i);
}
//convert heap into sorted form
for (int i = size-1; i >= 0; i--)
{
swap(arr, 0, i);
heap(arr, i, 0);
}
}
//Convert array into min max form
public void max_min(int []arr,int size,int i,int location)
{
if(i <= size/2 && location<size)
{
//Fetch min max data
int min=arr[i];
int max=arr[size-1-i];

//Recursive call
max_min(arr, size, i+1,location+2);

if(size-1-i==i)
{
arr[location] = arr[i];
}
else
{
//Assign min max data
arr[location] = max;
arr[location+1] = min;
}
}
}
public static void main(String[] args) {

MyArray obj = new MyArray();
//Define array
int []arr = {1, 6, 9, 4, 3, 7, 8, 2, 10};

//Get the size of array elements
int size = arr.length;

obj.print_data(arr,size);

obj.sort(arr,size);

obj.max_min(arr,size,0,0);
System.out.print("\n Max Min Form");
obj.print_data(arr,size);
}
}```
```

#### Output

`````` 1 6 9 4 3 7 8 2 10
Max Min Form
10 1 9 2 8 3 7 4 6``````
``````/*
C# Program
Find nth digit of number
From right to left
*/
using System;
public class MyArray {
//Swap two element in array
public void swap(int[] arr, int first, int second) {
int auxiliary = arr[first];

arr[first] = arr[second];

arr[second] = auxiliary;
}
//Check array is form of max heap or not
public int compare(int[] arr, int left, int right, int root, int size) {
int location = -1;

if (left < size && arr[left] > arr[root]) {

if (right < size && arr[right] > arr[left]) {
//swap array element
swap(arr, right, root);
location = right;
} else {
//swap array element
swap(arr, left, root);
location = left;
}
} else if (right < size && arr[right] > arr[root]) {
//swap array element
swap(arr, right, root);
location = right;
}
return location;
}

public void heap(int[] arr, int size, int root) {
//Get The Location
int left = 2 * root + 1;
int right = 2 * root + 2;

// Check modification of array
int next = compare(arr, left, right, root, size);

if (next != -1) {
//When array is not form of max heap then its converted
heap(arr, size, next);
}
}
public void print_data(int[] arr, int size) {
Console.Write("\n");
for (int i = 0; i < size; i++) {
Console.Write(" " + arr[i]);
}
}
//Sort the array element
public void sort(int[] arr, int size) {

for (int i = (size / 2) - 1; i >= 0; i--) {
heap(arr, size, i);
}
//convert heap into sorted form
for (int i = size - 1; i >= 0; i--) {
swap(arr, 0, i);
heap(arr, i, 0);
}
}
//Convert array into min max form
public void max_min(int[] arr, int size, int i, int location) {
if (i <= size / 2 && location < size) {
//Fetch min max data
int min = arr[i];
int max = arr[size - 1 - i];

//Recursive call
max_min(arr, size, i + 1, location + 2);

if (size - 1 - i == i) {
arr[location] = arr[i];
} else {
//Assign min max data
arr[location] = max;
arr[location + 1] = min;
}
}
}
public static void Main(String[] args) {

MyArray obj = new MyArray();
//Define array
int[] arr = {
1,
6,
9,
4,
3,
7,
8,
2,
10
};

//Get the size of array elements
int size = arr.Length;

obj.print_data(arr, size);

obj.sort(arr, size);

obj.max_min(arr, size, 0, 0);
Console.Write("\n Max Min Form");
obj.print_data(arr, size);
}
}```
```

#### Output

`````` 1 6 9 4 3 7 8 2 10
Max Min Form
10 1 9 2 8 3 7 4 6``````
``````<?php
/*
Php Program
Find nth digit of number
From right to left
*/
class MyArray {
//Swap two element in array
public 	function swap(&\$arr, \$first, \$second) {
\$auxiliary = \$arr[\$first];
\$arr[\$first] = \$arr[\$second];
\$arr[\$second] = \$auxiliary;
}
//Check array is form of max heap or not
public 	function compare(&\$arr, \$left, \$right, \$root, \$size) {
\$location = -1;
if (\$left < \$size && \$arr[\$left] > \$arr[\$root]) {
if (\$right < \$size && \$arr[\$right] > \$arr[\$left]) {
//swap array element
\$this->swap(\$arr, \$right, \$root);
\$location = \$right;
} else {
//swap array element
\$this->swap(\$arr, \$left, \$root);
\$location = \$left;
}
} else
if (\$right < \$size && \$arr[\$right] > \$arr[\$root]) {
//swap array element
\$this->swap(\$arr, \$right, \$root);
\$location = \$right;
}
return \$location;
}
public 	function heap(&\$arr, \$size, \$root) {
//Get The Location
\$left = 2 *\$root + 1;
\$right = 2 *\$root + 2;
// Check modification of array
\$next = \$this->compare(\$arr, \$left, \$right, \$root, \$size);
if (\$next != -1) {
//When array is not form of max heap then its converted
\$this->heap(\$arr, \$size, \$next);
}
}
public 	function print_data(\$arr, \$size) {
echo("\n");
for (\$i = 0; \$i < \$size; \$i++) {
echo(" ". \$arr[\$i]);
}
}
//Sort the array element
public 	function sort(&\$arr, \$size) {
for (\$i = (intval(\$size / 2)) - 1; \$i >= 0; \$i--) {
\$this->heap(\$arr, \$size, \$i);
}
//convert heap into sorted form
for (\$i = \$size - 1; \$i >= 0; \$i--) {
\$this->swap(\$arr, 0, \$i);
\$this->heap(\$arr, \$i, 0);
}
}
//Convert array into min max form
public 	function max_min(&\$arr, \$size, \$i, \$location) {
if (\$i <= intval(\$size / 2) && \$location < \$size) {
//Fetch min max data
\$min = \$arr[\$i];
\$max = \$arr[\$size - 1 - \$i];
//Recursive call
\$this->max_min(\$arr, \$size, \$i + 1, \$location + 2);
if (\$size - 1 - \$i == \$i) {
\$arr[\$location] = \$arr[\$i];
} else {
//Assign min max data
\$arr[\$location] = \$max;
\$arr[\$location + 1] = \$min;
}
}
}
};

function main() {
\$obj = new MyArray();
//Define array
\$arr = array(1, 6, 9, 4, 3, 7, 8, 2, 10);
//Get the size of array elements
\$size = count(\$arr);
\$obj->print_data(\$arr, \$size);
\$obj->sort(\$arr, \$size);
\$obj->max_min(\$arr, \$size, 0, 0);
echo("\n Max Min Form");
\$obj->print_data(\$arr, \$size);
}
main();```
```

#### Output

`````` 1 6 9 4 3 7 8 2 10
Max Min Form
10 1 9 2 8 3 7 4 6``````
``````/*
Node Js Program
Find nth digit of number
From right to left
*/
class MyArray {
//Swap two element in array
swap(arr, first, second) {
var auxiliary = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
//Check array is form of max heap or not
compare(arr, left, right, root, size) {
var location = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
//swap array element
this.swap(arr, right, root);
location = right;
} else {
//swap array element
this.swap(arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
//swap array element
this.swap(arr, right, root);
location = right;
}
return location;
}
heap(arr, size, root) {
//Get The Location
var left = 2 *root + 1;
var right = 2 *root + 2;
// Check modification of array
var next = this.compare(arr, left, right, root, size);
if (next != -1) {
//When array is not form of max heap then its converted
this.heap(arr, size, next);
}
}
print_data(arr, size) {
process.stdout.write("\n");
for (var i = 0; i < size; i++) {
process.stdout.write(" " + arr[i]);
}
}
//Sort the array element
sort(arr, size) {
for (var i = (parseInt(size / 2)) - 1; i >= 0; i--) {
this.heap(arr, size, i);
}
//convert heap into sorted form
for (var i = size - 1; i >= 0; i--) {
this.swap(arr, 0, i);
this.heap(arr, i, 0);
}
}
//Convert array into min max form
max_min(arr, size, i, location) {
if (i <= parseInt(size / 2) && location < size) {
//Fetch min max data
var min = arr[i];
var max = arr[size - 1 - i];
//Recursive call
this.max_min(arr, size, i + 1, location + 2);
if (size - 1 - i == i) {
arr[location] = arr[i];
} else {
//Assign min max data
arr[location] = max;
arr[location + 1] = min;
}
}
}
}

function main(args) {
var obj = new MyArray();
//Define array
var arr = [1, 6, 9, 4, 3, 7, 8, 2, 10];
//Get the size of array elements
var size = arr.length;
obj.print_data(arr, size);
obj.sort(arr, size);
obj.max_min(arr, size, 0, 0);
process.stdout.write("\n Max Min Form");
obj.print_data(arr, size);
}
main();```
```

#### Output

`````` 1 6 9 4 3 7 8 2 10
Max Min Form
10 1 9 2 8 3 7 4 6``````
``````# Python 3 Program
# Find nth digit of number
# From right to left
class MyArray :
# Swap two element in array
def swap(self, arr, first, second) :
auxiliary = arr[first]
arr[first] = arr[second]
arr[second] = auxiliary

# Check array is form of max heap or not
def compare(self, arr, left, right, root, size) :
location = -1
if (left < size and arr[left] > arr[root]) :
if (right < size and arr[right] > arr[left]) :
# swap array element
self.swap(arr, right, root)
location = right
else :
# swap array element
self.swap(arr, left, root)
location = left

elif (right < size and arr[right] > arr[root]) :
# swap array element
self.swap(arr, right, root)
location = right

return location

def heap(self, arr, size, root) :
# Get The Location
left = 2 * root + 1
right = 2 * root + 2
#  Check modification of array
next = self.compare(arr, left, right, root, size)
if (next != -1) :
# When array is not form of max heap then its converted
self.heap(arr, size, next)

def print_data(self, arr, size) :
print(end="\n")
i = 0
while (i < size) :
print(" ", arr[i],end="")
i += 1

# Sort the array element
def sort(self, arr, size) :
i = (int(size / 2)) - 1
while (i >= 0) :
self.heap(arr, size, i)
i -= 1

# convert heap into sorted form
i = size - 1
while (i >= 0) :
self.swap(arr, 0, i)
self.heap(arr, i, 0)
i -= 1

# Convert array into min max form
def max_min(self, arr, size, i, location) :
if (i <= int(size / 2) and location < size) :
# Fetch min max data
min = arr[i]
max = arr[size - 1 - i]
# Recursive call
self.max_min(arr, size, i + 1, location + 2)
if (size - 1 - i == i) :
arr[location] = arr[i]
else :
# Assign min max data
arr[location] = max
arr[location + 1] = min

def main() :
obj = MyArray()
# Define array
arr = [1, 6, 9, 4, 3, 7, 8, 2, 10]
# Get the size of array elements
size = len(arr)
obj.print_data(arr, size)
obj.sort(arr, size)
obj.max_min(arr, size, 0, 0)
print("\n Max Min Form")
obj.print_data(arr, size)

if __name__ == "__main__":
main()```
```

#### Output

`````` 1 6 9 4 3 7 8 2 10
Max Min Form

10 1 9 2 8 3 7 4 6``````
``````# Ruby Program
# Find nth digit of number
# From right to left
class MyArray
# Swap two element in array
def swap(arr, first, second)
auxiliary = arr[first]
arr[first] = arr[second]
arr[second] = auxiliary
end
# Check array is form of max heap or not
def compare(arr, left, right, root, size)
location = -1
if (left < size and arr[left] > arr[root])
if (right < size and arr[right] > arr[left])
# swap array element
self.swap(arr, right, root)
location = right
else
# swap array element
self.swap(arr, left, root)
location = left
end
elsif (right < size and arr[right] > arr[root])
# swap array element
self.swap(arr, right, root)
location = right
end
return location
end
def heap(arr, size, root)
# Get The Location
left = 2 * root + 1
right = 2 * root + 2
#  Check modification of array
location = self.compare(arr, left, right, root, size)
if (location != -1)
# When array is not form of max heap then its converted
self.heap(arr, size, location)
end
end
def print_data(arr, size)
print("\n")
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
end
# Sort the array element
def sort(arr, size)
i = (size / 2) - 1
while (i >= 0)
self.heap(arr, size, i)
i -= 1
end
# convert heap into sorted form
i = size - 1
while (i >= 0)
self.swap(arr, 0, i)
self.heap(arr, i, 0)
i -= 1
end
end
# Convert array into min max form
def max_min(arr, size, i, location)
if (i <= size / 2 and location < size)
# Fetch min max data
min = arr[i]
max = arr[size - 1 - i]
# Recursive call
self.max_min(arr, size, i + 1, location + 2)
if (size - 1 - i == i)
arr[location] = arr[i]
else
# Assign min max data
arr[location] = max
arr[location + 1] = min
end
end
end
end
def main()
obj = MyArray.new()
# Define array
arr = [1, 6, 9, 4, 3, 7, 8, 2, 10]
# Get the size of array elements
size = arr.length
obj.print_data(arr, size)
obj.sort(arr, size)
obj.max_min(arr, size, 0, 0)
print("\n Max Min Form")
obj.print_data(arr, size)
end
main()```
```

#### Output

`````` 1 6 9 4 3 7 8 2 10
Max Min Form
10 1 9 2 8 3 7 4 6``````
``````/*
Scala Program
Find nth digit of number
From right to left
*/
class MyArray {
//Swap two element in array
def swap(arr: Array[Int], first: Int, second: Int): Unit = {
var auxiliary: Int = arr(first);arr(first) = arr(second);arr(second) = auxiliary;
}
//Check array is form of max heap or not
def compare(arr: Array[Int], left: Int, right: Int, root: Int, size: Int): Int = {
var location: Int = -1;
if (left < size && arr(left) > arr(root)) {
if (right < size && arr(right) > arr(left)) {
//swap array element
this.swap(arr, right, root);
location = right;
} else {
//swap array element
this.swap(arr, left, root);
location = left;
}
} else
if (right < size && arr(right) > arr(root)) {
//swap array element
this.swap(arr, right, root);
location = right;
}
return location;
}
def heap(arr: Array[Int], size: Int, root: Int): Unit = {
//Get The Location
var left: Int = 2 * root + 1;
var right: Int = 2 * root + 2;
// Check modification of array
var next: Int = this.compare(arr, left, right, root, size);
if (next != -1) {
//When array is not form of max heap then its converted
this.heap(arr, size, next);
}
}
def print_data(arr: Array[Int], size: Int): Unit = {
print("\n");
var i: Int = 0;
while (i < size) {
print(" " + arr(i));
i += 1;
}
}
//Sort the array element
def sort(arr: Array[Int], size: Int): Unit = {
var i: Int = ((size / 2).toInt) - 1;
while (i >= 0) {
this.heap(arr, size, i);
i -= 1;
}
//convert heap into sorted form
i = size - 1;
while (i >= 0) {
this.swap(arr, 0, i);
this.heap(arr, i, 0);
i -= 1;
}
}
//Convert array into min max form
def max_min(arr: Array[Int], size: Int, i: Int, location: Int): Unit = {
if (i <= (size / 2).toInt && location < size) {
//Fetch min max data
var min: Int = arr(i);
var max: Int = arr(size - 1 - i);
//Recursive call
this.max_min(arr, size, i + 1, location + 2);
if (size - 1 - i == i) {
arr(location) = arr(i);
} else {
//Assign min max data
arr(location) = max;
arr(location + 1) = min;
}
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
//Define array
var arr: Array[Int] = Array(1, 6, 9, 4, 3, 7, 8, 2, 10);
//Get the size of array elements
var size: Int = arr.length;
obj.print_data(arr, size);
obj.sort(arr, size);obj.
max_min(arr, size, 0, 0);
print("\n Max Min Form");
obj.print_data(arr, size);
}
}```
```

#### Output

`````` 1 6 9 4 3 7 8 2 10
Max Min Form
10 1 9 2 8 3 7 4 6``````
``````/*
Swift 4 Program
Find nth digit of number
From right to left
*/
class MyArray {
//Swap two element in array
func swap(_ arr: inout [Int], _ first: Int, _ second: Int) {
let auxiliary: Int = arr[first];
arr[first] = arr[second];
arr[second] = auxiliary;
}
//Check array is form of max heap or not
func compare(_ arr: inout [Int], _ left: Int, _ right: Int, _ root: Int, _ size: Int) -> Int {
var location: Int = -1;
if (left < size && arr[left] > arr[root]) {
if (right < size && arr[right] > arr[left]) {
//swap array element
self.swap(&arr, right, root);
location = right;
} else {
//swap array element
self.swap(&arr, left, root);
location = left;
}
} else
if (right < size && arr[right] > arr[root]) {
//swap array element
self.swap(&arr, right, root);
location = right;
}
return location;
}
func heap(_ arr: inout [Int], _ size: Int, _ root: Int) {
//Get The Location
let left: Int = 2 * root + 1;
let right: Int = 2 * root + 2;
// Check modification of array
let next: Int = self.compare(&arr, left, right, root, size);
if (next != -1) {
//When array is not form of max heap then its converted
self.heap(&arr, size, next);
}
}
func print_data(_ arr: [Int], _ size: Int) {
print(terminator:"\n");
var i: Int = 0;
while (i < size) {
print(" ", arr[i],terminator:"");
i += 1;
}
}
//Sort the array element
func sort(_ arr: inout [Int], _ size: Int) {
var i: Int = (size / 2) - 1;
while (i >= 0) {
self.heap(&arr, size, i);
i -= 1;
}
//convert heap into sorted form
i = size - 1;
while (i >= 0) {
self.swap(&arr, 0, i);
self.heap(&arr, i, 0);
i -= 1;
}
}
//Convert array into min max form
func max_min(_ arr: inout [Int], _ size: Int, _ i: Int, _ location: Int) {
if (i <= size / 2 && location < size) {
//Fetch min max data
let min: Int = arr[i];
let max: Int = arr[size - 1 - i];
//Recursive call
self.max_min(&arr, size, i + 1, location + 2);
if (size - 1 - i == i) {
arr[location] = arr[i];
} else {
//Assign min max data
arr[location] = max;
arr[location + 1] = min;
}
}
}
}
func main() {
let obj: MyArray = MyArray();
//Define array
var arr: [Int] = [1, 6, 9, 4, 3, 7, 8, 2, 10];
//Get the size of array elements
let size: Int = arr.count;
obj.print_data(arr, size);
obj.sort(&arr, size);
obj.max_min(&arr, size, 0, 0);
print("\n Max Min Form");
obj.print_data(arr, size);
}
main();```
```

#### Output

``````  1  6  9  4  3  7  8  2  10
Max Min Form

10  1  9  2  8  3  7  4  6``````

## Time Complexity

• The time complexity of the above algorithm is O(n log n), where n is the size of the array.
• The Max Heap approach has a time complexity of O(n log n) for sorting.
• The conversion of the sorted array into an alternating arrangement has a time complexity of O(n) because it requires traversing the array once.

## Resultant Output Explanation

The given C program implements the above algorithm to sort the array [1, 6, 9, 4, 3, 7, 8, 2, 10] in an alternative manner.

In the provided output, the program displays the original array before and after the sorting and conversion process.

The output shows that the original array [1, 6, 9, 4, 3, 7, 8, 2, 10] is sorted in ascending order to become [1, 2, 3, 4, 6, 7, 8, 9, 10]. Then, the sorted array is converted into the alternating arrangement [10, 1, 9, 2, 8, 3, 7, 4, 6].

The program correctly sorts the array and converts it into an alternating arrangement in-place.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.