カクテル シェーカー ソート –双方向バブルソーティングの一種であるシェーカーソーティング。
アルゴリズムは次のように機能します。
<オル>
アルゴリズムの時間計算量はバブル – に似ています。 O(n2)。
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://www.youtube.com/watch?v=njClLBoEbfI
https://www.geeksforgeeks.org/cocktail-sort/
https://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort
スリープソート
睡眠並べ替え – sleep sort は、決定論的な奇妙な並べ替えアルゴリズムのもう 1 つの代表です。
次のように動作します:
<オル>
C での睡眠ソート アルゴリズムのサンプル コード:
#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 (maximal < number) {
maximal = number;
maximalThreadID = threadID;
}
}
printf("\n");
printf("Sorted: ");
pthread_join(maximalThreadID, NULL);
printf("\n");
return 0;
}
この実装では、マイクロ秒で usleep 関数を使用し、値に 1000 を乗算しました。ミリ秒単位
で。アルゴリズムの時間計算量 – O(とても長い)
リンク
https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/sleepSort
ソース
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
スターリンソート
スターリン ソート – sort through は、データ損失を伴う並べ替えアルゴリズムの 1 つです。
このアルゴリズムは非常に生産的で効率的で、時間計算量は O(n) です。
次のように動作します:
<オル>
アルゴリズムの出力の例:
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 コード:
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}")
欠点としてはデータ損失が挙げられますが、O(n) で理想的なソート済みリストを実現するためには、他にどのような方法があるでしょうか?
リンク
https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/stalinSort
ソース
https://github.com/gustavo-depaula/stalin-sort
https://www.youtube.com/shorts/juRL-Xn-E00
https://www.youtube.com/watch?v=L78i2YcyYfk
選択範囲の並べ替え
選択並べ替え –選択ソートアルゴリズム。何を選ぶの？でも最低数!!!
アルゴリズムの時間計算量 – O(n2)
アルゴリズムは次のように機能します。
<オル>
アルゴリズムの実行例:
(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)
Rosetta コードで Objective-C 実装が見つかりませんでした。 、私は自分でこう書きました。
#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 Собрать и запустить можно либо на MacOS/Xcode, либо на любой операционной системе поддерживающей GNUstep, например у меня собирается Clang на Arch Linux.
Скрипт сборки:
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
カウンティングソート
カウントソート–カウントソートアルゴリズム。に関しては？はい！そのとおりです!
アルゴリズムには少なくとも 2 つの配列が含まれます。最初の配列は –ソートする整数のリスト、2 番目 –サイズ = (最大数 – 最小数) + 1 の配列。最初はゼロのみを含みます。次に、最初の配列から数値が並べ替えられ、その数値要素を使用して 2 番目の配列のインデックスが取得され、1 ずつ増分されます。リスト全体を調べた後、最初の配列からの数値の繰り返し数を含む、完全に満たされた 2 番目の配列が得られます。 アルゴリズムには重大なオーバーヘッドがあります – 2 番目の配列には、最初のリストにない数値のゼロも含まれます。メモリによるオーバーヘッド
2 番目の配列を受け取った後、それを反復処理し、インデックスでソートされた数値を書き込み、カウンターを 0 にデクリメントします。最初は、ゼロ カウンタは無視されます。
カウントソートアルゴリズムの最適化されていない操作の例:
<オル>
Python 3 のアルゴリズム コード:
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"Maximal 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)Из-за использования двух массивов, временная сложность алгоритма O(n + k)
Ссылки
https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/countingSort
Источники
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
ボゴソート
疑似ソートまたはスワンプ ソート。最も役に立たないソート アルゴリズムの 1 つ。
次のように動作します。
1. 入力は数値の配列です
2. 数字の配列をランダムにシャッフル（シャッフル）する
3. 配列がソートされているかどうかを確認します
4. ソートされていない場合、配列は再度シャッフルされます
5. 配列がランダムに並べ替えられるまで、このすべてのアクションが繰り返されます。
ご覧のとおり、このアルゴリズムのパフォーマンスはひどいもので、賢い人は O(n * n!) さえも信じています。何年もの間、カオスの神の栄光のためにサイコロを投げることに行き詰まる可能性があります。配列は決してソートされません。それともソートされるかもしれません >
実装
TypeScript で実装するには、次の関数を実装する必要がありました。
1. オブジェクトの配列をシャッフルする
2. 配列の比較
3. 0 から数値 (原文どおり!) までの範囲の乱数を生成します
4. 進行状況を印刷します。並べ替えは延々と続くようです
以下は TypeScript 実装コードです。
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); var temp = 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}`);Для отладки можно использовать VSCode и плагин TypeScript Debugger от kakumei.
Как долго
Вывод работы алгоритма:
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Для массива из 10 чисел Богосорт перемешивал исходный массив 148798 раз, многовато да?
Алгоритм можно использовать как учебный, для понимания возможностей языка с которым предстоит работать на рынке. Лично я был удивлен узнав что в ванильных JS и TS до сих пор нет своего алгоритма перемешивания массивов, генерации целого числа в диапазоне, доступа к хэшам объектов для быстрого сравнения.
Ссылки
https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/bogosort
https://www.typescriptlang.org/
https://marketplace.visualstudio.com/items?itemName=kakumei.ts-debug
Источники
https://www.youtube.com/watch?v=r2N3scbd_jg
https://en.wikipedia.org/wiki/Bogosort
RGB画像をグレーに
この投稿では、RGB バッファをグレー (グレースケール) に変換するアルゴリズムについて説明します。
これは非常に簡単に行われ、バッファの各ピクセル カラー チャネルが特定の式に従って変換され、出力はグレーの画像になります。
平均的な方法:
red = average;
green = average;
blue = average;Складываем 3 цветовых канала и делим на 3.
Однако существует еще один метод – метод средневзвешенный, он учитывает цветовосприятие человека:
red = luminance;
green = luminance;
blue = luminance;
Какой метод лучше использовать? Да какой вам больше подходит для конкретной задачи. Далее сравнение методов с помощью тестовой цветовой сетки:
Пример реализации на JavaScript + HTML 5
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
);
}Источники
https://www.baeldung.com/cs/convert-rgb-to-grayscale
https://twitter.com/mudasobwa/status/1528046455587495940
https://rosettacode.org/wiki/Grayscale_image
Ссылки
http://papugi.demensdeum.repl.co/
Благодарности
Спасибо Aleksei Matiushkin (https://twitter.com/mudasobwa) за наводку на Rosetta Code
最長の共通部分文字列
この投稿では、最大共通部分文字列問題を解決するためのアルゴリズムについて説明します。暗号化されたバイナリ データを復号化しようとしているとします。まず、最大の部分文字列を検索して共通のパターンを見つけてみましょう。
入力文字列の例:
adasDATAHEADER??jpjjwerthhkjbcvkDATAHEADER??kkasdf
2 回繰り返される文字列を探しています。
データヘッダー??
プレフィックス
まず、2 つの文字列の接頭辞を比較するメソッドを作成しましょう。左側の接頭辞の文字が右側の接頭辞の文字と等しい結果の文字列を返します。
たとえば、行の場合は次のようになります。
val lhs = "asdfWUKI"
val rhs = "asdfIKUW"
結果文字列 –空自
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)
}
ブルートフォース
物事がうまくいかないときは、強引な手段に頼るべきです。 longestPrefix メソッドを使用して、文字列を 2 つのループで処理します。最初のループでは i から最後までの文字列を取得し、2 番目のループでは i + 1 から最後までの文字列を渡して、最大のプレフィックスを検索します。このアルゴリズムの時間計算量は約 O(n^2) ~ O(n*^3) です。
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」と呼ばれるデータ構造というツールが必要です。このデータ構造は、ループ内に埋められた部分文字列の配列であり、各部分文字列は行の次の文字から始まり、最後まで続きます。
たとえば、次の行の場合:
adasDATAHEADER??
サフィックス配列は次のようになります:
adasDATAHEADER??
dasDATAHEADER??
asDATAHEADER??
sDATAHEADER??
DATAHEADER??
ATAHEADER??
TAHEADER??
AHEADER??
HEADER??
EADER??
ADER??
DER??
ER??
R??
??
?
並べ替えることで解決します
サフィックス配列をソートしてから、現在の要素が左側 (lhs) にあり、次の要素が右側 (rhs) にあるループ内のすべての要素を調べて、longestPrefix を使用して最長のプレフィックスを計算します。方法
について。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
}
アルゴリズムの時間計算量は O(N log N) であり、単純な解決策よりもはるかに優れています。
ソース
https://en.wikipedia.org/wiki/Longest_common_substring_problem
ソースコード
https://gitlab.com/demensdeum/algorithms