Given a bitonic array arr[] the task is to sort the given bitonic array.
A Bitonic Sequence is a sequence of numbers that is first strictly increasing then after a point strictly decreasing.
Examples:
Input: arr[] = {5, 10, 15, 25, 20, 3, 2, 1}
Output: 1 2 3 5 10 15 20 25
Input: arr[] = {5, 20, 30, 40, 36, 33, 25, 15, 10}
Output: 5 10 15 20 25 30 33 36 40
Approach:
- The idea is to initialize a variable K to the highest power of 2 in size of the array such as to compare elements that are K distant apart.
- Swap the elements if they are not in increasing order.
- Reduce K by half and repeat the process until K becomes zero.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to Sort a Bitonic array// in constant spacevoid sortArr(int a[], int n){ int i, k; // Initialize the value of k k = (int)log2(n); k = pow(2, k); // In each iteration compare elements // k distance apart and swap if // they are not in order while (k > 0) { for (i = 0; i + k < n; i++) if (a[i] > a[i + k]) swap(a[i], a[i + k]); // k is reduced to half // after every iteration k = k / 2; } // Print the array elements for (i = 0; i < n; i++) { cout << a[i] << " "; }}// Driver Codeint main(){ // Given array arr[] int arr[] = { 5, 20, 30, 40, 36, 33, 25, 15, 10 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call sortArr(arr, n); return 0;} |
Java
// Java program for the above approach import java.io.*;class GFG{ // Function to Sort a Bitonic array // in constant space static void sortArr(int a[], int n) { int i, k; // Initialize the value of k k = (int)(Math.log(n) / Math.log(2)); k = (int) Math.pow(2, k); // In each iteration compare elements // k distance apart and swap if // they are not in order while (k > 0) { for(i = 0; i + k < n; i++) if (a[i] > a[i + k]) { int tmp = a[i]; a[i] = a[i + k]; a[i + k] = tmp; } // k is reduced to half // after every iteration k = k / 2; } // Print the array elements for(i = 0; i < n; i++) { System.out.print(a[i] + " "); } } // Driver codepublic static void main (String[] args) { // Given array arr[] int arr[] = { 5, 20, 30, 40, 36, 33, 25, 15, 10 }; int n = arr.length; // Function call sortArr(arr, n); }}// This code is contributed by offbeat |
Python3
# Python3 program for the# above approachimport math# Function to sort bitonic# array in constant spacedef sortArr(a, n): # Initialize thevalue of k k = int(math.log(n, 2)) k = int(pow(2, k)) # In each iteration compare elements # k distance apart and swap it # they are not in order while(k > 0): i = 0 while i + k < n: if a[i] > a[i + k]: a[i], a[i + k] = a[i + k], a[i] i = i + 1 # k is reduced to half after # every iteration k = k // 2 # Print the array elements for i in range(n): print(a[i], end = " ")# Driver code# Given arraya = [ 5, 20, 30, 40, 36, 33, 25, 15, 10 ]n = len(a)# Function callsortArr(a, n)# This code is contributed by virusbuddah_ |
C#
// C# program for the above approach using System;class GFG{ // Function to Sort a Bitonic array // in constant space static void sortArr(int []a, int n) { int i, k; // Initialize the value of k k = (int)(Math.Log(n) / Math.Log(2)); k = (int) Math.Pow(2, k); // In each iteration compare elements // k distance apart and swap if // they are not in order while (k > 0) { for(i = 0; i + k < n; i++) if (a[i] > a[i + k]) { int tmp = a[i]; a[i] = a[i + k]; a[i + k] = tmp; } // k is reduced to half // after every iteration k = k / 2; } // Print the array elements for(i = 0; i < n; i++) { Console.Write(a[i] + " "); } } // Driver codepublic static void Main(String[] args) { // Given array []arr int []arr = { 5, 20, 30, 40, 36, 33, 25, 15, 10 }; int n = arr.Length; // Function call sortArr(arr, n); }}// This code is contributed by amal kumar choubey |
Javascript
<script>// Java script program for the above approach // Function to Sort a Bitonic array// in constant spacefunction sortArr(a,n){ let i, k; // Initialize the value of k k = parseInt(Math.log(n) / Math.log(2)); k = parseInt( Math.pow(2, k)); // In each iteration compare elements // k distance apart and swap if // they are not in order while (k > 0) { for(i = 0; i + k < n; i++) if (a[i] > a[i + k]) { let tmp = a[i]; a[i] = a[i + k]; a[i + k] = tmp; } // k is reduced to half // after every iteration k = k / 2; } // Print the array elements for(i = 0; i < n; i++) { document.write(a[i] + " "); }} // Driver code // Given array arr[] let arr = [ 5, 20, 30, 40, 36, 33, 25, 15, 10 ]; let n = arr.length; // Function call sortArr(arr, n);// This code is contributed by sravan kumar </script> |
Output
5 10 15 20 25 30 33 36 40
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Efficient Approach : Using Binary search and Merge function of Merge sort.
- Find peak element index using binary search in given array.
- Divide the array into two parts first from index 0 to peak and second from index peak+1 to N-1
and traverse both the arrays in ascending order and do the following operations until any of the
arrays is exhausted :
(i) If element of first array is less than element of second array then store it into a tmp array
and increase the indexes of both the arrays (tmp and first).
(ii) Else store the element of second array into tmp array and increase the indexes of both
the arrays (tmp and second). - Check both the arrays and the array which is not fully traversed, store the remaining elements into
tmp array. - Copy all the elements of tmp array back in original array.
Below is the implementation of the above approach :
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std; // Function to Sort a Bitonic arrayvoid sortArr(vector<int>&arr,int n){ // Auxiliary array to store the sorted elements vector<int>tmp(n, 0); // Index of peak element in the bitonic array int peak = -1; int low = 0; int high = n - 1; int k = 0; // Modified Binary search to find the index of peak element while (low <= high){ int mid = (low + high) / 2; // Condition for checking element at index mid is peak element or not if (( mid == 0 || arr[mid - 1] < arr[mid] ) && ( mid == n - 1 || arr[mid + 1] < arr[mid] )){ peak = mid; break; } // If elements before mid element // are in increasing order it means // peak is present after the mid index if (arr[mid] < arr[mid + 1]) low = mid + 1; // If elements after mid element // are in decreasing order it means // peak is present before the mid index else high = mid - 1; } // Merging both the sorted arrays present // before after the peak element low = 0; high = n - 1; // Loop until any of both arrays is exhausted while (low <= peak && high > peak){ // Storing less value element in tmp array if (arr[low] < arr[high]){ tmp[k++] = arr[low++]; } else{ tmp[k++] = arr[high--]; } } // Storing remaining elements of array which is // present before peak element in tmp array while (low <= peak){ tmp[k++] = arr[low++]; } // Storing remaining elements of array which is // present after peak element in tmp array while (high > peak){ tmp[k++] = arr[high++]; } // Storing all elements of tmp array back in // original array for(int i = 0; i < n; i++) arr[i] = tmp[i];} // Driver code // Given array arr[]int main(){vector<int>arr = { 5, 20, 30, 40, 36, 33, 25, 15, 10 };int n = arr.size();// Function callsortArr(arr, n);for(auto x : arr) cout<<x<<" ";}// This code is contributed by shinjanpatra |
Java
// Java program for the above approach import java.util.*;public class GFG { // Function to Sort a Bitonic array static void sortArr(int arr[], int n) { // Auxiliary array to store the sorted elements int tmp[] = new int[n]; // Index of peak element in the bitonic array int peak = -1, low = 0, high = n-1, k=0; // Modified Binary search to find the index of peak element while (low <= high){ int mid = (low + high) / 2; // Condition for checking element at index mid is peak element or not if (( mid == 0 || arr[mid - 1] < arr[mid] ) && ( mid == n - 1 || arr[mid + 1] < arr[mid] )) { peak = mid; break; } // If elements before mid element // are in increasing order it means // peak is present after the mid index if (arr[mid] < arr[mid + 1]) low = mid + 1; // If elements after mid element // are in decreasing order it means // peak is present before the mid index else high = mid - 1; } // Merging both the sorted arrays present // before after the peak element low = 0; high = n - 1; // Loop until any of both arrays is exhausted while (low <= peak && high > peak){ // Storing less value element in tmp array if (arr[low] < arr[high]) tmp[k++] = arr[low++]; else tmp[k++] = arr[high--]; } // Storing remaining elements of array which is // present before peak element in tmp array while (low <= peak) tmp[k++] = arr[low++]; // Storing remaining elements of array which is // present after peak element in tmp array while (high > peak) tmp[k++] = arr[high--]; // Storing all elements of tmp array back in // original array for (int i = 0; i < n; i++) arr[i] = tmp[i]; } // Driver code public static void main(String[] args) { // Given array arr[] int arr[] = { 5, 20, 30, 40, 36, 33, 25, 15, 10 }; int n = arr.length; // Function call sortArr(arr, n); for (int x : arr) System.out.print(x + " "); }} |
Python3
# Python program for the above approach # Function to Sort a Bitonic arraydef sortArr(arr, n): # Auxiliary array to store the sorted elements tmp = [0 for i in range(n)] # Index of peak element in the bitonic array peak, low, high, k = -1, 0, n - 1, 0 # Modified Binary search to find the index of peak element while (low <= high): mid = (low + high) // 2 # Condition for checking element at index mid is peak element or not if (( mid == 0 or arr[mid - 1] < arr[mid] ) and ( mid == n - 1 or arr[mid + 1] < arr[mid] )): peak = mid break # If elements before mid element # are in increasing order it means # peak is present after the mid index if (arr[mid] < arr[mid + 1]): low = mid + 1 # If elements after mid element # are in decreasing order it means # peak is present before the mid index else: high = mid - 1 # Merging both the sorted arrays present # before after the peak element low,high = 0,n - 1 # Loop until any of both arrays is exhausted while (low <= peak and high > peak): # Storing less value element in tmp array if (arr[low] < arr[high]): tmp[k] = arr[low] k += 1 low += 1 else: tmp[k] = arr[high] k += 1 high -= 1 # Storing remaining elements of array which is # present before peak element in tmp array while (low <= peak): tmp[k] = arr[low] k += 1 low += 1 # Storing remaining elements of array which is # present after peak element in tmp array while (high > peak): tmp[k] = arr[high] k += 1 high -= 1 # Storing all elements of tmp array back in # original array for i in range(n): arr[i] = tmp[i] # Driver code # Given array arr[]arr = [ 5, 20, 30, 40, 36, 33, 25, 15, 10 ]n = len(arr)# Function callsortArr(arr, n)for x in arr: print(x ,end = " ")# This code is contributed by shinjanpatra |
Javascript
<script>// JavaScript program for the above approach // Function to Sort a Bitonic arrayfunction sortArr(arr, n){ // Auxiliary array to store the sorted elements let tmp = new Array(n).fill(0) // Index of peak element in the bitonic array let peak = -1 let low = 0 let high = n - 1 let k = 0 // Modified Binary search to find the index of peak element while (low <= high){ let mid = Math.floor((low + high) / 2) // Condition for checking element at index mid is peak element or not if (( mid == 0 || arr[mid - 1] < arr[mid] ) && ( mid == n - 1 || arr[mid + 1] < arr[mid] )){ peak = mid break } // If elements before mid element // are in increasing order it means // peak is present after the mid index if (arr[mid] < arr[mid + 1]) low = mid + 1 // If elements after mid element // are in decreasing order it means // peak is present before the mid index else high = mid - 1 } // Merging both the sorted arrays present // before after the peak element low = 0 high = n - 1 // Loop until any of both arrays is exhausted while (low <= peak && high > peak){ // Storing less value element in tmp array if (arr[low] < arr[high]){ tmp[k++] = arr[low++] } else{ tmp[k++] = arr[high--] } } // Storing remaining elements of array which is // present before peak element in tmp array while (low <= peak){ tmp[k++] = arr[low++] } // Storing remaining elements of array which is // present after peak element in tmp array while (high > peak){ tmp[k++] = arr[high++] } // Storing all elements of tmp array back in // original array for(let i = 0; i < n; i++) arr[i] = tmp[i]} // Driver code // Given array arr[]let arr = [ 5, 20, 30, 40, 36, 33, 25, 15, 10 ]let n = arr.length// Function callsortArr(arr, n)for(let x of arr) document.write(x ," ")// This code is contributed by shinjanpatra</script> |
C#
// C# program for the above approach // Include namespace systemusing System;public class GFG{ // Function to Sort a Bitonic array public static void sortArr(int[] arr, int n) { // Auxiliary array to store the sorted elements int[] tmp = new int[n]; // Index of peak element in the bitonic array var peak = -1; var low = 0; var high = n - 1; var k = 0; // Modified Binary search to find the index of peak element while (low <= high) { var mid = (int)((low + high) / 2); // Condition for checking element at index mid is peak element or not if ((mid == 0 || arr[mid - 1] < arr[mid]) && (mid == n - 1 || arr[mid + 1] < arr[mid])) { peak = mid; break; } // If elements before mid element // are in increasing order it means // peak is present after the mid index if (arr[mid] < arr[mid + 1]) { low = mid + 1; } else { high = mid - 1; } } // Merging both the sorted arrays present // before after the peak element low = 0; high = n - 1; // Loop until any of both arrays is exhausted while (low <= peak && high > peak) { // Storing less value element in tmp array if (arr[low] < arr[high]) { tmp[k++] = arr[low++]; } else { tmp[k++] = arr[high--]; } } // Storing remaining elements of array which is // present before peak element in tmp array while (low <= peak) {tmp[k++] = arr[low++]; } // Storing remaining elements of array which is // present after peak element in tmp array while (high > peak) {tmp[k++] = arr[high--]; } // Storing all elements of tmp array back in // original array for (int i = 0; i < n; i++) { arr[i] = tmp[i]; } } // Driver code public static void Main(String[] args) { // Given array arr[] int[] arr = {5, 20, 30, 40, 36, 33, 25, 15, 10}; var n = arr.Length; // Function call sortArr(arr, n); foreach (int x in arr) { Console.Write(x.ToString() + " "); } }} |
Output
5 10 15 20 25 30 33 36 40
Time Complexity : O(N)
Auxiliary Space : O(N) (can be done in O(1) also)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
