How to run Unreal Tournament 99 on MacBook M1

macOS M1 Ventura

If you’re a dedicated Unreal Tournament 99 fan like me, you’ll want to run the game on the latest operating systems and hardware. I have successfully run Unreal Tournament 99 on an M1 Macbook Pro running macOS Ventura 13.0.1.

  1. To run the game under macOS for the M1 processor you need:
  2. Download the version from the repository, https://github.com/OldUnreal/UnrealTournamentPatches/releases for macOS.
  3. Drop UnrealTournament.app to /Applications
  4. Create an Unreal Tournament folder in ~/Library/Application Support/
  5. Copy the Windows versions of the Maps, Sounds, Textures, Music folder to ~/Library/Application Support/Unreal Tournament
  6. Delete the files LadderFonts.utx, UWindowFonts.utx from the folder ~/Library/Application Support/Unreal Tournament/Textures
  7. Run UnrealTournament.app from /Applications, enjoy the frags!

The penultimate step is needed to display the correct fonts, the original ones are displayed too small.
After starting, configure the screen resolution, keyboard, font size in the GUI, and other necessary settings.

Unreal Tournament macOS Ventura M1

Windows 11

Also, for dessert, the launch of Unreal Tournament 99 on Windows 11, the game works immediately after installation, without additional shamanism, but there are problems with displaying the GUI, the performance of an outdated D3D renderer. Therefore, it is better to use the patched version.

  1. The launch process is very similar to that for macOS:
  2. Download version from https://github.com/OldUnreal/UnrealTournamentPatches/releases repository for Windows, for example in zip.
  3. Unpack and replace files over the current Unreal Tournament.
  4. Run the game from [Game folder]/System/UnrealTournament.exe

I am glad that fans continue to support such a masterpiece and there is an opportunity to play even on modern hardware.

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.

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:

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

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

  1. Building a binary search tree
  2. 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

TreeSort Algorithm Explained and Implemented with Examples in Java | Sorting Algorithms | Geekific – YouTube

Tree sort – YouTube

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

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

Tree Sort – GeeksforGeeks

Tree sort – Wikipedia

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:

  1. Run a loop with counter i up to the maximum number of characters in the number
  2. 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
  3. The character is converted to a number
  4. Select a bucket by index – number, put the whole number there
  5. After finishing iterating over numbers, convert all buckets back to a list of numbers
  6. Get numbers sorted by digit
  7. 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:

  1. Heap creation
  2. Sifting algorithm (heapify)
  3. 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

Bumblebee All Troubles

Recently, it turned out that users of modern Nvidia GPUs under Arch Linux do not need to use the bumblebee package at all, for example, for me it did not detect an external monitor when connected. I recommend removing the bumblebee package and all related packages, and installing prime using the instructions on the Arch Wiki.
Next, to launch all games on Steam and 3D applications, add prime-run, for Steam this is done like this prime-run %command% in additional launch options.
To check the correctness, you can use glxgears, prime-run glxgears.
https://bbs.archlinux.org/viewtopic.php? pid=2048195#p2048195

Quicksort

Quicksort is a divide-and-conquer sorting algorithm. Recursively, in parts, parse the array of numbers, setting the numbers in the smaller and larger order from the selected pivot element, insert the pivot element itself into the hot-point between them. After a few recursive iterations, you’ll end up with a sorted list. Time complexity O(n2).

Scheme:

  1. We start with the fact that we get a list of elements outside, sorting boundaries. In the first step, the sort boundaries will be from start to finish.
  2. Check that the boundaries of the beginning and end do not intersect, if this happens, then it’s time to finish
  3. Select some element from the list, call it pivot
  4. Shift to the right to the end to the last index, so as not to interfere
  5. Create a counter of *smaller numbers* while equal to zero
  6. Loop through the list from left to right, up to and including the last index where the anchor element is located
  7. Each element is compared to the pivot
  8. If it is less than the reference, then we swap it in places according to the index of the counter of smaller numbers. Increment the counter of smaller numbers.
  9. When the cycle reaches the anchor element, we stop, swap the anchor element with the element by the counter of smaller numbers.
  10. We run the algorithm separately for the left smaller part of the list, and separately for the right most part of the list.
  11. As a result, all recursive iterations will start to stop due to the check in paragraph 2
  12. Get sorted list

Quicksort was invented by the scientist Charles Antony Richard Hoare at Moscow State University, having learned Russian, he studied computer translation, as well as probability theory at the Kolmogorov school. In 1960, due to a political crisis, he left the Soviet Union.

An example implementation in Rust:

extern crate rand;

use rand::Rng;

fn swap(numbers: &mut [i64], from: usize, to: usize) {
    let temp = numbers[from];
    numbers[from] = numbers[to];
    numbers[to] = temp;
}

fn quicksort(numbers: &mut [i64], left: usize, right: usize) {
    if left >= right {
        return
    }
    let length = right - left;
    if length <= 1 {
        return
    }
    let pivot_index = left + (length / 2);
    let pivot = numbers[pivot_index];

    let last_index = right - 1;
    swap(numbers, pivot_index, last_index);

    let mut less_insert_index = left;

    for i in left..last_index {
        if numbers[i] < pivot {
            swap(numbers, i, less_insert_index);
            less_insert_index += 1;
        }
    }
    swap(numbers, last_index, less_insert_index);
    quicksort(numbers, left, less_insert_index);
    quicksort(numbers, less_insert_index + 1, right);
}

fn main() {
    let mut numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    let mut reference_numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

    let mut rng = rand::thread_rng();
    for i in 0..numbers.len() {
        numbers[i] = rng.gen_range(-10..10);
        reference_numbers[i] = numbers[i];
    }

    reference_numbers.sort();

  println!("Numbers           {:?}", numbers);
  let length = numbers.len();
  quicksort(&mut numbers, 0, length);
  println!("Numbers           {:?}", numbers);
  println!("Reference numbers {:?}", reference_numbers);

  if numbers != reference_numbers {
    println!("Validation failed");
    std::process::exit(1);
  }
  else {
    println!("Validation success!");
    std::process::exit(0);
  }
}

If you don't understand anything, I suggest watching a video by Rob Edwards from the San Diego State University https://www.youtube.com/watch?v=ZHVk2blR45Q it most simply, step by step, shows the essence and implementation of the algorithm.

Links

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

References

https://www.youtube.com/watch?v=4s-aG6yGGLU
https://www.youtube.com/watch?v=ywWBy6J5gz8
https://www.youtube.com/watch?v=Hoixgm4-P4M
https://ru.wikipedia.org/wiki/Быстрая_сортировка
https://www.youtube.com/watch?v=Hoixgm4-P4M
https://www.youtube.com/watch?v=XE4VP_8Y0BU
https://www.youtube.com/watch?v=MZaf_9IZCrc
https://www.youtube.com/watch?v=ZHVk2blR45Q
http://rosettacode.org/wiki/Sorting_algorithms/Quicksort
https://www.youtube.com/watch?v=4s-aG6yGGLU
https://www.youtube.com/watch?v=dQw4w9WgXcQ
https://www.youtube.com/watch?v=maibrCbZWKw
https://www.geeksforgeeks.org/quick-sort/
https://www.youtube.com/watch?v=uXBnyYuwPe8