Ordenar una array binaria usando un recorrido

Dada una array binaria, ordénela usando un recorrido y sin espacio adicional.
Ejemplos: 
 

Input : 1 0 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 0 1 0 0 
Output : 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1
Explanation: The output is a sorted array of 0 and 1

Input : 1 0 1 0 1 0 1 0 
Output : 0 0 0 0 1 1 1 1
Explanation: The output is a sorted array of 0 and 1

Enfoque: Este concepto está relacionado con la partición de ordenación rápida . En la partición de clasificación rápida, después de un escaneo, la izquierda de la array es la más pequeña y la derecha de la array es el elemento pivote seleccionado más grande.
Algoritmo: 
 

1. Cree un índice variable, digamos j = -1
2. Atraviesa la array de principio a fin
3. Si el elemento es 0, intercambie el elemento actual con el elemento en la posición del índice ( j ^th ) e incremente el índice ( j) en 1.
4. Si el elemento es 1, mantenga el elemento como está.

Implementación: 
 

// CPP program to sort a binary array
#include <iostream>
using namespace std;
 
void sortBinaryArray(int a[], int n)
{
    int j = -1;
    for (int i = 0; i < n; i++) {
 
        // if number is smaller than 1
        // then swap it with j-th number
        if (a[i] < 1) {
            j++;
            swap(a[i], a[j]);
        }
    }
}
 
// Driver code
int main()
{
    int a[] = { 1, 0, 0, 1, 0, 1, 0, 1, 1, 1,
                1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0 };
    int n = sizeof(a) / sizeof(a[0]);
    sortBinaryArray(a, n);
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
 
    return 0;
}

// JAVA Code for Sort a binary
// array using one traversal
import java.util.*;
 
class GFG {
 
    static void sortBinaryArray(int a[], int n)
    {
        int j = -1;
        for (int i = 0; i < n; i++) {
 
            // if number is smaller than 1
            // then swap it with j-th number
            if (a[i] < 1) {
                j++;
                int temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
        }
    }
 
    /* Driver program to test above function */
    public static void main(String[] args)
    {
 
        int a[] = { 1, 0, 0, 1, 0, 1, 0, 1, 1, 1,
                    1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0 };
 
        int n = a.length;
 
        sortBinaryArray(a, n);
 
        for (int i = 0; i < n; i++)
            System.out.print(a[i] + " ");
    }
}

# A Python program to sort a
# binary array
def sortBinaryArray(a, n):
    j = -1
    for i in range(n):
 
        # if number is smaller
        # than 1 then swap it
        # with j-th number
        if a[i] < 1:
            j = j + 1
             
            # swap
            a[i], a[j] = a[j], a[i]
     
 
# Driver program
a = [1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1,
        1, 1, 0, 0, 1, 1, 0, 1, 0, 0]
n = len(a)
 
sortBinaryArray(a, n)
 
for i in range(n):
        print(a[i], end = " ")
 
# This code is contributed by Shrikant13.

// C# Code for Sort a binary
// array using one traversal
using System;
 
class GFG {
 
    static void sortBinaryArray(int[] a,
                                  int n)
    {
        int j = -1;
        for (int i = 0; i < n; i++)
        {
 
            // if number is smaller than
            // 1 then swap it with j-th
            // number
            if (a[i] < 1) {
                j++;
                int temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
        }
    }
 
    /* Driver program to test above
    function */
    public static void Main()
    {
 
        int[] a = { 1, 0, 0, 1, 0, 1, 0,
                    1, 1, 1, 1, 1, 1, 0,
                    0, 1, 1, 0, 1, 0, 0 };
 
        int n = a.Length;
 
        sortBinaryArray(a, n);
 
        for (int i = 0; i < n; i++)
            Console.Write(a[i] + " ");
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP Code for Sort a binary
// array using one traversal
function sortBinaryArray($a, $n)
{
    $j = -1;
    for ($i = 0; $i < $n; $i++)
    {
 
        // if number is smaller than
        // 1 then swap it with j-th
        // number
        if ($a[$i] < 1)
        {
            $j++;
            $temp = $a[$j];
            $a[$j] = $a[$i];
            $a[$i] = $temp;
        }
    }
for ($i = 0; $i < $n; $i++)
        echo $a[$i] . " ";
     
}
 
 
// Driver Code
$a = array(1, 0, 0, 1, 0, 1, 0,
           1, 1, 1, 1, 1, 1, 0,
           0, 1, 1, 0, 1, 0, 0);
 
$n = count($a);
sortBinaryArray($a, $n);
 
// This code is contributed by Sam007
?>

<script>
// Javascript Code for Sort a binary
// array using one traversal
 
    function sortBinaryArray(a, n)
    {
        let j = -1;
        for (let i = 0; i < n; i++) {
   
            // if number is smaller than 1
            // then swap it with j-th number
            if (a[i] < 1) {
                j++;
                let temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
        }
    }
   
// driver function
        let a = [ 1, 0, 0, 1, 0, 1, 0, 1, 1, 1,
                    1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0 ];
   
        let n = a.length;
   
        sortBinaryArray(a, n);
   
        for (let i = 0; i < n; i++)
            document.write(a[i] + " ");
   
  // This code is contributed by code_hunt.
</script>   

Producción : 
 

0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1

Análisis de Complejidad: 
 

• Complejidad temporal: O(n). 
  Solo se necesita un recorrido de la array, por lo que la complejidad del tiempo es O (n).

• Complejidad espacial: O(1). 
  El espacio requerido es constante.

Este artículo es una contribución de Devanshu Agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.