Moving zeros to the beginning of an array

Using Swift
1

I need help with my solution the algorithm question below. My code works but the elements to right side of the array are not supposed to be sorted. My solution came from a java code.

You are given an array of integers. Rearrange the array so that all zeroes are at the beginning of the array.For example,a = [4,2,0,1,0,3,0] -> [0,0,0,4,1,2,3]

Java Code

public static void moveZeroesToBeginning(int[] a) {   
 int boundary = 0;   

 for (int i = 0; i < a.length; i++) {      
  if (a[i] == 0) {            
 
Utils.swap(a, i, boundary);           
 boundary += 1;      
  }   
 }
}

Swift code

func moveZerosTotheFront(arrays:[Int] )->[Int] {
    var result = arrays
    var boundary = 0
    for index in 0...arrays.count-1{
        if result[index] == 0{
            print(index )
            result.swapAt(index, boundary)
            boundary+=1
        }
    }
    return result
}
2

If Utils.swap only swap the two element at i and boundary, it should have the same behaviour as your Swift code. My advice is to try to include result at the print line so that you can see what's going on.

You'll see that it isn't actually sorting the non-zero entries. The algorithm just ignores the order of those entries altogether. and you can confirm by trying [1, 2, 0, 3, 0, 4, 0]. You need a different algorithm if you want to maintain those the order ([0, 0, 0, 0, 4, 1, 2, 3]).

3

Thank you for the response. Can you please recommend a strategy that I can use to partition the array into two parts that are zeros and non zeros ?

4

See Array’s partition method, though it makes no guarantees about how the elements in each partition are sorted.

1 Like
5

Assuming you want to maintain the order of the array’s elements, it seems that you’re looking for a stable partitioning algorithm. The best way to do this in Swift is to use the Swift Algorithms package. In an Xcode 13 project, you can add Swift Algorithms by going to File > Add Packages… > Apple Swift Packages > swift-algorithms > Add Package. (Swift Algorithms is open-source and made by Apple itself, so you don’t have to worry about it containing malicious code.)

Once you have added Swift Algorithms to your project, you can move all zeros in an array to the beginning with the following code:

import Algorithms

var array = [4, 2, 0, 1, 0, 3, 0]
_ = array.stablePartition(by: { $0 != 0 })
print(array)
// [0, 0, 0, 4, 2, 1, 3]

stablePartition(by:) returns the index of the beginning of the second partition (in this case, the index of the beginning of the non-zero numbers), which you may find useful.

3 Likes
6

Perhaps this is not what you're looking for because I'm taking advantage of the fact that zeros are the same predictable thing and thus can be discarded and recreated at will, but you could simply filter-out all the zeros, then add back the correct number of zeros at the beginning.

let array = [4, 2, 0, 1, 0, 3, 0]
let nonZeros = array.filter { $0 != 0 }
let result = Array(repeating: 0, count: array.count - nonZeros.count) + nonZeros
print(result)

It can also be done in-place by iterating in reverse and writing the non-zero values from the end, then filling the rest with zeros:

var array = [4, 2, 0, 1, 0, 3, 0]
var insertIndex = array.count
for index in (0 ..< array.count).reversed() where array[index] != 0 {
  insertIndex -= 1
  array[insertIndex] = array[index]
}
for index in 0 ..< insertIndex {
  array[index] = 0 // fill remaining with zeros
}
print(array)

No need to swap anything here. :wink:

7

I’m not sure but… It could be one line in Swift?

func moveZerosTotheFront(array: [Int]) -> [Int] {
    array.sorted { $0 == 0 && $1 != 0 }
}

To be clear, the sorted() method provided by Swift Standard Library is not guaranteed to be stable. It just happens that the current implementation is a stable one. If you want a really stable one, check out Algorithms.

1 Like
8

This is about partitioning, not sorting. You’re doing a lot of extra work for no reason there.

When it comes to algorithms, you should be doing as little work as possible.

9

Hello. If you don't want to use libraries, you can use this snippet:

  /*
   *   input:  [0, 10, 0, 1, 2, 3, 0, 0, 4, 0, 0, 5, 0, 6, 0, 7, 8, 9]
   *   output: [0, 0, 0, 0, 0, 0, 0, 0, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9]
   */
  var array: [Int] = [0, 10, 0, 1, 2, 3, 0, 0, 4, 0, 0, 5, 0, 6, 0, 7, 8, 9]
  var startZeroIndex: Int?
  
  for index in array.indices.reversed() {
    if array[index] == 0 {
      if startZeroIndex == nil {
        startZeroIndex = index
      }
    } else {
      if let startIndex = startZeroIndex {
        array[startIndex] = array[index]
        array[index] = 0
        
        startZeroIndex = startIndex - 1
      } else {
        continue
      }
    }
  }

  print(array)
10

First off, you really should just use packages. Swift is quite good at eliminating unused code during compilation with the right compiler settings, and it saves you the trouble of writing rigorous performance and unit tests.

Second, Swift Algorithms is open-source: you could just copy their implementation if you insist (though you’ll have to copy the license and such too).

Third, your implementation has quadratic time complexity.

When writing pure algorithms in Swift, you should make them as generic as possible, ensure proper unit test coverage, and carefully document everything (especially time complexity). This generally takes a couple minutes at most.

11

In this case, you probably don’t care about the relative order of the zeros. That means you want either an unstable partition (which is in the standard library) or a half-stable partition (which is in Swift Algorithms), depending on whether you care about the relative order of non-zero elements.

12

Is there a half-stable partition in Swift Algorithms? There’s a stable partitioning algorithm, but I don’t see a half-stable partitioning algorithm.

There’s a _halfStablePartition method in the standard library, but it isn’t publicly accessible (it is currently used in the public partition method, but that’s an implementation detail and the order isn’t guaranteed). You can copy the code from the standard library and paste it in your own project if you’d like to use it.

13

It’s incredibly poorly-named, but it is in fact right here.

14

Just in case, if this is part of an assignment, don't actually copy codes.

15

And if it isn’t, also don’t copy code. If you can’t write it yourself, it should be a versioned dependency.

Mimicking code is generally fine, though. So long as you understand it completely.