## Binary Insertion Sort

Binary Insertion Sort is a variant of insertion sort in which the insertion position is determined using a binary search. The time complexity of the algorithm is O(n2)

The algorithm works like this:

1. Loop from zero to end of list
2. In the loop, a number is selected for sorting, the number is stored in a separate variable
3. Binary search looks for the index to insert this number against the numbers on the left
4. After finding the index, the numbers on the left are shifted one position to the right, starting at the insertion index. The process will erase the number to be sorted.
5. The previously stored number is inserted at the insertion index
6. At the end of the loop, the entire list will be sorted

During a binary search, it is possible that the number will not be found, but the index is not returned. Due to the peculiarities of the binary search, the number closest to the desired one will be found, then to return the index it will be necessary to compare it with the desired one, if the desired one is less, then the desired one should be at the index on the left, and if it is greater or equal, then on the right.

Source code in Go:

``````package main

import (
"fmt"
"math/rand"
"time"
)

const numbersCount = 20
const maximalNumber = 100

func binarySearch(numbers []int, item int, low int, high int) int {
for high > low {
center := (low + high) / 2
if numbers[center] < item { low = center + 1 } else if numbers[center] > item {
high = center - 1
} else {
return center
}
}

if numbers[low] < item {
return low + 1
} else {
return low
}
}

func main() {
rand.Seed(time.Now().Unix())
var numbers [numbersCount]int
for i := 0; i < numbersCount; i++ {
numbers[i] = rand.Intn(maximalNumber)
}
fmt.Println(numbers)

for i := 1; i < len(numbers); i++ { searchAreaLastIndex := i - 1 insertNumber := numbers[i] insertIndex := binarySearch(numbers[:], insertNumber, 0, searchAreaLastIndex) for x := searchAreaLastIndex; x >= insertIndex; x-- {
numbers[x+1] = numbers[x]
}
numbers[insertIndex] = insertNumber
}
fmt.Println(numbers)
}
``````

https://gitlab.com/demensdeum/algorithms/-/blob/master/sortAlgorithms/binaryInsertionSort/binaryInsertionSort.go

## Shell Sort

Shell Sort is a variant of sorting by inserts with preliminary combing of an array of numbers.

We need to remember how insertion sort works:

1. The loop starts from zero to the end of the loop, thus the array is divided into two parts
2. For the left side, the second loop is started, comparing elements from right to left, the smaller element on the right is omitted until there is a smaller element on the left
3. At the end of both cycles, we get a sorted list

Once in a while, computer scientist Donald Shell wondered how to improve the insertion sort algorithm. He came up with the idea to preliminarily go through the array with two cycles, but at a certain distance, gradually reducing the “comb” until it turns into a regular insertion sort algorithm. Everything is really so simple, no pitfalls, we add another one to the two cycles from above, in which we gradually reduce the size of the “comb”. The only thing that will need to be done is to check the distance when comparing so that it does not go beyond the array.

A really interesting topic is the choice of sequence for changing the length of the comparison at each iteration of the first loop. It is interesting for the reason that the performance of the algorithm depends on it.

A table of known variants and time complexity can be viewed here:
https://en.wikipedia.org/wiki/Shellsort#Gap_sequences

Different people were engaged in calculating the ideal distance, so, apparently, this topic was interesting to them. Couldn’t they just fire up Ruby, call the fastest sort() algorithm?

In general, these strange people wrote dissertations on the topic of calculating the distance / gap of the “comb” for the Shell algorithm. I just used the results of their work and checked 5 types of sequences, Hibbard, Knuth-Pratt, Ciura, Sedgewick.

``````from typing import List
import time
import random
from functools import reduce
import math

DEMO_MODE = False

if input("Demo Mode Y/N? ").upper() == "Y":
DEMO_MODE = True

class Colors:
BLUE = '\033[94m'
RED = '\033[31m'
END = '\033[0m'

def swap(list, lhs, rhs):
list[lhs], list[rhs] = list[rhs], list[lhs]
return list

def colorPrintoutStep(numbers: List[int], lhs: int, rhs: int):
for index, number in enumerate(numbers):
if index == lhs:
print(f"{Colors.BLUE}", end = "")
elif index == rhs:
print(f"{Colors.RED}", end = "")
print(f"{number},", end = "")
if index == lhs or index == rhs:
print(f"{Colors.END}", end = "")
if index == lhs or index == rhs:
print(f"{Colors.END}", end = "")
print("\n")
input(">")

def ShellSortLoop(numbers: List[int], distanceSequence: List[int]):
distanceSequenceIterator = reversed(distanceSequence)
while distance:= next(distanceSequenceIterator, None):
for sortArea in range(0, len(numbers)):
for rhs in reversed(range(distance, sortArea + 1)):
lhs = rhs - distance
if DEMO_MODE:
print(f"Distance: {distance}")
colorPrintoutStep(numbers, lhs, rhs)
if numbers[lhs] > numbers[rhs]:
swap(numbers, lhs, rhs)
else:
break

def ShellSort(numbers: List[int]):
global ShellSequence
ShellSortLoop(numbers, ShellSequence)

def HibbardSort(numbers: List[int]):
global HibbardSequence
ShellSortLoop(numbers, HibbardSequence)

def ShellPlusKnuttPrattSort(numbers: List[int]):
global KnuttPrattSequence
ShellSortLoop(numbers, KnuttPrattSequence)

def ShellPlusCiuraSort(numbers: List[int]):
global CiuraSequence
ShellSortLoop(numbers, CiuraSequence)

def ShellPlusSedgewickSort(numbers: List[int]):
global SedgewickSequence
ShellSortLoop(numbers, SedgewickSequence)

def insertionSort(numbers: List[int]):
global insertionSortDistanceSequence
ShellSortLoop(numbers, insertionSortDistanceSequence)

def defaultSort(numbers: List[int]):
numbers.sort()

def measureExecution(inputNumbers: List[int], algorithmName: str, algorithm):
if DEMO_MODE:
print(f"{algorithmName} started")
numbers = inputNumbers.copy()
startTime = time.perf_counter()
algorithm(numbers)
endTime = time.perf_counter()
print(f"{algorithmName} performance: {endTime - startTime}")

def sortedNumbersAsString(inputNumbers: List[int], algorithm) -> str:
numbers = inputNumbers.copy()
algorithm(numbers)
return str(numbers)

if DEMO_MODE:
maximalNumber = 10
numbersCount = 10
else:
maximalNumber = 10
numbersCount = random.randint(10000, 20000)

randomNumbers = [random.randrange(1, maximalNumber) for i in range(numbersCount)]

ShellSequenceGenerator = lambda n: reduce(lambda x, _: x + [int(x[-1]/2)], range(int(math.log(numbersCount, 2))), [int(numbersCount / 2)])
ShellSequence = ShellSequenceGenerator(randomNumbers)
ShellSequence.reverse()
ShellSequence.pop()

HibbardSequence = [
0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095,
8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575,
2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727,
268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591
]

KnuttPrattSequence = [
1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720,
797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733,
1743392200, 5230176601, 15690529804, 47071589413
]

CiuraSequence = [
1, 4, 10, 23, 57, 132, 301, 701, 1750, 4376,
10941, 27353, 68383, 170958, 427396, 1068491,
2671228, 6678071, 16695178, 41737946, 104344866,
260862166, 652155416, 1630388541
]

SedgewickSequence = [
1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905,
8929, 16001, 36289, 64769, 146305, 260609, 587521,
1045505, 2354689, 4188161, 9427969, 16764929, 37730305,
67084289, 150958081, 268386305, 603906049, 1073643521,
2415771649, 4294770689, 9663381505, 17179475969
]

insertionSortDistanceSequence = [1]

algorithms = {
"Default Python Sort": defaultSort,
"Shell Sort": ShellSort,
"Shell + Hibbard" : HibbardSort,
"Shell + Prat, Knutt": ShellPlusKnuttPrattSort,
"Shell + Ciura Sort": ShellPlusCiuraSort,
"Shell + Sedgewick Sort": ShellPlusSedgewickSort,
"Insertion Sort": insertionSort
}

for name, algorithm in algorithms.items():
measureExecution(randomNumbers, name, algorithm)

reference = sortedNumbersAsString(randomNumbers, defaultSort)

for name, algorithm in algorithms.items():
if sortedNumbersAsString(randomNumbers, algorithm) != reference:
print("Sorting validation failed")
exit(1)

print("Sorting validation success")
exit(0)
``````
In my implementation, for a random set, the fastest numbers are the Sedgwick and Hibbard gaps.

### mypy

I would also like to mention the static typing analyzer for Python 3 – mypy. Helps to cope with the problems inherent in languages ​​with dynamic typing, namely, it eliminates the possibility of sticking something where it is not necessary.
As experienced programmers say, “static typing is not needed when you have a team of professionals”, someday we will all become professionals, we will write code in complete unity and understanding with machines, but for now you can use similar utilities and languages ​​with static typing.

## Double Selection Sort

Double Selection Sort – a subspecies of sorting by selection, it seems like it should be accelerated twice. The vanilla algorithm double loops through the list of numbers, finds the minimum number, and swaps it with the current digit pointed to by the loop at the level above. Double selection sort, on the other hand, looks for the minimum and maximum number, then it replaces the two digits indicated by the loop at the level above – two numbers on the left and on the right. All this orgy ends when the cursors of numbers to replace meet in the middle of the list, as a result, sorted numbers are obtained to the left and right of the visual center. The time complexity of the algorithm is similar to Selection Sort – O(n2), but supposedly there is a 30% speedup.

### Corner case

Already at this stage, you can imagine the moment of collision, when the number of the left cursor (the minimum number) will point to the maximum number in the list, then the minimum number is permuted, the permutation of the maximum number immediately breaks down. Therefore, all implementations of the algorithm contain a check of such cases, replacement of indices with correct ones. In my implementation, one check was enough:

``````if (leftCursor == maximalNumberIndex) {
maximalNumberIndex = minimalNumberIndex;
}``````

### Cito implementation

Cito is a lib language, a translator language. You can write on it for C, C++, C#, Java, JavaScript, Python, Swift, TypeScript, OpenCL C, while knowing absolutely nothing about these languages. The source code in the Cito language is translated into the source code in the supported languages, then you can use it as a library, or directly by correcting the generated code by hand. A kind of Write once – translate to anything.
Double Selection Sort – Cito:

``````public class DoubleSelectionSort
{
public static int[] sort(int[]# numbers, int length)
{
int[]# sortedNumbers = new int[length];
for (int i = 0; i < length; i++) {
sortedNumbers[i] = numbers[i];
}
for (int leftCursor = 0; leftCursor < length / 2; leftCursor++) {
int minimalNumberIndex = leftCursor;
int minimalNumber = sortedNumbers[leftCursor];

int rightCursor = length - (leftCursor + 1);
int maximalNumberIndex = rightCursor;
int maximalNumber = sortedNumbers[maximalNumberIndex];

for (int cursor = leftCursor; cursor <= rightCursor; cursor++) { int cursorNumber = sortedNumbers[cursor]; if (minimalNumber > cursorNumber) {
minimalNumber = cursorNumber;
minimalNumberIndex = cursor;
}
if (maximalNumber < cursorNumber) {
maximalNumber = cursorNumber;
maximalNumberIndex = cursor;
}
}

if (leftCursor == maximalNumberIndex) {
maximalNumberIndex = minimalNumberIndex;
}

int fromNumber = sortedNumbers[leftCursor];
int toNumber = sortedNumbers[minimalNumberIndex];
sortedNumbers[minimalNumberIndex] = fromNumber;
sortedNumbers[leftCursor] = toNumber;

fromNumber = sortedNumbers[rightCursor];
toNumber = sortedNumbers[maximalNumberIndex];
sortedNumbers[maximalNumberIndex] = fromNumber;
sortedNumbers[rightCursor] = toNumber;
}
return sortedNumbers;
}
}
``````

## Cocktail Shaker Sort

Cocktail Shaker Sort – sorting in a shaker, a variant of bidirectional bubble sort.
The algorithm works like this:

1. Select the starting direction of the iteration in the loop (usually left-to-right)
2. Next, the numbers are checked in pairs
3. If the next element is larger, they are swapped
4. At the end, the iteration process restarts with the direction reversed
5. Iterates until there are no more permutations

The time complexity of the algorithm is similar to the bubble one – O(n2) .

An example implementation in PHP:

``````#!/usr/bin/env php
<?php

function cocktailShakeSort(\$numbers)
{
echo implode(",", \$numbers),"\n";
\$direction = false;
\$sorted = false;
do {
\$direction = !\$direction;
\$firstIndex = \$direction == true ? 0 : count(\$numbers) - 1;
\$lastIndex = \$direction == true ? count(\$numbers) - 1 : 0;

\$sorted = true;
for(
\$i = \$firstIndex;
\$direction == true ? \$i < \$lastIndex : \$i > \$lastIndex;
\$direction == true ? \$i++ : \$i--
) {
\$lhsIndex = \$direction ? \$i : \$i - 1;
\$rhsIndex = \$direction ? \$i + 1 : \$i;

\$lhs = \$numbers[\$lhsIndex];
\$rhs = \$numbers[\$rhsIndex];

if (\$lhs > \$rhs) {
\$numbers[\$lhsIndex] = \$rhs;
\$numbers[\$rhsIndex] = \$lhs;
\$sorted = false;
}
}
} while (\$sorted == false);

echo implode(",", \$numbers);
}

\$numbers = [2, 1, 4, 3, 69, 35, 55, 7, 7, 2, 6, 203, 9];
cocktailShakeSort(\$numbers);

?>``````

https://gitlab .com/demensdeum/algorithms/-/blob/master/sortAlgorithms/cocktailShakerSort/cocktailShakerSort.php

## FatBoySize – disk usage information tool

FatBoySize – disk usage information tool, it shows directories, files sizes in terminal.
Supports any OS that support Python 3.

```Usage: python3 fbs.py Verbose mode 1: python3 fbs.py -v Verbose mode 2: python3 fbs.py --version ```

Right now it works only for current terminal path.

Result example:
```python3 ~/Sources/my/fatboysize/fbs.py .local -> 145. GB Downloads -> 103. GB .cache -> 37.0 GB .android -> 11.6 GB Sources -> 8.63 GB ```

https://gitlab.com/demensdeum/fatboysize/

## …And Primus for All

In this note I will describe the launch of Steam games on the Linux distribution Arch Linux in the configuration of an Intel + Nvidia laptop

### Counter-Strike: Global Offensive

The only configuration that worked for me is Primus-vk + Vulkan.

Install the required packages:
`pacman -S vulkan-intel lib32-vulkan-intel nvidia-utils lib32-nvidia-utils vulkan-icd-loader lib32-vulkan-icd-loader primus_vk`

Next, add launch options for Counter-Strike: Global Offensive:
`pvkrun %command% -vulkan -console -fullscreen`

Should work!

### Sid Meier’s Civilization VI

Works in conjunction – Primus + OpenGL + LD_PRELOAD.

Install the Primus package:
`pacman -S primus`

Next, add launch options for Sid Meier’s Civilization VI:
`LD_PRELOAD='/usr/lib/libfreetype.so.6:/usr/lib/libbrotlicommon.so.1:/usr/lib/libbrotlidec.so.1' primusrun %command%`

LD_PRELOAD pushes the Freetype compression and font libraries.

### Dota 2

Works in conjunction – Primus + OpenGL + removal of locks at startup.

Install the Primus package:
`pacman -S primus`

Next, add launch options for Dota 2:
`primusrun %command% -gl -console`

If the game doesn’t start with fcntl(5) for /tmp/source_engine_2808995433.lock failed, then try deleting the /tmp/source_engine_2808995433.lock file
`rm /tmp/source_engine_2808995433.lock`
Usually the lock file is left over from the last game session unless the game was closed naturally.

### How to check?

The easiest way to check the launch of applications on a discrete Nvidia graphics card is through the nvidia-smi utility:

For games on the Source engine, you can check through the game console using the mat_info command:

## Sleep Sort

Sleep Sort – sleep sorting, another representative of deterministic strange sorting algorithms.

Works like this:

1. Iterates through a list of elements
2. Run a separate thread for each loop
3. The thread sleeps (sleep) the thread for a while – the value of the element and output the value after sleep
4. At the end of the loop, wait until the end of the thread’s longest sleep, display a sorted list

An example code for the sleep sort algorithm in C:

``````#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

typedef struct {
int number;

void *sortNumber(void *args) {
usleep(number * 1000);
printf("%d", number);
return NULL;
}

int main(int argc, char *argv[]) {
const int numbers[] = {2, 42, 1, 87, 7, 9, 5, 35};
const int length = sizeof(numbers) / sizeof(int);

int maximal = 0;

printf("Sorting: ");
if (maximum < number) {
maximal = number;
}
}
printf("\n");
printf("Sorted: ");
printf("\n");
return 0;
}
``````

In this implementation, I used the usleep function on microseconds with the value multiplied by 1000, i.e. in milliseconds.
The time complexity of the algorithm is O(v. long)

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

## Stalin Sort

Stalin Sort – sorting right through, one of the sorting algorithms with data loss.
The algorithm is very efficient and efficient, O(n) time complexity.

It works like this:

1. Loop through the array, comparing the current element with the next
2. If the next element is less than the current one, then delete it
3. As a result, we get a sorted array in O(n)

An example of the output of the algorithm:

``````Numbers: [1, 3, 2, 4, 6, 42, 4, 8, 5, 0, 35, 10]
Gulag: [1, 3, 2, 4, 6, 42, 4, 8, 5, 0, 35, 10]
Element 2 sent to Gulag
Element 4 sent to Gulag
Element 8 sent to Gulag
Element 5 sent to Gulag
Element 0 sent to Gulag
Element 35 sent to Gulag
Element 10 sent to Gulag
Numbers: [1, 3, 4, 6, 42]
Gulag: [2, 4, 8, 5, 0, 35, 10]
``````

Python 3 code:

``````numbers = [1, 3, 2, 4, 6, 42, 4, 8, 5, 0, 35, 10]
gulag = []

print(f"Numbers: {numbers}")
print(f"Gulag: {numbers}")

i = 0
maximal = numbers[0]

while i < len(numbers):
element = numbers[i]
if maximal > element:
print(f"Element {element} sent to Gulag")
gulag append(element)
del numbers[i]
else:
maximal = element
i += 1

print(f"Numbers: {numbers}")
print(f"Gulag: {gulag}")
``````

Of the disadvantages, data loss can be noted, but if you move to a utopian, ideal, sorted list in O(n), how else?