Ordenar una array bitónica

Dada una array bitónica arr[], la tarea es ordenar la array bitónica dada. 
 

Una secuencia bitónica es una secuencia de números que primero es estrictamente creciente y luego después de un punto estrictamente decreciente.

Ejemplos: 
 

Entrada: arr[] = {5, 10, 15, 25, 20, 3, 2, 1} 
Salida: 1 2 3 5 10 15 20 25
Entrada: arr[] = {5, 20, 30, 40, 36, 33, 25, 15, 10} 
Salida: 5 10 15 20 25 30 33 36 40

Acercarse: 
 

• La idea es inicializar una variable K a la potencia más alta de 2 en el tamaño de la array para comparar elementos que están K distantes entre sí.
• Intercambia los elementos si no están en orden creciente.
• Reduzca K a la mitad y repita el proceso hasta que K sea cero.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to Sort a Bitonic array
// in constant space
void 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 Code
int 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 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 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);
}
}
 
// This code is contributed by offbeat

# Python3 program for the
# above approach
import math
 
# Function to sort bitonic
# array in constant space
def 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 array
a = [ 5, 20, 30, 40, 36, 33, 25, 15, 10 ]
n = len(a)
 
# Function call
sortArr(a, n)
 
# This code is contributed by virusbuddah_

// 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 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);
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
// Java script program for the above approach
     
// Function to Sort a Bitonic array
// in constant space
function 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>

5 10 15 20 25 30 33 36 40 

Complejidad de tiempo: O(N*log N)  
Espacio auxiliar: O(1)
 

Enfoque eficiente: uso de la función de búsqueda binaria y combinación de clasificación de combinación.

1. Encuentre el índice de elementos máximos mediante la búsqueda binaria en una array dada.
2. Divida la array en dos partes, primero desde el índice 0 hasta el pico y la segunda desde el índice pico+1 hasta N-1
   y recorra ambas arrays en orden ascendente y realice las siguientes operaciones hasta que
   se agote cualquiera de las arrays:
                 (i) Si el elemento de la primera array es menor que el elemento de la segunda array, luego guárdela en una array tmp
                      y aumente los índices de ambas arrays (tmp y primera).
                 (ii) De lo contrario, almacene el elemento de la segunda array en la array tmp y aumente los índices de ambas
                      arrays (tmp y segunda).
3. Verifique tanto las arrays como la array que no está completamente recorrida, almacene los elementos restantes en la
   array tmp.
4. Copie todos los elementos de la array tmp nuevamente en la array original.

 
A continuación se muestra la implementación del enfoque anterior :

// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
     
// Function to Sort a Bitonic array
void 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 call
sortArr(arr, n);
 
for(auto x : arr)
    cout<<x<<" ";
 
}
 
// This code is contributed by shinjanpatra

// 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 + " ");
    }
}

# Python program for the above approach
     
# Function to Sort a Bitonic array
def 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 call
sortArr(arr, n)
 
for x in arr:
    print(x ,end = " ")
 
# This code is contributed by shinjanpatra

<script>
 
// JavaScript program for the above approach
     
// Function to Sort a Bitonic array
function 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 call
sortArr(arr, n)
 
for(let x of arr)
    document.write(x ," ")
 
// This code is contributed by shinjanpatra
 
</script>

5 10 15 20 25 30 33 36 40 

Complejidad de tiempo: O(N)
Espacio auxiliar: O(N) (también se puede hacer en O(1))