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++
// 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
// 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
# 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#
// 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
Javascript
<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.
- Encuentre el índice de elementos máximos mediante la búsqueda binaria en una array dada.
- 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). - Verifique tanto las arrays como la array que no está completamente recorrida, almacene los elementos restantes en la
array tmp. - 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++
// 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
// 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 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
Javascript
<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))
Publicación traducida automáticamente
Artículo escrito por sasidharreddy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA