Fixing slow HDD Windows 10

This article is dedicated to all die hard hdd users.

Original (Mae Mu)

1.5 years of using HP Pavilion laptop HDD dualboot (Windows 10) and SSD (Ubuntu) I began to notice a very long loading of applications, a common interface unresponsive, hangs on simple operations in Windows 10. The problem has been minimized to the extent that the use of a laptop has become possible again. Next, I will describe the action that I have taken to correct the problem.

Diagnostics

For the study to be eliminated mystification of any order, first determine the root cause damage hard drives. What can go wrong when dealing with a hard drive? Problems can occur in the physical layer electronics and logical data software.
By electronics problems include such things as PC / Laptop power problems; Wear a hard disk component failure in the circuits and chips internal drive components, software, firmware error, the consequences of hit shock / disc falls, or similar problems with other devices that affect its operation.
Hard disk wear and tear is considered critical time of occurrence of the amount of such a large number of bad sectors (bad block) in which the further operation of the disc is not possible. These blocks are blocked by the hard drive firmware, the data is transferred to other sectors automatically and should not affect the disk performance to a certain critical point.
The problems include programming logic error in the file system due to incorrect operation of the application, a user action: off on the hot device, the completion of the recording process without properly stopping the application, errors in drivers, operating system services.
Not having a specialized electronic diagnostic tools, we only need to check the correct software level, already in the process of electronics may show problems that are usually eliminated by block repair (replacement of components / chips); Next, consider the software methods of diagnosis using diagnostic tools. It is worth noting that all utilities must be run on a system with the highest priority, as other applications may interfere with measurements of performance, lock the drive read / write, which will lead to incorrect results of diagnosis.

SMART

S.M.A.R.T. monitoring service for storage devices -. HDD, SDD, eMMC etc. It allows to evaluate the wear devices, view the number of bad blocks, based on the data to take further action. View SMART can be used in various applications for working with disks, I prefer to use tools from the manufacturer. For your hard drive Seagate SeaTools utility I used, output status as a GOOD for him, that is, drive firmware finds that all is well.

Manufacturer Tools

Disc producer utility provides tests to check his work. SeaTools has several types of tests, you can use them all to localize the problem. Quick and simple tests can not detect any problems, so I prefer for many tests. In my case only on the Long Test errors were found.

Slowride

To check the correctness of the reading, finding slow or dead blocks, I wrote an application slowride. It works on a very simple principle – opens a handle to a block device, with user-defined settings produces read data of the entire device, with measurements of time, slow output blocks. The program stops at the first error, would then have to go to more serious utility to remove the data as a simple data disc methods is not possible to read.
In my case, reading the entire disk it was carried out properly, with little drawdown speed – 90MB / s (5400rpm) in one second, in some areas of the disc. From which one could conclude that I am dealing with a software problem.

Acoustic Analysis

This method does not apply to software methods of diagnosis, however, it is important enough to fix the problem. For example, when the operating part supply unit, a hard disk may Freeze / hang emitting a loud click.
In my case, when dealing with the disc in Windows 10, I heard familiar to all owners of HDD, loud buzz run around the drive head when you try to do anything in the operating system, but the sound was almost constant, it made me think about too much disk fragmentation, disk reloading background service.

Fixing

Electronics problems during software diagnostics have not been found, chunked read the entire disc was completed correctly, but showed SeaTools errors Long Test verification.

Manufacturer Tools

Manufacturer disk diagnostic software in addition provides the error correction procedure. The SeaTools is responsible for this Fix All button, then agreed to accept the potential loss of data, it will start the process of correction. I did my case, this fix? No, the drive continued to work as loudly and slowly, but the Long Test error is no longer shown.

CHKDSK

CHKSDK is Microsoft’s tool to eliminate programming errors for Windows file systems. Over time, these errors accumulate on the disc and can greatly interfere with the work, including the result in the inability to read / write any data at all. Instructions on the use of tools you can find on the Microsoft site, I recommend to use all possible flags for error correction (at the time of this writing, is / r / b / f); Need to run a check with the administrator via the Windows terminal (cmd), for the system partition it will be held on the system boots, it may take a very long time, in my case took 12 hours.
I did this fix in my case? Not.

Disk Defragmenter

Working with the disk data blocks is carried out, large files typically stored in multiple blocks / fragments. Over time, a lot of deleted files create empty blocks that are not there, because of this when writing files to fill these voids, and disk head has to physically travel long distances. This problem is called fragmentation, and with her face only a user’s hard drive. At the time several fixes fragmentation of my hard drive was 41%, visually it looks like this:

That is bad. See fragmentation, to defragment, you can use Defragger utility or built defragmenter. You can also turn the service on “Optimize drives” in Windows 10, put down a defragmentation schedule in the control panel.Defragment only need the HDD, discs include undesirable for SSDAs this will lead to accelerated wear of the disc, probably for this reason that defragmentation is disabled by default.

Also known is an alternative embodiment of defragmentation – transferring data to another disk, the formatting of the disk, and copying the data back. In this case, data will be recorded on a completely empty sector, while maintaining the correct logical structure to run the system. This reset option is fraught with problems potentially critical metadata that may not move during normal copying.

Disable Services

With utility Mark Russinovich Process Monitor you can track the processes that load the hard drive their business, just include the column IO Write / Read. After the study of this column, I disabled the service Xbox Game Bar, a well-known service background acceleration Superfetch programs under the new name SysMain, through the panel of the control panel services. Superfetch should constantly analyze the application used by the user, and accelerate their launch using caching in memory, in my case it led to a background downloading the entire disc and the inability to work.

Clean the Drive

I also removed the old app, unwanted files, thus freeing up the sector to correct the fragmentation, simplifying the job of the operating system, reducing the number of useless, heavy services and programs.

Total

What helped the most? A marked difference in performance was achieved after a disk defrag, spontaneous hang persists by disabling services Xbox and Superfetch. It would not have these problems if I used the SSD? Problems with slow performance when fragmentation would definitely would not have been a problem with the services had to remove in any case, and software errors do not depend on the type of drive. In the near future I plan to complete the migration to the SSD, but for now, “Long live the pancakes, pancakes forever!”

References

http://www.outsidethebox.ms/why-windows-8-defragments-your-ssd-and-how-you-can-avoid-this/
https://channel9.msdn.com/Shows/The-Defrag-Show
https://www.seagate.com/ru/ru/support/downloads/seatools/
https://www.ccleaner.com/defraggler/download
https://docs.microsoft.com/en-us/windows-server/administration/windows-commands/chkdsk
https://gitlab.com/demensdeum/slowride/

Backend server C++ FCGI

Quick note about how I wrote the backend for 3D Cube Art Project editor, the server needs to store and display the user work from web version, giving them a short URL on the save button. At first I wanted to use the Swift/PHP/Ruby/JS or some similar modern language for the backend, but looking at the characteristics of my VPS was decided to write a server on the C/C ++.
First you need to install on the server and libfcgi fcgi support module for your web server, for example Ubuntu and Apache:


sudo apt install libfcgi libapache2-mod-fcgid

Next, configure the module in the config file:

FcgidMaxProcessesPerClass – the maximum number of processes in the class, I put 1 process because it does not count on a big load.
AddHandler fcgid-script .fcgi – file extension which should start fcgi module.
Add in the config directory which will run cgi applications:

Next, write an application to the C/C ++ with fcgi support, collect it, and it is copied to the folder /var/www/html/cgi-bin.
Examples code and build script:
https://gitlab.com/demensdeum/cube-art-project-server/-/blob/master/src/cubeArtProjectServer.cpp
https://gitlab.com/demensdeum/cube-art-project-server/-/blob/master/src/build.sh
Then you need to restart your web server:


systemctl restart apache2

Next, put down the necessary rights for the execution of cgi-bin folder via chmod.
After that, your cgi program should work through the browser to the link, for example Cube Art Project Server:
http://192.243.103.70/cgi-bin/cubeArtProject/cubeArtProjectServer.fcgi
If something does not work, then see the web server logs, or connect the debugger to a running process, the debugging process should not differ from the usual process of debugging the client application.

References

https://habr.com/ru/post/154187/
http://chriswu.me/blog/writing-hello-world-in-fcgi-with-c-plus-plus/

Source Code

https://gitlab.com/demensdeum/cube-art-project-server

Porting C++ SDL Application To Android

In this article I will describe his experience porting 3D editor prototype Cube Art Project on Android.
First, look at the result, the emulator running the editor with 3D cursor red cube:

To build a successful have to do the following:

  1. Install the latest Android SDK and NDK (National Palace of Culture version of the fresher the better).
  2. Download the code SDL2, take out a template to build an application for android.
  3. Add SDL Image, SDL Mixer for assembly.
  4. Add the library of my game engine and toolkit, their dependencies (GLM, JSON for Modern C++)
  5. Adapt the assembly files for Gradle.
  6. Adapt the C ++ code to be compatible with Android, changes were platform specific components (OpenGL ES, the graphics context initialization)
  7. Assemble and test the project on the emulator.

Project Template

Load the source code SDL, SDL Image, SDL Mixer:
https://www.libsdl.org/download-2.0.php
The docs folder contains detailed instructions on working with project android template; copy the directory android-project in a separate folder, make a symlink or copy the SDL folder in android-project / app / jni.
Substitute the correct identifier for avd flag, run the emulator from the Android Sdk directory:


cd ~/Android/Sdk/emulator
./emulator -avd Pixel_2_API_24

Specify the path to the script, pick a project:


rm -rf app/build || true
export ANDROID_HOME=/home/demensdeum/Android/Sdk/
export ANDROID_NDK_HOME=/home/demensdeum/Android/android-ndk-r21-beta2/
./gradlew clean build
./gradlew installDebug

Should meet SDL project template with the code in C from a file


android-sdl-test-app/cube-art-project-android/app/jni/src/YourSourceHere.c

Dependencies

Download the source code archives for SDL_image, SDL_mixer:
https://www.libsdl.org/projects/SDL_image/
https://www.libsdl.org/projects/SDL_mixer/

Load depending on your project, for example, my shared library:
https://gitlab.com/demensdeum/FlameSteelCore/
https://gitlab.com/demensdeum/FlameSteelCommonTraits
https://gitlab.com/demensdeum/FlameSteelBattleHorn
https://gitlab.com/demensdeum/FlameSteelEngineGameToolkit/
https://gitlab.com/demensdeum/FlameSteelEngineGameToolkitFSGL
https://gitlab.com/demensdeum/FSGL
https://gitlab.com/demensdeum/cube-art-project

All of this was discharged into app / jni, each “module” in a separate folder, such as app / jni / FSGL. Next, you have the option to find workers generators Application.mk and Android.mk files, I have not found, but maybe there’s a simple solution based on CMake. Click on a link and start to get acquainted with the format of the build files for Android NDK:

https://developer.android.com/ndk/guides/application_mk
https://developer.android.com/ndk/guides/android_mk

You should also read about different APP_STL implementation NDK:
https://developer.android.com/ndk/guides/cpp-support.html

After reviewing create for each “module” file Android.mk, further example of an assembly file shared library Cube-Art-Project:


LOCAL_PATH := $(call my-dir)
include $(CLEAR_VARS)

APP_STL := c++_static
APP_CPPFLAGS := -fexceptions
LOCAL_MODULE := CubeArtProject
LOCAL_C_INCLUDES := $(LOCAL_PATH)/src $(LOCAL_PATH)/../include $(LOCAL_PATH)/../include/FlameSteelCommonTraits/src/FlameSteelCommonTraits
LOCAL_EXPORT_C_INCLUDES = $(LOCAL_PATH)/src/

define walk
  $(wildcard $(1)) $(foreach e, $(wildcard $(1)/*), $(call walk, $(e)))
endef

ALLFILES = $(call walk, $(LOCAL_PATH)/src)
FILE_LIST := $(filter %.cpp, $(ALLFILES))
$(info CubeArtProject source code files list)
$(info $(FILE_LIST))
LOCAL_SRC_FILES := $(FILE_LIST:$(LOCAL_PATH)/%=%)

LOCAL_SHARED_LIBRARIES += FlameSteelCore
LOCAL_SHARED_LIBRARIES += FlameSteelBattleHorn
LOCAL_SHARED_LIBRARIES += FlameSteelCommonTraits
LOCAL_SHARED_LIBRARIES += FlameSteelEngineGameToolkit
LOCAL_SHARED_LIBRARIES += FlameSteelEngineGameToolkitFSGL
LOCAL_SHARED_LIBRARIES += FSGL
LOCAL_SHARED_LIBRARIES += SDL2
LOCAL_SHARED_LIBRARIES += SDL2_image

LOCAL_LDFLAGS := -static-libstdc++
include $(BUILD_SHARED_LIBRARY)

CMake any experienced user realizes this configuration with the first string formats are very similar in Android.mk no GLOB_RECURSIVE, so we have to recursively search for source files with walk functions.

Change Application.mk, Android.mk with-but to build C++ instead of C code:


APP_ABI := armeabi-v7a arm64-v8a x86 x86_64
APP_PLATFORM=android-16
APP_STL := c++_static
APP_CPPFLAGS := -fexceptions

Rename YourSourceHere.c -> YourSourceHere.cpp, grep for entry, change the path in the assembly, for example:


app/jni/src/Android.mk:LOCAL_SRC_FILES := YourSourceHere.cpp

Next, try to build the project, if you see an error from the compiler about the absence of Heather, check the correctness of the ways in Android.mk; if mistakes are kind of linker “undefined reference”, check the correctness of indications of source code files in assemblies ottreysit lists possible by specifying $ (info $ (FILE_LIST)) in Android.mk file. Do not forget the double-linking mechanism, with modules in LOCAL_SHARED_LIBRARIES key and correct linking through the LD, for example FSGL:


LOCAL_LDLIBS := -lEGL -lGLESv2

Adaptation And Launching

I had to change some things, for example to remove GLEW of assemblies for iOS and Android, to rename part of OpenGL calls, adding a suffix EOS (glGenVertexArrays -> glGenVertexArraysOES), include macro missing modernistic features debug, the cherry on the cake is the implicit include vulnerability GLES2 Heather indicating macro GL_GLEXT_PROTOTYPES 1 :


#define GL_GLEXT_PROTOTYPES 1
#include "SDL_opengles2.h"

Also, a black screen in the first starts with an error type “E / libEGL: validate_display: 255 error 3008 (EGL_BAD_DISPLAY)”, has changed initialize SDL window, GL profile initialization and it worked:


SDL_DisplayMode mode;
SDL_GetDisplayMode(0,0,&mode);
int width = mode.w;
int height = mode.h;

window = SDL_CreateWindow(
            title,
            0,
            0,
            width,
            height,
            SDL_WINDOW_OPENGL | SDL_WINDOW_FULLSCREEN | SDL_WINDOW_RESIZABLE
        );

SDL_GL_SetAttribute( SDL_GL_CONTEXT_PROFILE_MASK, SDL_GL_CONTEXT_PROFILE_ES );

On the default emulator application is installed with the “Game” icon SDL and name.

I needed to explore the possibility of automatically generating assembly files based on CMake, or else migrate assembly for all platforms on Gradle; CMake but remains the de facto choice for the current development in C++.

Source Code

https://gitlab.com/demensdeum/android-sdl-test-app
https://gitlab.com/demensdeum/android-sdl-test-app/tree/master/cube-art-project-android

Sources

https://developer.android.com/ndk/guides/cpp-support.html
https://developer.android.com/ndk/guides/application_mk
https://developer.android.com/ndk/guides/android_mk
https://lazyfoo.net/tutorials/SDL/52_hello_mobile/android_windows/index.php
https://medium.com/androiddevelopers/getting-started-with-c-and-android-native-activities-2213b402ffff

Flipped World

To develop a new project Cube Art Project has adopted a methodology for the development of Test Driven Development. In this approach, implemented first test for a particular functional application, and then implemented this functionality. A great advantage in this approach, I believe the final implementation of the interfaces, the most uninitiated in the details of implementation, prior to the development of the functional. With this approach, the test dictates the further implementation, added to all the advantages of contract programming when interfaces are contracts for the implementation.

Cube Art Project – 3D editor in which the user builds the shape of cubes, not so long ago, this genre was very popular. Since this graphic application, I decided to add tests to the validation of screenshots.

For screenshot validation you need to get them from OpenGL context first, it is done with the help of glReadPixels function. Description of function arguments are simple – the starting position, width, height, format (. RGB / RGBA / etc.), a pointer to the output buffer, anyone working with SDL or having experience with data buffers in C will simply substitute the correct arguments. However consider it necessary to describe an interesting feature of the output buffer glReadPixels, the pixels stored therein upwards and in SDL_Surface all basic operations taking place downwards.

That is, the reference by uploading a screenshot from the png file, I could not compare the two buffers in the forehead, as one of them upside down.

To flip the output buffer of OpenGL you need to fill it up taking away the height of the screenshot to coordinate Y. However, cost to take into account that there is a chance to go beyond the buffer limits, if not take the unit to fill the time, which will lead to memory corruption.

Since I’m all over the place trying to use OOP paradigm “programming interfaces”, instead of a direct C-like memory access at the sign, when you try to write data outside of the buffer object I reported it to the method of borders through validation.

Final code method of obtaining screenshots in the style of top-down:


    auto width = params->width;
    auto height = params->height;

    auto colorComponentsCount = 3;
    GLubyte *bytes = (GLubyte *)malloc(colorComponentsCount * width * height);
    glReadPixels(0, 0, width, height, GL_RGB, GL_UNSIGNED_BYTE, bytes);

    auto screenshot = make_shared(width, height);

    for (auto y = 0; y(redColorByte, greenColorByte, blueColorByte, 255);
            screenshot->setColorAtXY(color, x, height - y - 1);
        }
    }

    free(bytes);

Sources

https://community.khronos.org/t/glreadpixels-fliped-image/26561
https://stackoverflow.com/questions/8346115/why-are-bmps-stored-upside-down

Source Code

https://gitlab.com/demensdeum/cube-art-project-bootstrap

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

Insertion Sort, Merge Sort

Insertion Sort

Insertion sort – each element is compared to the previous item in the list and inserted in place of more. Since the items are sorted from first to last, then each successive element is compared with pre-sorted list that *might* reduce the total time. Time complexity O(n^2), that is identical to the bubble sort.

Merge Sort

Merge sort – the list is divided into groups of one element, then the group “merge” in pairs with simultaneous comparison. In my implementation at the merge of pairs elements to the left compared with the right elements, and then moved to the result list, if the items in left are over, then right list elements added to resulting list (their extra comparison is unnecessary, since all the elements in the groups are sorted by iterations)
The operation of this algorithm is very easy to parallelize, pairs merging step can be performed in threads, with thread dispatcher wait.
Algorithm output for single-threaded performance:


["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["Alice", "John"], ["#1", "Mike"], ["20", "Артем"], ["60", "60"], ["DoubleTrouble"]]
[["#1", "Alice", "John", "Mike"], ["20", "60", "60", "Артем"], ["DoubleTrouble"]]
[["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"], ["DoubleTrouble"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]

Algorithm output for multithreaded execution:


["John", "Alice", "Mike", "#1", "Артем", "20", "60", "60", "DoubleTrouble"]
[["John"], ["Alice"], ["Mike"], ["#1"], ["Артем"], ["20"], ["60"], ["60"], ["DoubleTrouble"]]
[["20", "Артем"], ["Alice", "John"], ["60", "60"], ["#1", "Mike"], ["DoubleTrouble"]]
[["#1", "60", "60", "Mike"], ["20", "Alice", "John", "Артем"], ["DoubleTrouble"]]
[["DoubleTrouble"], ["#1", "20", "60", "60", "Alice", "John", "Mike", "Артем"]]
["#1", "20", "60", "60", "Alice", "DoubleTrouble", "John", "Mike", "Артем"]

Time complexity O (n * log (n)), which is slightly better than O (n ^ 2)

References

https://en.wikipedia.org/wiki/Insertion_sort
https://en.wikipedia.org/wiki/Merge_sort

Source Code

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

Bubble Sort in Erlang

Bubble sort is quite boring, but it becomes more interesting if you try to implement it in a functional language for telecom – Erlang.

We have a list of numbers, we need to sort it. bubble sort algorithm runs through the whole list, iterating, and comparing the number of pairs. Upon verification of the following occurs: a smaller number is added to the output list, or change the number of places in this list if the right is smaller bust continues with the next iteration number. This bypass is repeated as long as the list will no longer be replaced.

In practice it is not necessary to use due to the large time complexity – O (n ^ 2); I implemented it in Erlang language in an imperative style, but if you’re interested you can look for the best options:


-module(bubbleSort).
-export([main/1]).

startBubbleSort([CurrentHead|Tail]) ->
    compareHeads(CurrentHead, Tail, [], [CurrentHead|Tail]).

compareHeads(CurrentHead, [NextHead|Tail], [], OriginalList) ->   
    if
        CurrentHead < NextHead ->
            compareHeads(NextHead, Tail, [CurrentHead], OriginalList);
        true ->
            compareHeads(CurrentHead, Tail, [NextHead], OriginalList)
    end;
    
compareHeads(CurrentHead, [NextHead|Tail], OriginalOutputList, OriginalList) ->
    if
        CurrentHead < NextHead ->
            OutputList = OriginalOutputList ++ [CurrentHead],
            compareHeads(NextHead, Tail, OutputList, OriginalList);
        true ->
            OutputList = OriginalOutputList ++ [NextHead],
            compareHeads(CurrentHead, Tail, OutputList, OriginalList)
    end;
  
compareHeads(CurrentHead, [], OriginalOutputList, OriginalList) ->
    OutputList = OriginalOutputList ++ [CurrentHead],
    if
        OriginalList == OutputList ->
            io:format("OutputList: ~w~n", [OutputList]);
        true ->
            startBubbleSort(OutputList)
    end.
  
main(_) ->
    UnsortedList = [69,7,4,44,2,9,10,6,26,1],
    startBubbleSort(UnsortedList).

Install and run

In Erlang Ubuntu install is easy, just enter the following command in a terminal sudo apt install erlang. In this language, each file must be of a module (module), a list of functions that can be used outside – export. The interesting features of the language is the lack of variables, only constants, there is no standard syntax for the PLO (which does not prevent the use of OOP techniques), and of course the parallel computing without locks based on actor model.

Start module can be either through an interactive console erl, running one command after another, either through easier escript bubbleSort.erl; For different cases the file will look different, for example escript necessary to make the main function, from which it will start.

References

https://www.erlang.org/

https://habr.com/ru/post/197364/

Source Code

https://gitlab.com/demensdeum/algorithms/blob/master/bubbleSort/bubbleSort.erl

Lexicographical comparison

lexicographic comparisons rows algorithm works very simple loop compares the character codes and the result is returned if the symbols are not equal.

An example for the C language can be found here:
https://github.com/gcc-mirror/gcc/blob/master/libiberty/memcmp.c

Keep in mind that you need to compare the characters in a single static encoding, such as Swift, I used the comparison character by character to UTF-32. Array sorting option using memcmp work exactly for single-byte character, otherwise (variable length coding) may order is incorrect. I do not rule out the possibility of implementation on the basis of a variable-length encoding, but is likely to be much more complicated.

Time complexity at most O(1), the average and worst-O(n)

References

https://ru.wikipedia.org/wiki/Лексикографический_порядок

Source Code

https://gitlab.com/demensdeum/algorithms/blob/master/lexiCompare/lexiCompare.swift