Nos dan una array. Necesitamos ordenar los elementos de posición par en orden ascendente y los elementos de posición impar en orden descendente. Debemos aplicar la ordenación por inserción para ordenarlos.
Ejemplos:
Input : a[] = {7, 10, 11, 3, 6, 9, 2, 13, 0}
Output : 11 3 7 9 6 10 2 13 0
Even positioned elements after sorting int
ascending order : 3 9 10 13
Odd positioned elements after sorting int
descending order : 11 7 6 2 0
Aplicamos por separado la técnica de clasificación por inserción en los elementos de posición par y los elementos de posición impar por separado pero dentro de la misma array. El ciclo comienza para el impar posicionado desde el índice 0 (1er elemento) y para el par desde el 1er índice (2do elemento) y continúa aumentando en 2 ya que cada alternativa es impar/par posicionada.
Ahora simplemente aplicamos el procedimiento de clasificación por inserción en las posiciones pares e impares. los elementos impares son A[0, 2, 4,…] y los pares son A[1, 3, 5, 7..]. Por lo tanto, se consideran subarrays separadas pero dentro de la misma array.
Explicación para la posición impar:
El elemento 0 ya está ordenado. Ahora el 2º elemento comparado con el 0º e insertado y así sucesivamente el (i+2)º elemento comparado con los anteriores hasta el final de la array. Se aplica el mismo enfoque para los elementos de posición uniforme en
la array (esto es lo mismo que la técnica de clasificación por inserción).
C++
// C++ program to sort even positioned elements
// in ascending order and odd positioned
// elements in descending order.
#include<stdio.h>
#include<stdlib.h>
// Function to calculate the given problem.
void evenOddInsertionSort(int arr[], int n)
{
for (int i = 2; i < n; i++)
{
int j = i-2;
int temp = arr[i];
/* checking whether the position is even
or odd. And after checking applying the
insertion sort to the given
positioned elements.*/
// checking for odd positioned.
if ((i+1) & 1 == 1)
{
// Inserting even positioned elements
// in ascending order.
while (temp >= arr[j] && j >= 0)
{
arr[j+2] = arr[j];
j -= 2;
}
arr[j+2] = temp;
}
// sorting the even positioned.
else {
// Inserting odd positioned elements
// in descending order.
while (temp <= arr[j] && j >= 0)
{
arr[j+2] = arr[j];
j -= 2;
}
arr[j+2] = temp;
}
}
}
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
for (int i=0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
/* Driver program to test insertion sort */
int main()
{
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
evenOddInsertionSort(arr, n);
printArray(arr, n);
return 0;
}
Java
// Java program to sort even positioned elements
// in ascending order and odd positioned
// elements in descending order.
class GFG
{
// Function to calculate the given problem.
static void evenOddInsertionSort(int arr[], int n)
{
for (int i = 2; i < n; i++)
{
int j = i - 2;
int temp = arr[i];
/* checking whether the position is even
or odd. And after checking applying the
insertion sort to the given
positioned elements.*/
// checking for odd positioned.
if (((i + 1) & 1) == 1)
{
// Inserting even positioned elements
// in ascending order.
while (j >= 0 && temp >= arr[j])
{
arr[j + 2] = arr[j];
j -= 2;
}
arr[j + 2] = temp;
}
// sorting the even positioned.
else
{
// Inserting odd positioned elements
// in descending order.
while (j >= 0 && temp <= arr[j])
{
arr[j + 2] = arr[j];
j -= 2;
}
arr[j + 2] = temp;
}
}
}
// A utility function to print an array of size n
static void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
{
System.out.printf("%d ", arr[i]);
}
System.out.printf("\n");
}
/* Driver program to test insertion sort */
public static void main(String[] args)
{
int arr[] = {12, 11, 13, 5, 6};
int n = arr.length;
evenOddInsertionSort(arr, n);
printArray(arr, n);
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 program to sort even # positioned elements in ascending # order and odd positionedelements # in descending order. # Function to calculate # the given problem. def evenOddInsertionSort(arr, n): for i in range(2, n): j = i - 2 temp = arr[i] # checking whether the position # is even or odd. And after # checking applying the insertion # sort to the given # positioned elements. # checking for odd positioned. if ((i + 1) & 1 == 1) : # Inserting even positioned elements # in ascending order. while (temp >= arr[j] and j >= 0): arr[j + 2] = arr[j] j -= 2 arr[j + 2] = temp # sorting the even positioned. else : # Inserting odd positioned elements # in descending order. while (temp <= arr[j] and j >= 0) : arr[j + 2] = arr[j] j -= 2 arr[j + 2] = temp # A utility function to print an array of size n def printArray(arr, n): for i in range(0, n): print(arr[i], end=" ") # Driver program arr = [12, 11, 13, 5, 6] n = len(arr) evenOddInsertionSort(arr, n) printArray(arr, n) # This code is contributed by # Smitha Dinesh Semwal
C#
// C# program to sort even positioned elements
// in ascending order and odd positioned
// elements in descending order.
using System;
class GFG
{
// Function to calculate the given problem.
static void evenOddInsertionSort(int []arr, int n)
{
for (int i = 2; i < n; i++)
{
int j = i - 2;
int temp = arr[i];
/* checking whether the position is even
or odd. And after checking applying the
insertion sort to the given
positioned elements.*/
// checking for odd positioned.
if (((i + 1) & 1) == 1)
{
// Inserting even positioned elements
// in ascending order.
while (j >= 0 && temp >= arr[j])
{
arr[j + 2] = arr[j];
j -= 2;
}
arr[j + 2] = temp;
}
// sorting the even positioned.
else
{
// Inserting odd positioned elements
// in descending order.
while (j >= 0 && temp <= arr[j])
{
arr[j + 2] = arr[j];
j -= 2;
}
arr[j + 2] = temp;
}
}
}
// A utility function to print an array of size n
static void printArray(int []arr, int n)
{
for (int i = 0; i < n; i++)
{
Console.Write("{0} ", arr[i]);
}
Console.Write("\n");
}
/* Driver code */
public static void Main(String[] args)
{
int []arr = {12, 11, 13, 5, 6};
int n = arr.Length;
evenOddInsertionSort(arr, n);
printArray(arr, n);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to sort even positioned elements
// in ascending order and odd positioned
// elements in descending order.
// Function to calculate the given problem.
function evenOddInsertionSort(arr, n)
{
for (let i = 2; i < n; i++)
{
let j = i - 2;
let temp = arr[i];
/* checking whether the position is even
or odd. And after checking applying the
insertion sort to the given
positioned elements.*/
// checking for odd positioned.
if (((i + 1) & 1) == 1)
{
// Inserting even positioned elements
// in ascending order.
while (j >= 0 && temp >= arr[j])
{
arr[j + 2] = arr[j];
j -= 2;
}
arr[j + 2] = temp;
}
// sorting the even positioned.
else
{
// Inserting odd positioned elements
// in descending order.
while (j >= 0 && temp <= arr[j])
{
arr[j + 2] = arr[j];
j -= 2;
}
arr[j + 2] = temp;
}
}
}
// A utility function to print an array of size n
function printArray(arr, n)
{
for (let i = 0; i < n; i++)
{
document.write(arr[i] + " ");
}
document.write();
}
// Driver code
let arr = [12, 11, 13, 5, 6];
let n = arr.length;
evenOddInsertionSort(arr, n);
printArray(arr, n);
</script>
Producción:
13 5 12 11 6
Complejidad temporal: O(n 2 )
Espacio auxiliar: O(1)
Existen mejores enfoques para resolver este problema sin ordenar por inserción. Consulte Clasificar elementos pares en orden creciente e impar en orden decreciente para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por UtkrishtPatesaria y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA