Eliminar elementos para ordenar la array

Dada una array de enteros, la tarea es eliminar elementos de la array para ordenar la array. Es decir, eliminar los elementos que no siguen un orden creciente.

Ejemplos:  

Entrada: arr[] = {1, 2, 4, 3, 5, 7, 8, 6, 9, 10} 
Salida: 1 2 4 5 7 8 9 10

Entrada: arr[] = {10, 12, 9, 5, 2, 13, 14} 
Salida: 10 12 13 14  

Enfoque: recorra la array dada y para cada elemento que sea mayor o igual que el elemento tomado anteriormente, agregue este elemento a otra array; de lo contrario, salte al siguiente elemento. Al final, la array recién creada se ordenará de acuerdo con la clasificación de Stalin. 

1. Para cada elemento, compruebe si el elemento es mayor que el elemento anterior o no. 
   • En caso afirmativo, compruebe el siguiente elemento.
   • De lo contrario, elimine ese elemento.
2. Después de que todos los elementos hayan sido recorridos, obtendremos una array ordenada.

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

// C++ implementation of the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to sort the array
// by removing misplaced elements
void removeElements(int arr[], int n)
{
 
    // brr[] is used to store
    // the sorted array elements
    int brr[n], l = 1;
 
    brr[0] = arr[0];
    for (int i = 1; i < n; i++) {
        if (brr[l - 1] <= arr[i]) {
            brr[l] = arr[i];
            l++;
        }
    }
 
    // Print the sorted array
    for (int i = 0; i < l; i++)
        cout << brr[i] << " ";
}
 
// Driver code
int main()
{
    int arr[] = { 10, 12, 9, 10, 2, 13, 14 };
    int n = sizeof(arr) / sizeof(arr[0]);
    removeElements(arr, n);
 
    return 0;
}

// Java implementation of the approach
 
class GFG
{
     
// Function to sort the array
// by removing misplaced elements
static void removeElements(int []arr, int n)
{
 
    // brr[] is used to store
    // the sorted array elements
    int []brr = new int[n];
    int l = 1;
 
    brr[0] = arr[0];
    for (int i = 1; i < n; i++)
    {
        if (brr[l - 1] <= arr[i])
        {
            brr[l] = arr[i];
            l++;
        }
    }
 
    // Print the sorted array
    for (int i = 0; i < l; i++)
        System.out.print(brr[i] + " ");
}
 
// Driver code
static public void main (String[] args)
{
    int []arr = { 10, 12, 9, 10, 2, 13, 14 };
    int n = arr.length;
    removeElements(arr, n);
}
}
 
// This code is contributed by Code_Mech.

# Python3 implementation of the approach
 
# Function to sort the array
# by removing misplaced elements
def removeElements(arr,  n) :
 
    # brr[] is used to store
    # the sorted array elements
    brr = [0]*n; l = 1;
 
    brr[0] = arr[0];
    for i in range(1,n) :
        if (brr[l - 1] <= arr[i]) :
            brr[l] = arr[i];
            l += 1;
 
    # Print the sorted array
    for i in range(l) :
        print(brr[i],end=" ");
 
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 10, 12, 9, 10, 2, 13, 14 ];
    n = len(arr);
    removeElements(arr, n);
 
    # This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function to sort the array
// by removing misplaced elements
static void removeElements(int []arr, int n)
{
 
    // brr[] is used to store
    // the sorted array elements
    int []brr = new int[n];
    int l = 1;
 
    brr[0] = arr[0];
    for (int i = 1; i < n; i++)
    {
        if (brr[l - 1] <= arr[i])
        {
            brr[l] = arr[i];
            l++;
        }
    }
 
    // Print the sorted array
    for (int i = 0; i < l; i++)
        Console.Write(brr[i] + " ");
}
 
// Driver code
static public void Main ()
{
    int []arr = { 10, 12, 9, 10, 2, 13, 14 };
    int n = arr.Length;
    removeElements(arr, n);
}
}
 
// This code is contributed by jit_t

<script>
    // Javascript implementation of the approach
     
    // Function to sort the array
    // by removing misplaced elements
    function removeElements(arr, n)
    {
 
        // brr[] is used to store
        // the sorted array elements
        let brr = new Array(n);
        brr.fill(0);
        let l = 1;
 
        brr[0] = arr[0];
        for (let i = 1; i < n; i++)
        {
            if (brr[l - 1] <= arr[i])
            {
                brr[l] = arr[i];
                l++;
            }
        }
 
        // Print the sorted array
        for (let i = 0; i < l; i++)
            document.write(brr[i] + " ");
    }
     
    let arr = [ 10, 12, 9, 10, 2, 13, 14 ];
    let n = arr.length;
    removeElements(arr, n);
 
</script>

10 12 13 14

Complejidad temporal: O(n)
Espacio auxiliar: O(n)
 

Método 2: en lugar de usar una array adicional, guárdelos en la misma array  

// C++ implementation of the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to sort the array
// by removing misplaced elements
void removeElements(int arr[], int n)
{
 
    // l stores the index
    int l = 1;
    for (int i = 1; i < n; i++) {
        if (arr[l - 1] <= arr[i]) {
            arr[l] = arr[i];
            l++;
        }
    }
 
    // Print the sorted array
    for (int i = 0; i < l; i++)
        cout << arr[i] << " ";
}
 
// Driver code
int main()
{
    int arr[] = { 10, 12, 9, 10, 2, 13, 14 };
    int n = sizeof(arr) / sizeof(arr[0]);
    removeElements(arr, n);
 
    return 0;
}

// Java implementation of the approach
class GFG{
 
// Function to sort the array
// by removing misplaced elements
static void removeElements(int arr[], int n)
{
     
    // l stores the index
    int l = 1;
    for(int i = 1; i < n; i++)
    {
        if (arr[l - 1] <= arr[i])
        {
            arr[l] = arr[i];
            l++;
        }
    }
 
    // Print the sorted array
    for(int i = 0; i < l; i++)
        System.out.print(arr[i] + " ");
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 10, 12, 9, 10, 2, 13, 14 };
    int n = arr.length;
     
    removeElements(arr, n);
}
}
 
// This code is contributed by shikhasingrajput

# Python3 implementation of the approach
 
# Function to sort the array
# by removing misplaced elements
def removeElements(arr, n):
     
    # l stores the index
    l = 1
    for i in range(1, n):
        if (arr[l - 1] <= arr[i]):
            arr[l] = arr[i]
            l += 1
         
    # Print the sorted array
    for i in range(l):
        print(arr[i], end = " ")
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 10, 12, 9, 10, 2, 13, 14 ]
    n = len(arr)
     
    removeElements(arr, n)
 
# This code is contributed by Surbhi Tyagi.

// C# implementation of the approach
using System;
 
class GFG{
 
// Function to sort the array
// by removing misplaced elements
public static void removeElements(int []arr, int n)
{
     
    // l stores the index
    int l = 1;
    for(int i = 1; i < n; i++)
    {
        if (arr[l - 1] <= arr[i])
        {
            arr[l] = arr[i];
            l++;
        }
    }
 
    // Print the sorted array
    for(int i = 0; i < l; i++)
        Console.Write( arr[i] + " ");
}
 
// Driver code
public static void Main(string []args)
{
    int []arr = { 10, 12, 9, 10, 2, 13, 14 };
    int n = arr.Length;
     
    removeElements(arr, n);
}
}
 
// This code is contributed by importantly

<script>
 
    // Javascript implementation of the approach
     
    // Function to sort the array
    // by removing misplaced elements
    function removeElements(arr, n)
    {
 
        // l stores the index
        let l = 1;
        for (let i = 1; i < n; i++) {
            if (arr[l - 1] <= arr[i]) {
                arr[l] = arr[i];
                l++;
            }
        }
 
        // Print the sorted array
        for (let i = 0; i < l; i++)
            document.write(arr[i] + " ");
    }
     
    let arr = [ 10, 12, 9, 10, 2, 13, 14 ];
    let n = arr.length;
    removeElements(arr, n);
 
</script>

10 12 13 14

Complejidad temporal: O(n)
Espacio auxiliar: O(1)