Skip to main content

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.

Last updated on by Kalkicode




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.

New Comment