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:
- Cree un índice variable, digamos j = -1
- Atraviesa la array de principio a fin
- 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.
- Si el elemento es 1, mantenga el elemento como está.
Implementación:
CPP
// 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
// 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] + " "); } }
Python3
# 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#
// 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 // 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 ?>
Javascript
<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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA