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 3Entrada: 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)