## 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

## …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?

## Selection Sort

Selection Sort – selection sort algorithm. Choice of what? But the minimum number!!!
The time complexity of the algorithm is O(n2)

The algorithm works as follows:

1. We loop through the array from left to right, remember the current starting index and the number by index, let’s call the number A
2. Inside the loop, we run another one to pass from left to right, looking for less than A
3. When we find a smaller one, remember the index, now the smaller one becomes the number A
4. When the inner loop ends, swap the number at the start index and the number A
5. After a full pass of the upper loop, we get a sorted array

Algorithm execution example:

``````Round 1
(29, 49, 66, 35, 7, 12, 80)
29 > 7
(7, 49, 66, 35, 29, 12, 80)
Round 1 ENDED
Round 2
(7, 49, 66, 35, 29, 12, 80)
49 > 35
35 > 29
29 > 12
(7, 12, 66, 35, 29, 49, 80)
Round 2 ENDED
Round 3
(7, 12, 66, 35, 29, 49, 80)
66 > 35
35 > 29
(7, 12, 29, 35, 66, 49, 80)
Round 3 ENDED
Round 4
(7, 12, 29, 35, 66, 49, 80)
(7, 12, 29, 35, 66, 49, 80)
Round 4 ENDED
Round 5
(7, 12, 29, 35, 66, 49, 80)
66 > 49
(7, 12, 29, 35, 49, 66, 80)
Round 5 ENDED
Round 6
(7, 12, 29, 35, 49, 66, 80)
(7, 12, 29, 35, 49, 66, 80)
Round 6 ENDED
Sorted: (7, 12, 29, 35, 49, 66, 80)
``````

Not finding an Objective-C implementation at Rosetta Code, wrote his self:

``````#include "SelectionSort.h"
#include <Foundation/Foundation.h>

@implementation SelectionSort
- (void)performSort:(NSMutableArray *)numbers
{
NSLog(@"%@", numbers);
for (int startIndex = 0; startIndex < numbers.count-1; startIndex++) {
int minimalNumberIndex = startIndex;
for (int i = startIndex + 1; i < numbers.count; i++) {
id lhs = [numbers objectAtIndex: minimalNumberIndex];
id rhs = [numbers objectAtIndex: i];
if ([lhs isGreaterThan: rhs]) {
minimalNumberIndex = i;
}
}
id temporary = [numbers objectAtIndex: minimalNumberIndex];
[numbers setObject: [numbers objectAtIndex: startIndex]
atIndexedSubscript: minimalNumberIndex];
[numbers setObject: temporary
atIndexedSubscript: startIndex];
}
NSLog(@"%@", numbers);
}

@end``````

You can build and run either on MacOS/Xcode, or on any operating system that supports GNUstep, for example, I'm building Clang on Arch Linux.
Assembly script:

``````clang SelectionSort.m \
main.m\
-lobjc \
`gnustep-config --objc-flags` \
`gnustep-config --objc-libs` \
-I /usr/include/GNUstepBase\
-I /usr/lib/gcc/x86_64-pc-linux-gnu/12.1.0/include/ \
-lgnustep-base \
-o SelectionSort \``````

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

## Counting Sort

Counting sort – counting sort algorithm. What? Yes! Just like that!

The algorithm involves at least two arrays, the first is a list of integers to be sorted, the second is an array of size = (maximum number – minimum number) + 1, initially containing only zeros. Next, the numbers from the first array are sorted out, the index in the second array is obtained by the element-number, which is incremented by one. After going through the entire list, we will get a completely filled second array with the number of repetitions of numbers from the first. The algorithm has a serious overhead – the second array also contains zeros for numbers that are not in the first list, the so-called. memory overhead.

After getting the second array, iterate over it and write the sorted version of the number by index, decrementing the counter to zero. Initially, the zero counter is ignored.

An unoptimized example of how the counting sort algorithm works:

1. Input array 1,9,1,4,6,4,4
2. Then the array to count will be 0,1,2,3,4,5,6,7,8,9 (minimum number 0, maximum 9)
3. With total counters 0,2,0,0,3,0,1,0,0,1
4. Total sorted array 1,1,4,4,4,6,9

Algorithm code in Python 3:

``````print("Counting Sort")

numbers = [42, 89, 69, 777, 22, 35, 42, 69, 42, 90, 777]

minimal = min(numbers)
maximal = max(numbers)
countListRange = maximal - minimal
countListRange += 1
countList = [0] * countListRange

print(numbers)
print(f"Minimal number: {minimal}")
print(f"Maximum number: {maximal}")
print(f"Count list size: {countListRange}")

for number in numbers:
index = number - minimal
countList[index] += 1

replacingIndex = 0
for index, count in enumerate(countList):
for i in range(count):
outputNumber = minimal + index
numbers[replacingIndex] = outputNumber
replacingIndex += 1

print(numbers)``````

Due to the use of two arrays, the time complexity of the algorithm is O(n + k)

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

## Bogosort

Pseudo sort or swamp sort, one of the most useless sorting algorithms.

It works like this:
1. Input is an array of numbers
2. An array of numbers is shuffled randomly (shuffle)
3. Checking if the array is sorted
4. If not sorted, then the array is shuffled again
5. All this action is repeated until the array is sorted randomly.

As you can see, the performance of this algorithm is terrible, smart people think that even O(n * n!) there is a chance to get stuck throwing dice for the glory of the god of chaos for many years, the array will not be sorted, or maybe sorted?

### Implementation

For the TypeScript implementation, I needed to implement the following functions:
1. Shuffling an array of objects
2. Comparing arrays
3. Generating a random number between zero and a number (sic!)
4. Seal of progress, as the sorting seems to run indefinitely

Below is the TypeScript implementation code:

``````const printoutProcess = (numbers: number[], sortedNumbers: number[], numberOfRuns: number) => console.log(`Still trying to sort: \${numbers}, current shuffle \${sortedNumbers}, try number: \${numberOfRuns}`);
const randomInteger = (maximal: number) => Math.floor(Math.random() * maximal);
const isEqual = (lhs: any[], rhs: any[]) => lhs.every((val, index) => val === rhs[index]);
const shuffle = (array: any[]) => {
for (var i = 0; i < array.length; i++) { var destination = randomInteger(array.length-1); vartemp = array[i]; array[i] = array[destination]; array[destination] = temp; } } let numbers: number[] = Array.from({length: 10}, ()=>randomInteger(10));
const originalNumbers = [...numbers];
const sortedNumbers = [...numbers].sort();

let numberOfRuns = 1;

do {
if (numberOfRuns % 1000 == 0) {
printoutProcess(originalNumbers, numbers, numberOfRuns);
}
shuffle(numbers);
numberOfRuns++;
} while (isEqual(numbers, sortedNumbers) == false)

console.log(`Success!`);
console.log(`Run number: \${numberOfRuns}`)
console.log(`Original numbers: \${originalNumbers}`);
console.log(`Current numbers: \${originalNumbers}`);
console.log(`Sorted numbers: \${sortedNumbers}`);``````

You can use VSCode and kakumei’s TypeScript Debugger plugin for debugging.

### How long

Output of the algorithm:

``````Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 2,9,7,8,0,7,4,5,2 ,5, try number: 144000
src/bogosort.ts:1
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 8,7,0,2,4,7,2,5,9,5, try number: 145000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 7,5,2,4,9,8,0,5,2,7, try number: 146000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 0,2,7,4,9,5,7,5,8,2, try number: 147000
src/bogosort.ts:2
Still trying to sort: 5,4,8,7,5,0,2,9,7,2, current shuffle 5,9,7,8,5,4,2,7,0,2, try number: 148000
src/bogosort.ts:2
Success!
src/bogosort.ts:24
Run number: 148798
src/bogosort.ts:25
Original numbers: 5,4,8,7,5,0,2,9,7,2
src/bogosort.ts:26
Current numbers: 5,4,8,7,5,0,2,9,7,2
src/bogosort.ts:27
Sorted numbers: 0,2,2,4,5,5,7,7,8,9``````

For an array of 10 numbers, Bogosort shuffled the original array 148798 times, too much right?
The algorithm can be used as a training one, to understand the capabilities of the language with which to work on the market. Personally, I was surprised to learn that vanilla JS and TS still do not have their own algorithm for shuffling arrays, generating an integer in a range, accessing object hashes for quick comparison.