Updated version are available here:

https://dzen.ru/a/ZtbHTpKj9VQripUx

## Turn on USB keyboard backlight on macOS

I recently bought a very inexpensive Getorix GK-45X USB keyboard with RGB backlight. After connecting it to a Macbook Pro on an M1 processor, it became clear that the RGB backlight was not working. Even by pressing the magic combination Fn + Scroll Lock, it was not possible to turn on the backlight, only the backlight level of the MacBook screen changed.

There are several solutions to this problem, namely OpenRGB (does not work), HID LED Test (does not work). Only the kvmswitch utility worked:

https://github.com/stoutput/OSX-KVM

You need to download it from the github and allow it to run from the terminal in the Security panel of the System Settings.

As I understood from the description, after launching the utility sends pressing Fn + Scroll Lock, thus turning on/off the backlight on the keyboard.

## Mitsume ga Tōru (NES) – The Three-Eyed One

## Number 2

Comrades, I take pride in projects that were created on the basis of Flame Steel Framework 1 and specifically on Flame Steel Engine 1, namely Death-Mask, Cube Art Project, since all this was conceived as a big experiment, creating a multimedia framework alone that can work on the most platforms. I think the experiment ended successfully immediately after the release of the Cube Art Project.

Now about the decisions that I came to during the development of new projects on FSFramework 1

During the development of Space Jaguar and the Space Jaguar Galaxy Bastards shooter, it became clear that the Flame Steel Framework tools were already outdated, not even having time to become at least somewhat convenient.

Therefore, I decided to develop a completely new Flame Steel Framework 2. The main decision will be to switch to my Rise 2 transpiler language, and the Component System (ECS) will no longer be used architecturally, because. it turned out to be needed only within the framework of game logic with great dynamics. For this reason, in Flame Steel Framework 2, the component system will only be possible while using the scripting languages that are planned to be implemented (at least Lua and JavaScript), an interesting feature is that these languages are dynamic in nature, so additional creation of the component system is redundant.

You can follow the development of new projects on the blog and on Gitlab:

https://gitlab.com/demensdeum/rise2

https://gitlab.com/demensdeum/flamesteelengine2

https://gitlab.com/demensdeum/flame-steel-engine-2-demo-projects

https://gitlab.com/demensdeum/space-jaguar-action-rpg

https://gitlab.com/demensdeum/space-jaguar-galaxy-bastards

## Tree sort

Tree sort – binary search tree sort. Time complexity – O(n²). In such a tree, each node has numbers less than the node on the left, more than the node on the right, when coming from the root and printing the values from left to right, we get a sorted list of numbers. Surprising huh?

Consider the binary search tree schema:

Derrick Coetzee (public domain)

Try to manually read the numbers starting from the penultimate left node of the lower left corner, for each node on the left – a node – on the right.

It will turn out like this:

- The penultimate node at the bottom left is 3.
- She has a left branch – 1.
- Take this number (1)
- Next, take the vertex 3 (1, 3) itself
- To the right is branch 6, but it contains branches. Therefore, we read it in the same way.
- Left branch of node 6 number 4 (1, 3, 4)
- Node 6 itself (1, 3, 4, 6)
- Right 7 (1, 3, 4, 6, 7)
- Go up to the root node – 8 (1,3, 4 ,6, 7, 8)
- Print everything on the right by analogy
- Get the final list – 1, 3, 4, 6, 7, 8, 10, 13, 14

To implement the algorithm in code, you need two functions:

- Building a binary search tree
- Printing the binary search tree in the correct order

They assemble a binary search tree in the same way as they read it, a number is attached to each node on the left or right, depending on whether it is less or more.

Lua example:

```
Node = {value = nil, lhs = nil, rhs = nil}
function Node:new(value, lhs, rhs)
output = {}
setmetatable(output, self)
self.__index = self
output.value = value
output.lhs = lhs
output.rhs = rhs
output.counter = 1
return output
end
function Node:Increment()
self.counter = self.counter + 1
end
function Node:Insert(value)
if self.lhs ~= nil and self.lhs.value > value then
self.lhs:Insert(value)
return
end
if self.rhs ~= nil and self.rhs.value < value then
self.rhs:Insert(value)
return
end
if self.value == value then
self:Increment()
return
elseif self.value > value then
if self.lhs == nil then
self.lhs = Node:new(value, nil, nil)
else
self.lhs:Insert(value)
end
return
else
if self.rhs == nil then
self.rhs = Node:new(value, nil, nil)
else
self.rhs:Insert(value)
end
return
end
end
function Node:InOrder(output)
if self.lhs ~= nil then
output = self.lhs:InOrder(output)
end
output = self:printSelf(output)
if self.rhs ~= nil then
output = self.rhs:InOrder(output)
end
return output
end
function Node:printSelf(output)
for i=0,self.counter-1 do
output = output .. tostring(self.value) .. " "
end
return output
end
function PrintArray(numbers)
output = ""
for i=0,#numbers do
output = output .. tostring(numbers[i]) .. " "
end
print(output)
end
function Treesort(numbers)
rootNode = Node:new(numbers[0], nil, nil)
for i=1,#numbers do
rootNode:Insert(numbers[i])
end
print(rootNode:InOrder(""))
end
numbersCount = 10
maxNumber = 9
numbers = {}
for i=0,numbersCount-1 do
numbers[i] = math.random(0, maxNumber)
end
PrintArray(numbers)
Treesort(numbers)
```

An important nuance is that for numbers that are equal to the vertex, a lot of interesting mechanisms for hooking to the node have been invented, but I just added a counter to the vertex class, when printing, the numbers are returned by the counter.

### Links

https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/treesort

### References

Convert Sorted Array to Binary Search Tree (LeetCode 108. Algorithm Explained) – YouTube

Sorting algorithms/Tree sort on a linked list – Rosetta Code

How to handle duplicates in Binary Search Tree? – GeeksforGeeks

Tree Sort | GeeksforGeeks – YouTube

## Bucket Sort

Bucket Sort – bucket sorting. The algorithm is similar to sorting by counting, with the difference that the numbers are collected into “buckets”-ranges, then the buckets are sorted using any other, sufficiently productive, sorting algorithm, and the final chord is the expansion of the “buckets” one by one, resulting in a sorted list.

The time complexity of the algorithm is **O(nk)**. The algorithm runs in linear time for data that obeys a uniform distribution. To put it simply, the elements must be in a certain range, without “splashes”, for example, numbers from 0.0 to 1.0. If among such numbers there are 4 or 999, then such a series, according to the laws of the yard, is no longer considered “even”.

Implementation example in Julia:

```
function bucketSort(numbers, bucketsCount)
buckets = Vector{Vector{Int}}()
for i in 0:bucketsCount - 1
bucket = Vector{Int}()
push!(buckets, bucket)
end
maxNumber = maximum(numbers)
for i in 0:length(numbers) - 1
bucketIndex = 1 + Int(floor(bucketsCount * numbers[1 + i] / (maxNumber + 1)))
push!(buckets[bucketIndex], numbers[1 + i])
end
for i in 0:length(buckets) - 1
bucketIndex = 1 + i
buckets[bucketIndex] = sort(buckets[bucketIndex])
end
flat = [(buckets...)...]
print(flat, "\n")
end
numbersCount = 10
maxNumber = 10
numbers = rand(1:maxNumber, numbersCount)
print(numbers,"\n")
bucketsCount = 10
bucketSort(numbers, bucketsCount)
```

The performance of the algorithm is also affected by the number of buckets, for more numbers it is better to take a larger number of buckets (Algorithms in a nutshell by George T. Heineman)

### Links

https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/bucketSort

### References

https://www.youtube.com/watch?v=VuXbEb5ywrU

https://www.youtube.com/watch?v=ELrhrrCjDOA

https://medium.com/karuna-sehgal/an-introduction-to-bucket-sort-62aa5325d124

https://www.geeksforgeeks.org/bucket-sort-2/

https://ru.wikipedia.org/wiki/%D0%91%D0%BB%D0%BE%D1%87%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0

https://www.youtube.com/watch?v=LPrF9yEKTks

https://en.wikipedia.org/wiki/Bucket_sort

https://julialang.org/

https://www.oreilly.com/library/view/algorithms-in-a/9780596516246/ch04s08.html

## Radix Sort

Radix Sort – radix sort. The algorithm is similar to counting sort in that there is no comparison of elements, instead elements are *character-by-character* grouped into *buckets* (buckets), the bucket is selected by the index of the current number-character. Time complexity – O(nd).

Works like this:

- The input will be the numbers 6, 12, 44, 9
- Let’s create 10 buckets of lists (0-9) into which we will add/sort numbers bit by bit.

Further:

- Run a loop with counter i up to the maximum number of characters in the number
- At index i from right to left we get one character for each number, if there is no character, then we consider it to be zero
- The character is converted to a number
- Select a bucket by index – number, put the whole number there
- After finishing iterating over numbers, convert all buckets back to a list of numbers
- Get numbers sorted by digit
- Repeat until all digits run out

Radix Sort example in Scala:

```
import scala.collection.mutable.ListBuffer
import scala.util.Random.nextInt
object RadixSort {
def main(args: Array[String]) = {
var maxNumber = 200
var numbersCount = 30
var maxLength = maxNumber.toString.length() - 1
var referenceNumbers = LazyList.continually(nextInt(maxNumber + 1)).take(numbersCount).toList
var numbers = referenceNumbers
var buckets = List.fill(10)(ListBuffer[Int]())
for( i <- 0 to maxLength) { numbers.foreach( number => {
var numberString = number.toString
if (numberString.length() > i) {
var index = numberString.length() - i - 1
var character = numberString.charAt(index).toString
var characterInteger = character.toInt
buckets.apply(characterInteger) += number
}
else {
buckets.apply(0) += number
}
}
)
numbers = buckets.flatten
buckets.foreach(x => x.clear())
}
println(referenceNumbers)
println(numbers)
println(s"Validation result: ${numbers == referenceNumbers.sorted}")
}
}
```

The algorithm also has a version for parallel execution, for example on the GPU; there is also a variant of bit sort, which is probably** very interesting and truly breathtaking!**

### Links

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/radixSort/radixSort.scala

### Sources

https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%80%D0%B0%D0%B7%D1%80% D1%8F%D0%B4%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0% B2%D0%BA%D0%B0

https://www.geeksforgeeks.org/radix-sort/

https://www.youtube.com/watch?v=toAlAJKojos

https://github.com/gyatskov/radix-sort

## Heapsort

Heapsort – heap sort. Time complexity – O(n log n), fast eh? I would call this sorting – sorting of falling stones. It seems to me that the easiest way to explain it is visually.

The input is a list of numbers, for example:

5, 0, 7, 2, 3, 9, 4

From left to right, a data structure is made – a binary tree, or as I call it – a pyramid. Pyramid elements can have a maximum of two child elements, with only one top element.

Let’s make a binary tree:

⠀⠀5

⠀0⠀7

2 3 9 4

If you look at the pyramid for a long time, you can see that these are just numbers from the array, going one after another, the number of elements in each floor is multiplied by two.

Then the fun begins, we sort the pyramid from bottom to top, using the falling pebbles method (heapify). Sorting could be started from the last floor (2 3 9 4 ), but it makes no sense because there is no floor below where one could fall.

Therefore, we start dropping elements from the penultimate floor (0 7)

⠀⠀5

⠀0⠀**7**

2 3 9 4

The first element to fall is selected on the right, in our case it is 7, then we look at what is under it, and below it are 9 and 4, nine is more than four, so also nine is more than seven! We drop 7 on 9, and raise 9 to place 7.

⠀⠀5

⠀0⠀9

2 3 **7** 4

Further, we understand that the seven has nowhere to fall below, go to the number 0, which is located on the penultimate floor on the left:

⠀⠀5

⠀**0**⠀9

2 3 7 4

We look at what is under it – 2 and 3, two is less than three, three is greater than zero, so we change zero and three in places:

⠀⠀5

⠀3⠀9

2 **0** 7 4

When you get to the end of the floor, go to the floor above and drop everything there if you can.

The result is a data structure – a heap (heap), namely max heap, because at the top is the largest element:

⠀⠀**9**

⠀3⠀7

2 0 5 4

If you return it to an array representation, you get a list:

[**9**, 3, 7, 2, 0, 5, 4]

From this we can conclude that by swapping the first and last element, we will get the first number in the final sorted position, namely 9 should be at the end of the sorted list, swap:

[4, 3, 7, 2, 0, 5, **9**]

Let’s look at the binary tree:

⠀⠀4

⠀3⠀7

2 0 5 9

The result is a situation in which the lower part of the tree is sorted, you just need to drop 4 to the correct position, repeat the algorithm, but do not take into account the already sorted numbers, namely 9:

⠀⠀**4**

⠀3⠀7

2 0 5 9

⠀⠀7

⠀3⠀**4**

2 0 5 9

⠀⠀7

⠀3⠀5

2 0 **4** 9

It turned out that we, having dropped 4, raised the next largest number after 9 – 7. Swap the last unsorted number (4) and the largest number (7)

⠀⠀4

⠀3⠀5

2 0 7 9

It turned out that now we have two numbers in the correct final position:

4, 3, 5, 2, 0, **7**, **9**

Next, we repeat the sorting algorithm, ignoring those already sorted, as a result we get heap:

⠀⠀0

⠀2⠀3

4 5 7 9

Or as a list:

0, 2, 3, 4, 5, 7, 9

### Implementation

The algorithm is usually divided into three functions:

- Heap creation
- Sifting algorithm (heapify)
- Replacing the last unsorted element and the first one

A heap is created by traversing the penultimate row of the binary tree using the heapify function, from right to left to the end of the array. Then the first replacement of numbers is made in the cycle, after which the first element falls / remains in place, as a result of which the largest element falls into first place, the cycle repeats with a decrease in participants by one, because after each pass, the sorted numbers remain at the end of the list.

Heapsort example in Ruby:

```
DEMO = true
module Colors
BLUE = "\033[94m"
RED = "\033[31m"
STOP = "\033[0m"
end
def heapsort(rawNumbers)
numbers = rawNumbers.dup
def swap(numbers, from, to)
temp = numbers[from]
numbers[from] = numbers[to]
numbers[to] = temp
end
def heapify(numbers)
count = numbers.length()
lastParentNode = (count - 2) / 2
for start in lastParentNode.downto(0)
siftDown(numbers, start, count - 1)
start -= 1
end
if DEMO
puts "--- heapify ends ---"
end
end
def siftDown(numbers, start, rightBound)
cursor = start
printBinaryHeap(numbers, cursor, rightBound)
def calculateLhsChildIndex(cursor)
return cursor * 2 + 1
end
def calculateRhsChildIndex(cursor)
return cursor * 2 + 2
end
while calculateLhsChildIndex(cursor) <= rightBound
lhsChildIndex = calculateLhsChildIndex(cursor)
rhsChildIndex = calculateRhsChildIndex(cursor)
lhsNumber = numbers[lhsChildIndex]
biggerChildIndex = lhsChildIndex
if rhsChildIndex <= rightBound
rhsNumber = numbers[rhsChildIndex]
if lhsNumber < rhsNumber
biggerChildIndex = rhsChildIndex
end
end
if numbers[cursor] < numbers[biggerChildIndex]
swap(numbers, cursor, biggerChildIndex)
cursor = biggerChildIndex
else
break
end
printBinaryHeap(numbers, cursor, rightBound)
end
printBinaryHeap(numbers, cursor, rightBound)
end
def printBinaryHeap(numbers, nodeIndex = -1, rightBound = -1)
if DEMO == false
return
end
perLineWidth = (numbers.length() * 4).to_i
linesCount = Math.log2(numbers.length()).ceil()
xPrinterCount = 1
cursor = 0
spacing = 3
for y in (0..linesCount)
line = perLineWidth.times.map { " " }
spacing = spacing == 3 ? 4 : 3
printIndex = (perLineWidth / 2) - (spacing * xPrinterCount) / 2
for x in (0..xPrinterCount - 1)
if cursor >= numbers.length
break
end
if nodeIndex != -1 && cursor == nodeIndex
line[printIndex] = "%s%s%s" % [Colors::RED, numbers[cursor].to_s, Colors::STOP]
elsif rightBound != -1 && cursor > rightBound
line[printIndex] = "%s%s%s" % [Colors::BLUE, numbers[cursor].to_s, Colors::STOP]
else
line[printIndex] = numbers[cursor].to_s
end
cursor += 1
printIndex += spacing
end
print line.join()
xPrinterCount *= 2
print "\n"
end
end
heapify(numbers)
rightBound = numbers.length() - 1
while rightBound > 0
swap(numbers, 0, rightBound)
rightBound -= 1
siftDown(numbers, 0, rightBound)
end
return numbers
end
numbersCount = 14
maximalNumber = 10
numbers = numbersCount.times.map { Random.rand(maximalNumber) }
print numbers
print "\n---\n"
start = Time.now
sortedNumbers = heapsort(numbers)
finish = Time.now
heapSortTime = start - finish
start = Time.now
referenceSortedNumbers = numbers.sort()
finish = Time.now
referenceSortTime = start - finish
print "Reference sort: "
print referenceSortedNumbers
print "\n"
print "Reference sort time: %f\n" % referenceSortTime
print "Heap sort: "
print sortedNumbers
print "\n"
if DEMO == false
print "Heap sort time: %f\n" % heapSortTime
else
print "Disable DEMO for performance measure\n"
end
if sortedNumbers != referenceSortedNumbers
puts "Validation failed"
exit 1
else
puts "Validation success"
exit 0
end
```

Without visualization, this algorithm is not easy to understand, so the first thing I recommend is to write a function that will print the current view of the binary tree.

### Links

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/heapsort/heapsort.rb

### References

http://rosettacode.org/wiki/Sorting_algorithms/Heapsort

https://www.youtube.com/watch?v=LbB357_RwlY

https://habr.com/ru/company/otus/blog/460087/

https://ru.wikipedia.org/wiki/Пирамидальная_сортировка

https://neerc.ifmo.ru/wiki/index.php?title=Сортировка_кучей

https://wiki5.ru/wiki/Heapsort

https://wiki.c2.com/?HeapSort

https://ru.wikipedia.org/wiki/Дерево (структура данных)

https://ru.wikipedia.org/wiki/Куча (структура данных)

https://www.youtube.com/watch?v=2DmK_H7IdTo

https://www.youtube.com/watch?v=kU4KBD4NFtw

https://www.youtube.com/watch?v=DU1uG5310x0

https://www.youtube.com/watch?v=BzQGPA_v-vc

https://www.geeksforgeeks.org/array-representation-of-binary-heap/

https://habr.com/ru/post/112222/

https://www.cs.usfca.edu/~galles/visualization/BST.html

https://www.youtube.com/watch?v=EQzqHWtsKq4

https://medium.com/@dimko1/%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8-heapsort-796ba965018b

https://ru.wikibrief.org/wiki/Heapsort

https://www.youtube.com/watch?v=GUUpmrTnNbw