Sort Numbers using a Fenwick Tree (with Help from ChatGPT)

Introduction

I already wrote a few years ago, two articles to sort out the numbers. My recent article explains that you can use the sum of all items to sort them by find which is the n^th position in the list by item number and reorder the list.

Background

You can read my previous article here.

The Discussion with ChatGPT

First of all, early today I asked ChatGPT how it was possible to sort numbers by building a tree and store the min and max values ​​in the tree and make the tree grow each list iteration.

But, I asked him (who?) also what an online algorithm is and he replied with a full explanation of what it is.

And then, he replied that a tree to sort an algorithm can be a Fenwick tree.

So, I was going to read a documentation of what a Fenwick tree is and I didn't understand anything.

The First Code as an Exercice

Next, I started to code an example of a Fenwick tree like this code.

[<<[
   t = [ 1,2,3,4 ],
   fun g(r) {
     output(r & (r+1))
   },
   fun sum[t](r) {
     res = 0,
     while(r >= 0) {
       res = res + t(r),
       r = g(r) - 1
     },
     output(res)
  },

  fun increase[t,g](i, delta) {
     foreach(j from g) {
        if (j <= i) {
           t(j) = t(j) + delta
        }
     }
  },

  // print(sum(1)),
  // print(sum(3)),
  print(g(0)),
  print(g(1)),
  print(g(2)),
  print(g(3)),
  increase(3,5),
  print(list@ToSequence(t,","))
]>>]

The output obtained is bad and does not work because of the calculation of the least significant bit of 'i'.

My Second Conversation with ChatGPT

My idea was to ask ChatGPT again to help me understand how the Fenwick tree works and how it works.

His explanations were unclear to me and I asked him (who?) a lot of questions that he can help (like a teacher who repeats his lesson over and over again).

And so, I asked this question:

Quote:

OK, so are you sure the Fenwick tree is summing a range from zero to r? Or did it erase the previous recorded item and not overwrite it? I have a hard time imagining the data structure of Fenwick's tree.

And ChatGPT answered to me:

Quote:

Yes, I'm sure that the Fenwick tree can be used to efficiently compute the prefix sum of a range from zero to r. In other words, it can be used to compute the sum of the elements in the array from the first element up to the element at index r.

The Fenwick tree is a data structure that is constructed using a binary tree. Each node in the tree stores the sum of a range of elements in the array. The root node stores the sum of the entire array, while the leaf nodes store the sum of a single element. The intermediate nodes store the sum of the ranges of their child nodes.

To compute the prefix sum of a range from zero to r, the query_fenwick_tree function follows a path through the tree that is determined by the least significant bits of r. It adds up the values of the nodes it passes through to compute the prefix sum of the elements in the range.

It's important to note that the Fenwick tree does not store the individual elements of the array. Instead, it stores the sum of ranges of elements. This allows it to efficiently compute the prefix sum of a range without having to store the individual elements.

I hope this helps to clarify things. Please let me know if you have any further questions.

So, while I couldn't figure out how it works yet, I started asking ChatGPT to show me an algorithm to calculate the least significant bit in a simple way. It has given to me that code:

def get_lsb(n):
    lsb = 0
    while (n & 1) == 0:
        lsb += 1
        n >>= 1
    return lsb

# Example usage
print(get_lsb(0))  # Outputs: 0
print(get_lsb(1))  # Outputs: 0
print(get_lsb(2))  # Outputs: 1
print(get_lsb(3))  # Outputs: 0
print(get_lsb(4))  # Outputs: 2
print(get_lsb(5))  # Outputs: 0
print(get_lsb(6))  # Outputs: 1
print(get_lsb(7))  # Outputs: 0

Now, I can write a code and I understand the Fenwick tree algorithm.

[<<[
  tree = [],
  fun lsb(n) {
    res = 0,
    while(n > 0 && n % 2 == 0) {
      res = res + 1,
      n = (n - n % 2) / 2
    },
    output(res)
  },
  fun init_fenwick_tree[tree](n) {
    while(n > 0) {
      tree = tree 0,
      n = n - 1
    }
  },
  fun create_fenwick_tree[tree](arr) {
    init_fenwick_tree(arr.length),
    foreach(i from arr) {
      update_fenwick_tree(i, arr(i))
    }
  },
  fun update_fenwick_tree[tree](i, diff) {
    while(i < tree.length) {
      tree(i) = tree(i) + diff,
      l = lsb(i),
      if (l == 0)
        { i = i + 1 }
      else
        i = i + l,
    }
  },
  create_fenwick_tree([1,2,3,4]),
  print(list@ToSequence(tree,";"))
]>>]

Now, the output is:

1;3;6;10

1) 1
2) 3 = 1+2
3) 6 = 1+2+3
4) 10 = 1+2+3+4

Later I Come Back to ChatGPT

I asked to ChatGPT:

Quote:

Is it possible to use Fenwick tree to calculate the sum of all elements in a list and then calculate the n-th position on each element to sort and reorder them in o(n)

He answered to me:

Quote:

Yes, it is possible to use the Fenwick tree to efficiently compute the prefix sums of a list of elements and use those prefix sums to sort the elements in linear time.

Here is an example of how this could be done:

ASM

def sort_using_fenwick_tree(arr):
    # Create a Fenwick tree for the array
    tree = [0] * (len(arr) + 1)
    for i, a in enumerate(arr):
        update_fenwick_tree(tree, i, a)

    # Sort the array using the prefix sums computed by the Fenwick tree
    sorted_arr = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        prefix_sum = query_fenwick_tree(tree, i)
        sorted_arr[prefix_sum - 1] = arr[i]
        update_fenwick_tree(tree, i, -arr[i])

    return sorted_arr

# Example usage
arr = [5, 2, 3, 1, 4]
sorted_arr = sort_using_fenwick_tree(arr)
print(sorted_arr)  # Outputs: [1, 2, 3, 4, 5]

The Code to Sort Numbers

Fix Errors

But, the previous code is not well-formed for sorting numbers. In fact, the LSB function was not written in a correct way.

The correct way to calculate LSB and how this instruction works:

i & -i

is to start calculating a string from a number, remove the least significant bit equal to 1 to 0, then recalculate the number from the string (the same number without the least significant bit equal to 1) and subtract the input number with that result.

The code below explains that:

[<<[
fun lsb(n) {
    res = [],
    k = n,
    while(n > 0) {
       p = n % 2,
       res = res p,
       n = (n - n % 2) / 2
    },
    select {
      default {
         foreach(i from res) {
            if (res(i) == 1) {
                res(i) = 0,
                jump "break"
            }
         }
      },
      break {}
    },
    z = 0,
    i = res.length - 1,
    while(i >= 0) {
       z = 2 * z,
       z = z + res(i),
       i = i - 1
    },
    output(k-z)
},
count = 0,
while(count < 20) {
    print("count = " count "; lsb = " lsb(count)),
    count = count + 1
}
]>>]

The output is now:

count = 0;lsb = 0
count = 1;lsb = 1
count = 2;lsb = 2
count = 3;lsb = 1
count = 4;lsb = 4
count = 5;lsb = 1
count = 6;lsb = 2
count = 7;lsb = 1
count = 8;lsb = 8
count = 9;lsb = 1
count = 10;lsb = 2
count = 11;lsb = 1
count = 12;lsb = 4
count = 13;lsb = 1
count = 14;lsb = 2
count = 15;lsb = 1
count = 16;lsb = 16
count = 17;lsb = 1
count = 18;lsb = 2
count = 19;lsb = 1 

These are the exact values of i & -i as you can view these results on this page.

Now, we can construct the Fenwick tree.

[<<[
fun init_fenwick_tree[tree](n) {
    while(n > 0) {
       tree = tree 0,
       n = n - 1
    }
},
fun create_fenwick_tree[tree](arr) {
    init_fenwick_tree(arr.length),
    foreach(i from arr) {
       update_fenwick_tree(i, arr(i))
    }
},
fun update_fenwick_tree[tree](i, diff) {
    select {
       default {
          while(i < tree.length) {
             tree(i) = tree(i) + diff,
             l = lsb(i),
             if (l == 0)
                 { jump "break" }
             else
                 i = i + l
          }
       },
       break {}
    }
},
fun query_fenwick_tree[tree](start, end) {
     sum = 0,
     i = end,
     select {
        default {
           while(i >= start) {
              sum = sum + tree(i),
              l = lsb(i),
              if (l == 0)
                  { jump "break" }
              else
                  i = i - l
           }
        },
        break {}
     },
     output(sum)
},
create_fenwick_tree([1,2,6,4,2,6,7,-3,9,1,4,6,-3,1,2,5]),
foreach(i from tree) {
    print(query_fenwick_tree(0,i))
}
]>>] 

The Fenwick tree is not a list of all sums. This is a specific list which is not complete. Reading the tree is not accurate.

To compute the sums by a range, you need to call query_fenwick_tree(start, end).

So, the output is finally:

1
3
9
13
15
21
28
25
34
35
39
45
42
43
45
50 

The Sort Algorithm

I don't know why, but the code ChatGPT showed me it doesn't work and it looks like it's sort by counting, but I'm not sure.

So, I wrote an another code to sort numbers by a counting sort. But this code has finally a complexity of o(n^2).

[<<[
    croisements = {},
    fun getIndex(sum, x) {
        output(1/((sum-x)/x+1))
    },
    fun toInt(x) {
        n = 0,
        fun selectIndice(t) {
            p = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ],
            select {
                 break {},
                 default {
                      count = 9,
                      while(count >= 0) {
                           if (p(count) <= t) {
                                t = p(count),
                                jump "break"
                           },
                           count = count - 1
                      }
                 }
            },
            output(t)
        },
        count = 1,
        while(x >= 1) {
            t = selectIndice(x % 10),
            x = (x-t) / 10,
            n = n + t*count,
            count = count * 10
        },
        output(n)
    },
    fun lsb(n) {
       res = [],
       k = n,
       while(n > 0) {
            p = n % 2,
            res = res p,
            n = (n - n % 2) / 2
       },
       select {
           default {
               foreach(i from res) {
                   if (res(i) == 1) {
                        res(i) = 0,
                        jump "break"
                   }
               }
           },
           break {}
       },
       z = 0,
       i = res.length - 1,
       while(i >= 0) {
            z = 2 * z,
            z = z + res(i),
            i = i - 1
       },
       output(k-z)
    },
    fun init_sort_tree[tree](arr) {
        foreach(i from arr) {
             h = { sum : 0, max : arr(i) },
             tree = tree h
        }
    },
    fun create_sort_tree[croisements,tree](arr) {
        init_sort_tree(arr),
        foreach(i from tree) {
             update_sort_tree(i, arr(i))
        }
    },
    fun update_sort_tree[croisements,arr,tree](i, diff) {
        j = i,
       select {
           default {
              while(i < tree.length) {
                    if (croisements(i) exists) {} else croisements(i) = [],
                    croisements(i) = croisements(i) j,
                    if (tree(i).max < diff) {
                        tree(i).max = diff
                    },
                    tree(i).sum = tree(i).sum + diff,
                    l = lsb(i),
                    if (l == 0)
                        { jump "break" }
                    else
                        i = i + l
              }
           },
           break {}
      }
    },
    fun query_sort_tree[exceptions, croisements, arr,tree](start, end) {
           i = end,
           sum = 0,
           max = tree(end).max,
              select {
                  default {
                       while(i >= start) {
                           if (croisements(end) exists) {} else croisements(end) = [],
                           croisements(end) = croisements(end) i,
                           if (exceptions(i)) {} else {
                               if (tree(i).max > max) {
                                    max = tree(i).max
                               },
                               sum = sum + tree(i).sum
                           },
                           l = lsb(i),
                           if (l == 0)
                                 { jump "break" }
                           else
                                 i = i - l
                       }
                  },
                  break {}
              },
              output({ sum : sum, max : max })
    },
    tree = [],
    arr = [1,2,6,4,2,6,7,3,9,1,4,6,3,1,2,5],
    print("start"),
    create_sort_tree(arr),
    print(arr),
    print(list@ToSequence(tree, ";")),
    foreach(i from croisements) {
         croisements(i) = croisements(i) "|"
    },
    exceptions = {},
    foreach(i from tree) {
       h = query_sort_tree(0, i),
       print(h.sum ";" h.max)
    },
    foreach(i from croisements) {
       print(i " = " list@ToSequence(croisements(i), ","))
    },

    // sort algorithm starting
    h = query_sort_tree(0, tree.length - 1),
    sum = h.sum,
    max = h.max,
    r = [],
    // init sorted result
    i = arr.length * arr.length,
    while(i > 0) {
         r = r 0,
         i = i - 1
     },
     foreach(i from arr) {
          s = toInt(getIndex(sum, arr(i)) * sum / max * arr.length * arr.length)),
          r( s ) = arr(i)
     },
     foreach(i from r) {
          if (r(i) == 0) {} else print(r(i) ",")
     }
]>>]

The output of this code shows:

1. the input list : this list items have only positive values and the algorithm works well for unique and positive values.
2. the tree list
3. the sum and the maximum value for each range from [0,i] when 0 <= i < n
4. the method to compute the sum (the list of indexes in the array and then in the tree for each range)
5. the sorted list

start
1,2,6,4,2,6,7,3,9,1,4,6,3,1,2,5
[object Object];....
1;1
3;2
9;6
13;6
15;6
21;6
28;7
31;7
40;9
41;9
45;9
51;9
54;9
55;9
57;9
62;9
0 = 0,|,0
1 = 1,|,1,0
2 = 1,2,|,2,0
3 = 3,|,3,2,0
4 = 1,2,3,4,|,4,0
5 = 5,|,5,4,0
6 = 5,6,|,6,4,0
7 = 7,|,7,6,4,0
8 = 1,2,3,4,5,6,7,8,|,8,0
9 = 9,|,9,8,0
10 = 9,10,|,10,8,0
11 = 11,|,11,10,8,0
12 = 9,10,11,12,|,12,8,0
13 = 13,|,13,12,8,0
14 = 13,14,|,14,12,8,0
15 = 15,|,15,14,12,8,0
1,
2,
3,
4,
5,
6,
7,
9,

Points of Interest

I learned Fenwick's tree algorithm. I explained and showed the results. I understood this algorithm well. Although this algorithm takes linear time, its complexity to retrieve the elements of the sorted list has a complexity of O(n^2) because I didn't quite understand how to reproduce the code ChatGPT gave me.

History

• 26^th December, 2022: Initial version