Given a binary array A[] of size N. The task is to arrange the array in increasing order.
Note: The binary array contains only 0  and 1.
 
Example 1:
Input: 
5
1 0 1 1 0
Output: 
0 0 1 1 1
Explanation: 
After arranging the elements in 
increasing order, elements will be as 
0 0 1 1 1.
Example 2:
Input:
10
1 0 1 1 1 1 1 0 0 0
Output: 
0 0 0 0 1 1 1 1 1 1
Explanation: 
After arranging the elements in 
increasing order, elements will be 
0 0 0 0 1 1 1 1 1 1.
Your Task: This is a function problem. You only need to complete the function binSort() that takes the array A[] and it's size N as parameters and sorts the array. The printing is done automatically by the driver code.
Expected Time Complexity: O(N)
Expected Auxilliary Space: O(1)
Constraints:
1 <= N <= 10^{6}
0 <= A[i] <= 1

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Sorting

Amortized analysis

Starter code: #User function Template for python3

class Solution:
    
    #Function to sort the binary array.
    def binSort(self, A, N): 
        #Your code here
        #No need to print the array
    

Solutions:
class Solution:

	def binSort(self, A, N):
		return A.sort()


class Solution:

	def binSort(self, A, N):
		total = sum(A)
		for i in range(N):
			if i < N - total:
				A[i] = 0
			else:
				A[i] = 1
		return A


class Solution:

	def binSort(self, A, N):
		ones = sum(A)
		for i in range(N):
			if i < N - ones:
				A[i] = 0
			else:
				A[i] = 1


class Solution:

	def binSort(self, A, N):
		j = -1
		for i in range(N):
			if A[i] < 1:
				j += 1
				(A[i], A[j]) = (A[j], A[i])


class Solution:

	def binSort(self, A, N):
		i = 0
		j = N - 1
		while i < j:
			if A[i] == 1 and A[j] == 0:
				(A[i], A[j]) = (A[j], A[i])
				i += 1
				j -= 1
			elif A[i] == 0 and A[j] == 0:
				i += 1
			elif A[i] == 1 and A[j] == 1:
				j -= 1
			else:
				i += 1
				j -= 1


class Solution:

	def binSort(self, A, N):
		(l, r) = (0, N - 1)
		while r >= 0 and A[r] == 1:
			r -= 1
		while l < r:
			if A[l] == 1:
				(A[l], A[r]) = (A[r], A[l])
				r -= 1
			else:
				l += 1


class Solution:

	def binSort(self, A, N):
		dic = {0: 0, 1: 0}
		for i in range(N):
			dic[A[i]] += 1
		A.clear()
		for i in range(dic[0]):
			A.append(0)
		for i in range(dic[1]):
			A.append(1)


class Solution:

	def binSort(self, A, N):
		s = 0
		l = N - 1
		while s <= l:
			if A[s] == 1 and A[l] == 0:
				(A[s], A[l]) = (A[l], A[s])
				s += 1
				N -= 1
			if A[s] == 0 and s <= N:
				s += 1
			if A[l] == 1 and l >= 0:
				l -= 1
		return A


class Solution:

	def binSort(self, A, N):
		first = 0
		last = N - 1
		while first < last:
			if A[first] == 1 and A[last] == 0:
				A[first] = 0
				A[last] = 1
				first += 1
				last -= 1
			elif A[first] == 1 and A[last] == 1:
				last -= 1
			elif A[first] == 0 and A[last] == 0:
				first += 1
			elif A[first] == 0 and A[last] == 1:
				first += 1
				last -= 1


class Solution:

	def binSort(self, A, N):
		i = 0
		j = N - 1
		while i < j:
			if A[i] == 1:
				while j >= 0 and A[j] != 0:
					j -= 1
				if i >= j:
					break
				(A[i], A[j]) = (A[j], A[i])
			i += 1


class Solution:

	def binSort(self, A, N):
		zero = 0
		for num in A:
			if num == 0:
				zero += 1
		k = 0
		while zero:
			A[k] = 0
			zero -= 1
			k += 1
		for i in range(k, N):
			A[i] = 1


class Solution:

	def binSort(self, A, N):
		zero = 0
		one = 0
		for i in A:
			if i == 0:
				zero += 1
			else:
				one += 1
		for i in range(zero):
			A[i] = 0
		for i in range(zero, zero + one):
			A[i] = 1


class Solution:

	def binSort(self, arr, N):
		left = 0
		right = len(arr) - 1
		while left < right:
			if arr[left] > arr[right]:
				(arr[left], arr[right]) = (arr[right], arr[left])
			if arr[left] == 0:
				left += 1
			if arr[right] == 1:
				right -= 1


class Solution:

	def binSort(self, A, N):
		c = 0
		for i in A:
			if i == 1:
				c += 1
		A[:] = []
		for i in range(N - c):
			A.append(0)
		for i in range(c):
			A.append(1)


class Solution:

	def binSort(self, A, N):
		z = A.count(1)
		p = [0] * (N - z)
		for i in range(z):
			p.append(1)
		for i in range(N):
			A[i] = p[i]


class Solution:

	def binSort(self, A, N):
		b = []
		c = []
		for i in range(N):
			if A[i] == 0:
				b.append(A[i])
			else:
				c.append(A[i])
		A.clear()
		b.extend(c)
		A.extend(b)
		return


class Solution:

	def binSort(self, A, N):
		for i in range(N):
			A.sort()
			return A


class Solution:

	def binSort(self, A, N):
		left = 0
		right = N - 1
		while left < right:
			while A[left] == 0 and left < right:
				left += 1
			while A[right] == 1 and left < right:
				right -= 1
			if left < right:
				A[left] = 0
				A[right] = 1
				left += 1
				right -= 1


class Solution:

	def binSort(self, A, N):
		i = 0
		j = 0
		while j < N:
			if A[j] == 0:
				(A[j], A[i]) = (A[i], A[j])
				i = i + 1
				j = j + 1
			else:
				j = j + 1
		return


class Solution:

	def binSort(self, arr, N):
		l = []
		for i in range(N):
			if arr[i] == 0:
				l.append(arr[i])
		for j in range(N):
			if arr[j] == 1:
				l.append(arr[j])
		arr[:] = l[:]
		return arr


class Solution:

	def binSort(self, arr, N):
		(l, r) = (0, N - 1)
		while l < r:
			if arr[l] == 0:
				l += 1
			elif arr[r] == 1:
				r -= 1
			else:
				(arr[l], arr[r]) = (arr[r], arr[l])
				l += 1
				r -= 1


class Solution:

	def binSort(self, arr, N):
		arr.sort()


class Solution:

	def binSort(self, A, N):
		temp = []
		for i in range(len(A)):
			if A[i] == 0:
				temp.append(A[i])
		for i in range(len(A)):
			if A[i] == 1:
				temp.append(A[i])
		for i in range(len(A)):
			A[i] = temp[i]
		temp.clear()


class Solution:

	def binSort(self, A, N):
		(left, right) = (0, N - 1)
		while left < right:
			if A[left] == 0:
				left += 1
			elif A[right] == 0:
				(A[left], A[right]) = (A[right], A[left])
				left += 1
				right -= 1
			else:
				right -= 1
		return A


class Solution:

	def binSort(self, A, N):
		cnt_one = 0
		cnt_zero = 0
		for i in range(0, N):
			if A[i] == 1:
				cnt_one += 1
			else:
				cnt_zero += 1
		i = 0
		while cnt_zero != 0:
			A[i] = 0
			i += 1
			cnt_zero -= 1
		while cnt_one != 0:
			A[i] = 1
			i += 1
			cnt_one -= 1
		return A


class Solution:

	def binSort(self, A, N):
		i = -1
		j = N
		while True:
			i += 1
			while i < N and A[i] == 0:
				i += 1
			j -= 1
			while j > -1 and A[j] == 1:
				j -= 1
			if i > j:
				return
			if i < N and j > -1:
				(A[i], A[j]) = (A[j], A[i])


class Solution:

	def binSort(self, A, N):
		i = -1
		pivot = 0
		for j in range(len(A)):
			if A[j] <= pivot:
				i += 1
				(A[j], A[i]) = (A[i], A[j])


class Solution:

	def binSort(self, A, N):
		a = A.count(0)
		b = A.count(1)
		for i in range(a):
			A[i] = 0
		for i in range(a, a + b):
			A[i] = 1


class Solution:

	def binSort(self, A, N):
		l = 0
		h = N - 1
		while True:
			while l < N and A[l] == 0:
				l += 1
			while h >= 0 and A[h] == 1:
				h -= 1
			if l >= h:
				break
			(A[l], A[h]) = (A[h], A[l])
			l += 1
			h -= 1


class Solution:

	def binSort(self, A, N):
		s = sorted(A)
		for i in range(len(A)):
			A[i] = s[i]


class Solution:

	def binSort(self, A, N):
		count = 0
		for i in A:
			if i == 0:
				count += 1
		A[0:count + 1] = [0] * count
		A[count:] = [1] * (N - count)


class Solution:

	def binSort(self, A, N):
		l = []
		for i in A:
			if i == 0:
				l.append(i)
		for j in A:
			if j == 1:
				l.append(j)
		A[:] = l[:]
		return A


class Solution:

	def binSort(self, arr, N):
		i = 0
		j = N
		while i < j:
			if arr[i] == 1:
				j -= 1
				while arr[j] != 0 and j >= 0:
					j -= 1
				if i < j:
					(arr[i], arr[j]) = (arr[j], arr[i])
				else:
					break
				i += 1
			else:
				i += 1


class Solution:

	def binSort(self, arr, n):
		count = 0
		for i in arr:
			if i == 0:
				count += 1
		for i in range(count):
			arr[i] = 0
		for i in range(count, n):
			arr[i] = 1


class Solution:

	def binSort(self, arr, N):
		left = 0
		right = len(arr) - 1
		while left < right:
			if arr[left] == 1 and arr[right] == 0:
				(arr[left], arr[right]) = (arr[right], arr[left])
			if arr[left] == 0:
				left += 1
			if arr[right] == 1:
				right -= 1
		return arr
		o = 0
		z = 0
		for i in range(N):
			if A[i] == 0:
				z += 1
			elif A[i] == 1:
				o += 1
		print(o)
		print(z)
		for i in range(o):
			A[i] = 0
		for i in range(o + z, N):
			A[i] = 1
		return A


class Solution:

	def binSort(self, a, n):
		i = 0
		for j in range(n):
			if a[j] == 0:
				(a[i], a[j]) = (a[j], a[i])
				i += 1
		return a