Sorting Boolean Arrays

· Dec 26, 03:48 PM

Lots of spare-time projects to choose from on a free day for me left me in a state of indecision. So I decided to take some old mathematics advice and compute the simplest thing I don’t already know. Today, that happens to be the code for sorting a Boolean array.

First is a function to test sortedness.

Function IsSorted(extends b() as Boolean) As Boolean
  dim theResult as Boolean = true
  
  dim firstTrueIndex as Integer = 1 + UBound(b)
  for i as Integer = 0 to UBound(b)
    if b(i) then
      firstTrueIndex = i
      exit
    end if
  next
  
  for i as Integer = firstTrueIndex to UBound(b)
    if not b(i) then
      theResult = false
      exit
    end if
  next
  
  return theResult
End Function

The sorting code uses a standard idea; one scans the array from left and right, swapping out-of-order elements until the pointers cross. 

Sub Sort(extends b() as Boolean)
  dim leftPtr as Integer = 0
  dim rightPtr as Integer = UBound(b) 
  
  do
    while leftPtr < rightPtr
      if not b(leftPtr) then
        leftPtr = leftPtr + 1
      else
        exit
      end if
    wend
  
    while rightPtr > leftPtr
      if b(rightPtr) then
        rightPtr = rightPtr - 1
      else
        exit
      end if
    wend
  
    if leftPtr < rightPtr then
      b(leftPtr) = false
      b(rightPtr) = true
      leftPtr = leftPtr + 1
      rightPtr = rightPtr - 1
    else
      exit
    end if
  loop
End Sub

This code is a little more subtle than a first glance might reveal, and I’m not telling whether or not I got it on the first try. If you have an interest in learning quicksort, this code might serve as a useful warmup for following the partition code.

---

Comment

  1. Wow, what an odd challenge.
    I’d simply count all the false values in the array in one loop, let that be N, then do a second loop in which I set the first N items to false, and the rest to true. This way, each value is read only once and written only once.
    Would that be a valid solution? Why did you choose yours? Is yours in any way superior, other than looking closer to quicksort’s partition function? :)

    — Thomas Tempelmann · Dec 26, 07:56 PM · #

  2. Sure, your idea would work. My code only reads values once, though there are a few more integer comparisons. I wrote my code with the idea of implementing SortWith using a Boolean array for keys.

    — charles Yeomans · Dec 26, 09:34 PM · #

Commenting is closed for this article.