Ordenar una array de 0s, 1s, 2s y 3s

Dada una array arr[] de tamaño N que consta de 0 , 1 , 2 y 3 solamente, la tarea es ordenar la array dada en orden ascendente .

Ejemplo: 

Entrada: arr[] = {0, 3, 1, 2, 0, 3, 1, 2}
Salida: 0 0 1 1 2 2 3 3

Entrada: arr[] = {0, 1, 3, 1, 0, 1, 3, 2, 1, 2, 0, 3, 0, 0, 1}
Salida: 0 0 0 0 0 1 1 1 1 1 2 2 3 3 3

 

Enfoque: el problema dado se puede resolver según el enfoque discutido en este artículo . La idea es primero colocar todos los 0 y 3 al principio y al final de la array, y luego ordenar las ocurrencias de los números enteros 1 y 2

Siga los pasos a continuación para resolver el problema:

  • Inicialice tres variables, digamos i , mid y j . Establezca los valores de i y mid como 0 y j como (N – 1) .
  • Iterar un ciclo hasta mid ≤ j y realizar los siguientes pasos:
    • Si el valor de arr[mid] es 0 , entonces intercambie arr[i] y arr[mid] e incremente el valor de i y mid en 1 .
    • De lo contrario, si el valor de arr[mid] es 3 , entonces intercambie arr[mid] y arr[j] y reduzca j en 1 .
    • De lo contrario, si el valor de arr[i] es 1 o 2 , incremente el valor de mid en 1 .
  • Ahora, para ordenar el subarreglo sobre el rango [i, j] iterando hasta que i ≤ j y realice las siguientes operaciones:
    • Si el valor de arr[i] es 2 , entonces intercambie arr[i] y arr[j] y reduzca el valor de j en 1 .
    • De lo contrario, incrementa el valor de i en 1 .
  • Después de completar los pasos anteriores, imprima la array arr[] como la array ordenada resultante.

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 the array having
// array element only 0, 1, 2, and 3
void sortArray(int arr[], int N)
{
    int i = 0, j = N - 1, mid = 0;
 
    // Iterate until mid <= j
    while (mid <= j) {
 
        // If arr[mid] is 0
        if (arr[mid] == 0) {
 
            // Swap integers at
            // indices i and mid
            swap(arr[i], arr[mid]);
 
            // Increment i
            i++;
 
            // Increment mid
            mid++;
        }
 
        // Otherwise if the value of
        // arr[mid] is 3
        else if (arr[mid] == 3) {
 
            // Swap arr[mid] and arr[j]
            swap(arr[mid], arr[j]);
 
            // Decrement j
            j--;
        }
 
        // Otherwise if the value of
        // arr[mid] is either 1 or 2
        else if (arr[mid] == 1
                 || arr[mid] == 2) {
 
            // Increment the value of mid
            mid++;
        }
    }
 
    // Iterate until i <= j
    while (i <= j) {
 
        // If arr[i] the value of is 2
        if (arr[i] == 2) {
 
            // Swap arr[i] and arr[j]
            swap(arr[i], arr[j]);
 
            // Decrement j
            j--;
        }
 
        // Otherwise, increment i
        else {
            i++;
        }
    }
 
    // Print the sorted array arr[]
    for (int i = 0; i < N; i++) {
        cout << arr[i] << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 2, 1, 0, 2, 3, 1, 0 };
    int N = sizeof(arr) / sizeof(arr[0]);
    sortArray(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Function to sort the array having
// array element only 0, 1, 2, and 3
static void sortArray(int[] arr, int N)
{
    int i = 0, j = N - 1, mid = 0;
 
    // Iterate until mid <= j
    while (mid <= j)
    {
         
        // If arr[mid] is 0
        if (arr[mid] == 0)
        {
             
            // Swap integers at
            // indices i and mid
            int temp = arr[i];
            arr[i] = arr[mid];
            arr[mid] = temp;
 
            // Increment i
            i++;
 
            // Increment mid
            mid++;
        }
 
        // Otherwise if the value of
        // arr[mid] is 3
        else if (arr[mid] == 3)
        {
             
            // Swap arr[mid] and arr[j]
            int temp = arr[mid];
            arr[mid] = arr[j];
            arr[j] = temp;
 
            // Decrement j
            j--;
        }
 
        // Otherwise if the value of
        // arr[mid] is either 1 or 2
        else if (arr[mid] == 1 || arr[mid] == 2)
        {
             
            // Increment the value of mid
            mid++;
        }
    }
 
    // Iterate until i <= j
    while (i <= j)
    {
         
        // If arr[i] the value of is 2
        if (arr[i] == 2)
        {
             
            // Swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
 
            // Decrement j
            j--;
        }
 
        // Otherwise, increment i
        else
        {
            i++;
        }
    }
 
    // Print the sorted array arr[]
    for(int k = 0; k < N; k++)
    {
        System.out.print(arr[k] + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int[] arr = { 3, 2, 1, 0, 2, 3, 1, 0 };
    int N = arr.length;
     
    sortArray(arr, N);
}
}
 
// This code is contributed by susmitakundugoaldanga

Python3

# Python3 program for the above approach
 
# Function to sort the array having
# array element only 0, 1, 2, and 3
def sortArray(arr, N):
    i = 0
    j = N - 1
    mid = 0
 
    # Iterate until mid <= j
    while (mid <= j):
 
        # If arr[mid] is 0
        if (arr[mid] == 0):
 
            # Swap integers at
            # indices i and mid
            arr[i], arr[mid] = arr[mid], arr[i]
 
            # Increment i
            i += 1
             
            # Increment mid
            mid += 1
 
        # Otherwise if the value of
        # arr[mid] is 3
        elif (arr[mid] == 3):
 
            # Swap arr[mid] and arr[j]
            arr[mid], arr[j] = arr[j], arr[mid]
             
            # Decrement j
            j -= 1
 
        # Otherwise if the value of
        # arr[mid] is either 1 or 2
        elif (arr[mid] == 1 or arr[mid] == 2):
            # Increment the value of mid
            mid += 1
 
    # Iterate until i <= j
    while (i <= j):
       
        # If arr[i] the value of is 2
        if (arr[i] == 2):
           
            # Swap arr[i] and arr[j]
            arr[i], arr[j] = arr[j], arr[i]
             
            # Decrement j
            j -= 1
 
        # Otherwise, increment i
        else:
            i += 1
 
    # Print the sorted array arr[]
    for i in range(N):
        print(arr[i], end = " ")
 
# Driver Code
if __name__ == '__main__':
    arr = [3, 2, 1, 0, 2, 3, 1, 0]
    N = len(arr)
    sortArray(arr, N)
 
#  This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to sort the array having
// array element only 0, 1, 2, and 3
static void sortArray(int[] arr, int N)
{
    int i = 0, j = N - 1, mid = 0;
 
    // Iterate until mid <= j
    while (mid <= j)
    {
         
        // If arr[mid] is 0
        if (arr[mid] == 0)
        {
             
            // Swap integers at
            // indices i and mid
            int temp = arr[i];
            arr[i] = arr[mid];
            arr[mid] = temp;
 
            // Increment i
            i++;
 
            // Increment mid
            mid++;
        }
 
        // Otherwise if the value of
        // arr[mid] is 3
        else if (arr[mid] == 3)
        {
             
            // Swap arr[mid] and arr[j]
            int temp = arr[mid];
            arr[mid] = arr[j];
            arr[j] = temp;
 
            // Decrement j
            j--;
        }
 
        // Otherwise if the value of
        // arr[mid] is either 1 or 2
        else if (arr[mid] == 1 || arr[mid] == 2)
        {
             
            // Increment the value of mid
            mid++;
        }
    }
 
    // Iterate until i <= j
    while (i <= j)
    {
         
        // If arr[i] the value of is 2
        if (arr[i] == 2)
        {
             
            // Swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
 
            // Decrement j
            j--;
        }
 
        // Otherwise, increment i
        else
        {
            i++;
        }
    }
 
    // Print the sorted array arr[]
    for(int k = 0; k < N; k++)
    {
        Console.Write(arr[k] + " ");
    }
}
 
// Driver Code
public static void Main()
{
    int[] arr = { 3, 2, 1, 0, 2, 3, 1, 0 };
    int N = arr.Length;
     
    sortArray(arr, N);
}
}
 
// This code is contributed by ukasp

Javascript

<script>
 
// javascript program for the above approach
 
// Function to sort the array having
// array element only 0, 1, 2, and 3
function sortArray(arr, N)
{
    var i = 0, j = N - 1, mid = 0;
 
    // Iterate until mid <= j
    while (mid <= j) {
 
        // If arr[mid] is 0
        if (arr[mid] == 0) {
 
            // Swap integers at
            // indices i and mid
            var temp = arr[i];
            arr[i] = arr[mid];
            arr[mid] = temp;
 
            // Increment i
            i++;
 
            // Increment mid
            mid++;
        }
 
        // Otherwise if the value of
        // arr[mid] is 3
        else if (arr[mid] == 3) {
             
            var temp = arr[mid];
            arr[mid] = arr[j];
            arr[j] = temp;
 
            // Decrement j
            j--;
        }
 
        // Otherwise if the value of
        // arr[mid] is either 1 or 2
        else if (arr[mid] == 1
                 || arr[mid] == 2) {
 
            // Increment the value of mid
            mid++;
        }
    }
 
    // Iterate until i <= j
    while (i <= j) {
 
        // If arr[i] the value of is 2
        if (arr[i] == 2) {
 
            // Swap arr[i] and arr[j]
            var temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
 
            // Decrement j
            j--;
        }
 
        // Otherwise, increment i
        else {
            i++;
        }
    }
 
    // Print the sorted array arr[]
    for (i = 0; i < N; i++) {
        document.write(arr[i] + " ");
    }
}
 
// Driver Code
    var arr = [3, 2, 1, 0, 2, 3, 1, 0];
    var N = arr.length;
    sortArray(arr, N);
     
</script>
Producción: 

0 0 1 1 2 2 3 3

 

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

Publicación traducida automáticamente

Artículo escrito por maddler y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *