shift all the zero values to the end of the array-CodePudding

How to write a code in python to shift all the zero values to the end of the array (There is a constant size integer array containing list of positive values (greater than 0). There are also some zero values in between data).

Example array [ 5 ,10, 0, 4, 0, 8, 0, 3 ]

I tried this way but its repeating the 3

    x=[5,10,0,4,0,8,0,3]
for i in range(1,8):
    if x[i]==0:
        for j in range(i,8):
            x[j]=x[j 1]

for i in range(0,8):
    print(x[i] )

CodePudding user response：

This is a simplified version of the Dutch National Flag Problem where you try to partition an array into 3 distinct parts instead of the 2 here.

The way you can solve this is by the two-pointer technique. One pointer A indicates that all element behind it are definitely non zeros while another pointer B moves forward looking for non-zeroes. Whenever B finds a none-zero it swaps that element with the element at index A and A is incremented. This results of all the non-zero elements landing to the left of A and all the zeroes to the right of A at the end.

def partition_zero_nonzero(arr): 
    l = 0   
    for i, el in enumerate(arr): 
        if el != 0: 
            arr[l], arr[i] = arr[i], arr[l]  
            l  = 1  
    return arr

A quick test:

arr =  [ 5 ,10, 0, 4, 0, 8, 0, 3 ]
partition_zero_nonzero(arr)
[5, 10, 4, 8, 3, 0, 0, 0]

Please note that this method also respect the relative ordering of the original array.

Of course, it is also possible to solve this problem by using additional space, adding all the non-zero element to the new array and filling the rest with zeros.

Update: Since you posted a solution with quadratic time complexity and asked if it's correct. Here is your corrected solution. I reiterate that it is really not efficient and you can do a lot better but it's fine for educational purposes.

def partition_zero_nonzero_quadratic(arr): 
    n_zeros = 0 
    for i in range(len(arr)): 
        if arr[i] == 0: 
            for j in range(i, len(arr)-1): 
                arr[j] = arr[j 1] 
            n_zeros  = 1 
    for i in range(len(arr)-n_zeros, len(arr)): 
        arr[i] = 0 
    return arr

Small test:

arr = [ 5 ,10, 0, 4, 0, 8, 0, 3 ]
partition_zero_nonzero_quadratic(arr)
[5, 10, 4, 8, 3, 0, 0, 0]

CodePudding user response：

Why not remove and append upon 0 encounter? This should equal a shift operation from a semantic point of view.

ex = [ 5 ,10, 0, 4, 0, 8, 0, 3 ]

for e in ex:
  try:
    ex.remove(0)
    ex.append(0)
  except ValueError:
    break

print(ex)  # [5, 10, 4, 8, 3, 0, 0, 0]

CodePudding user response：

Something like this would achieve what you need:

v = [5, 10, 0, 4, 0, 8, 0, 3]

v1 = [x for x in v if x != 0]   v.count(0) * [0]

CodePudding user response：

One way can be to loop over the list and separate the zero and non-zero elements of the list and append them to separate lists respectively. Then after that combine both the lists.

x=[5,10,0,4,0,8,0,3]

def list_partition(non_zero_list, zero_list):
    
    for i in range(len(x)):
        if x[i]==0:
            zero_list.append(x[i])
            
        elif x[i]!=0:
            non_zero_list.append(x[i])
            
    list3=non_zero_list zero_list
    return list3

final=list_partition([], [])
print(final)

This gives the output as follows:

[5, 10, 4, 8, 3, 0, 0, 0]