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);

?>

Links

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

Sources

https://www.youtube.com/watch?v=njClLBoEbfI
https://www.geeksforgeeks.org/cocktail-sort/< br />
https://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort

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 <pthread.h>
#include <unistd.h>

typedef struct {
    int number;
} ThreadPayload;

void *sortNumber(void *args) {
    ThreadPayload *payload = (ThreadPayload*) args;
    const int number = payload->number;
    free(payload);
    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;
    pthread_t maximalThreadID;

    printf("Sorting: ");
    for (int i = 0; i < length; i++) { pthread_t threadID; int number = numbers[i]; printf("%d", number); ThreadPayload *payload = malloc(sizeof(ThreadPayload)); payload->number = number;
        pthread_create(&threadID, NULL, sortNumber, (void *) payload);
        if (maximum < number) {
            maximal = number;
            maximalThreadID = threadID;
        }
    }
    printf("\n");
    printf("Sorted: ");
    pthread_join(maximalThreadID, NULL);
    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)

Links

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

Sources

https://codoholicconfessions.wordpress.com/2017 /05/21/strangest-sorting-algorithms/
https://twitter.com/javascriptdaily/status/856267407106682880?lang= en
https:// stackoverflow.com/questions/6474318/what-is-the-time-complexity-of-the-sleep-sort

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?

Links

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

Sources

https://github.com/gustavo-depaula/stalin-sort
https://www.youtube.com/shorts/juRL-Xn- E00
https://www.youtube.com/watch?v=L78i2YcyYfk

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 \

Links

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

Sources

https://rosettacode.org/wiki/Sorting_algorithms/Selection_sort
https://ru.wikipedia.org/wiki/Сортировка_выбором
https://en.wikipedia.org/wiki/Selection_sort
https://www.youtube.com/watch?v=LJ7GYbX7qpM

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)

Links

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

Sources

https://www.youtube.com/watch?v=6dk_csyWif0
https://www.youtube.com/watch?v=OKd534EWcdk
https://en.wikipedia.org/wiki/Counting_sort
https://rosettacode.org/wiki/Sorting_algorithms/Counting_sort
https://pro-prof.com/forums/topic/%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC-%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8-%D0%BF%D0%BE%D0%B4%D1%81%D1%87%D0%B5%D1%82%D0%BE%D0%BC

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.

Links

https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/bogosort
https://www.typescriptlang.org/
https://marketplace.visualstudio.com/items?itemName= kakumei.ts-debug

Sources

https://www.youtube.com/watch?v=r2N3scbd_jg
https://en.wikipedia.org/wiki/Bogosort

RGB Image to Grayscale

In this article I will describe algorithm of converting RGB image buffer to Grayscale
And this is done quite simply, each pixel of the color channel of the buffer is converted according to a certain formula, and the output is a gray image.
Average method:

const average = (red + green + blue) / 3;
red = average;
green = average;
blue = average;

Add the 3 color channels and divide by 3.

However, there is another method – the weighted average method, it takes into account the human color perception:

const luminance = 0.2126 * red + 0.7152 * green + 0.0722 * blue;
red = luminance;
green = luminance;
blue = luminance;

What is the best method to use? Choose one that suits you better for a particular task. Next, a comparison of methods using a test color grid:

Example JavaScript + HTML 5

function rgb2grayscale(
    image,
    canvas,
    weightedAverage
) {
    const context = canvas.getContext('2d');

    const imageWeight = image.width;
    const imageHeight = image.height;

    canvas.width = imageWeight;
    canvas.height = imageHeight;

    context.drawImage(image, 0, 0);

    let pixels = context
        .getImageData(
            0,
            0,
            imageWeight,
            imageHeight
        );

    for (let y = 0; y & lt; pixels.height; y++) {
        for (let x = 0; x & lt; pixels.width; x++) {
            const i = (y * 4) * pixels.width + x * 4;

            let red = pixels.data[i];
            let green = pixels.data[i + 1];
            let blue = pixels.data[i + 2]

            const average = (red + green + blue) / 3;
            const luminance = 0.2126 * red +
                0.7152 * green +
                0.0722 * blue;

            red = weightedAverage ? luminance : average;
            green = weightedAverage ? luminance : average;
            blue = weightedAverage ? luminance : average;

            pixels.data[i] = red;
            pixels.data[i + 1] = green;
            pixels.data[i + 2] = blue;
        }
    }
    context
        .putImageData(
            pixels,
            0,
            0,
            0,
            0,
            pixels.width,
            pixels.height
        );
}

References

https://www.baeldung.com/cs/convert-rgb-to-grayscale
https://twitter.com/mudasobwa/status/1528046455587495940
https://rosettacode.org/wiki/Grayscale_image

Links

http://papugi.demensdeum.repl.co/

Thanks

Thanks to Aleksei Matiushkin (https://twitter.com/mudasobwa) for showing Rosetta Code

Longest Common Substring

In this article I will describe an algorithm for solving the longest common substring. Suppose we try to decipher the encrypted binary data, first try to find the common patterns by searching the largest substring.
The input string for example: adasDATAHEADER??jpjjwerthhkjbcvkDATAHEADER??kkasdf
We are looking for a line repeated twice: DATAHEADER??

Prefixes

To begin write method for comparing prefixes of two rows, let returns the resulting string in which a left prefix symbols are the symbols of the right prefix.
For example, for strings:


        val lhs = "asdfWUKI"
        val rhs = "asdfIKUW"

The resulting string – asdf
Example of Kotlin:


fun longestPrefix(lhs: String, rhs: String): String {
        val maximalLength = min(lhs.length-1, rhs.length -1)
        for (i in 0..maximalLength) {
            val xChar = lhs.take(i)
            val yChar = rhs.take(i)
                if (xChar != yChar) {
                    return lhs.substring(0, i-1)
                }
        }
        return lhs.substring(0,maximalLength)
}

Brute Force

When it is impossible for a good, should resort to brute force. Using the method longestPrefix pass on row two cycles, the first line takes from i to the end of the second i + 1 to the end, transmits them to the search for the largest prefix. The time complexity of the algorithm is approximately equal to O (n ^ 2) ~ O (n * ^ 3).
Example of Kotlin:


fun searchLongestRepeatedSubstring(searchString: String): String {
        var longestRepeatedSubstring = ""
        for (x in 0..searchString.length-1) {
            val lhs = searchString.substring(x)
            for (y in x+1..searchString.length-1) {
                val rhs = searchString.substring(y)
                val longestPrefix = longestPrefix(lhs, rhs)
                if (longestRepeatedSubstring.length < longestPrefix.length) {
                    longestRepeatedSubstring = longestPrefix
                }
            }
        }
        return longestRepeatedSubstring
}

Suffix array

For a more elegant solution, we need a tool - a data structure called "suffix array." This data structure is an array of substrings filled in a loop, where every substring starts the next character string to the end.
For example for a row:


adasDATAHEADER??

Suffix array looks like this:


adasDATAHEADER??
dasDATAHEADER??
asDATAHEADER??
sDATAHEADER??
DATAHEADER??
ATAHEADER??
TAHEADER??
AHEADER??
HEADER??
EADER??
ADER??
DER??
ER??
R??
??
?

Solve sorting

Sort the suffix array, and then go through all the elements of the cycle where the left hand (lhs) the current item on the right (rhs) and calculate the next longest prefix using longestPrefix method.
Example of Kotlin:


fun searchLongestRepeatedSubstring(searchString: String): String {
    val suffixTree = suffixArray(searchString)
    val sortedSuffixTree = suffixTree.sorted()

    var longestRepeatedSubstring = ""
    for (i in 0..sortedSuffixTree.count() - 2) {
        val lhs = sortedSuffixTree[i]
        val rhs = sortedSuffixTree[i+1]
        val longestPrefix = longestPrefix(lhs, rhs)
        if (longestRepeatedSubstring.length < longestPrefix.length) {
            longestRepeatedSubstring = longestPrefix
        }
    }
    return longestRepeatedSubstring
}

Time complexity O (N log N), which is much better than brute force algorithm.

References

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

Source Code

https://gitlab.com/demensdeum/algorithms