BubbleSort Application

BubbleSort - Release Notes

Copyright 2025 by The Software Samurai.
On the web: http://www.SoftwareSam.us/
Software released under GNU GPL3, and documentation released under FDL1.3
This document describes version 0.0.03 of BubbleSort.

Description

The BubbleSort (‘bubsort’) utility is a GNU/Linux console application which demonstrates the structure of the “bubble sort” sorting algorithm for either text or numeric data.

The "bubble sort" is the simplest (and slowest) of the common sorting algorithms.
It's great flexibility is its strength, but it is recommend that it be used only if the total number of records is
“relatively small”.
This application uses a bi-directional bubble sort, also known as the “cocktail sort”, presumably because its inventor was sipping a martini at the time.
Sorting record pointers is much faster than sorting the actual records, regardless of record content, and therefore, except for pure numeric data, pointer sorting is recommended whenever practical. This application demonstrates sorting both using record pointers, and direct sorting of the record data.
When sorting complex records such as class instances, a method must be devised to determine which record is greater or lesser than the other.
1. This application uses the author's ‘WinPos’ class to demonstrate this technique. WinPos is a simple class with only two data members (row and column), but with an assortment of constructors and assignment operators for positioning data within a window.
2. While the WinPos class defines "operator==" and "operator!=" it does not include greater-than or less-than operators, so one of the data members is used to perform these comparisons during the sort. The assignment operators are used to demonstrate direct swapping of the objects in the array being sorted. Example:
  WinPos wpA( 14, 56 ), wpB( 12, 56 ), wpSwap; if ( wpA.row > wpB.row ) { wpSwap = wpA; wpA = wpB; wpB = wpSwap; }
3. Again, sorting pointers to objects is much faster that sorting the objects themselves, and should be used whenever practical; especially when the data are sorted and re-sorted under user control. Hint: pointers are actually numeric data.
  int RECORDS = 250, src = 0, trg = RECORDS - 1; WinPos array[RECORDS] = { {14,56}, ... {78,22} }; WinPos* ptr[RECORDS] = { &array[0], &array[1], ... &array[RECORDS - 1] }; WinPos* swap; if ( ptr[src]->row > ptr[trg]->row ) { swap = ptr[src]; ptr[src] = ptr[trg]; ptr[trg] = swap; }
  Please see the author's FileMangler application for a real-world example of sorting complex data records (file stat records for an arbitrary number of files and directories).

This application was designed under Fedora Linux and is built using the GNU C compiler, version 13.3.1 or higher (C++17 support required). If you are not using GCC, then verify that your compiler fully supports the C++17 standard.

Building From Source

Download and unpack the distribution archive.
- Navigate to the base directory where package will be installed (example):
  cd ~/Software
- Move the archive file to the base directory:
  mv ~/Dowloads/bubblesort-0.0.03.tar.bz2 ./.
- Unpack the tar archive:
  tar -xjvf bubblesort-0.0.03.tar.bz2
- Navigate to the target directory:
  cd BubbleSort

After unpacking the archive, the directory will look something like this:

/home/sam/Software/BubbleSort/BubbleSort.hpp        <== Application class definition
                             /BubbleSort.cpp        <== Application definition and implementation
                             /BubbleSortParse.cpp   <== Application definition and implementation
                             /gString.hpp           <== gString class definition (text analysis)
                             /gString.cpp           <== gString class implementation 
                             /Makefile              <== Build the 'bcart' application
                             /test_data.txt         <== External test data 
                             /README                <== Package description, release notes

Build the application:
gmake all

The GNU G++ compiler is invoked to build and link the binary executable file.
The application should build without errors and without warnings.

Test the build:
./bubsort − −version
The application version and a copyright message should be displayed.

BubbleSort (bubsort) v:0.0.03  Copyright (c) 2025-____ The Software Samurai
===========================================================================
gString-class version:0.0.03   locale:en_US.UTF-8
---------------------------------------------------------------------------
License GPLv3+: GNU GPL version 3 
This is free software: you are free to modify and/or redistribute it
under the terms set out in the license.
There is NO WARRANTY, to the extent permitted by law.

For invocation options, type:
./bubsort − −help
See the next section for a description of command-line options.
Make the application visible on the system $PATH:
This can be done in either of two ways:
  1) copy the executable to a directory on the path:
      cp − −preserve=all ./bubsort ~/usr/local/bin/.
  2) create a symbolic link to the executable in the source directory.
      cp − −symbolic-link ./bubsort ~/usr/local/bin/.

Operational Overview

BubbleSort is a very basic demonstration utility, bypassing user-friendliness in favor of simplicity.
The standard console app ‘− −help’ and ‘− −version’ options are available. A small number of command-line options provide access to all available functionality. See the next section for details.

This application relies heavily on our gString text-analysis tool which parses the source data, performs all text comparisons as well at moving text records (if necessary) during the sorting process.
Using the gString class for comparison and copying of text data encapsulates or bypasses all of the dangerous
C-language string manipulation functions. While C-language functions such as ‘wcsncasecmp’, ‘wcpncpy’, ‘wcwidth’, ‘mbsrtowcs’ ‘wcsrtombs’ and others are undeniably more efficient than the poorly-designed C++ ‘std::string’ etc.; they often lead to buffer overruns, memory leaks and other dangerous relics of a previous century. Using the gString class leverages the speed of these functions while minimizing the danger.

// String Comparison Examples: gString gsI( "Apples" ), gsL( "Bananas" ); // Case Sensitive: if ( (gsI.compare( gsL, true )) < ZERO ) { ... } if ( (gsI.compare( "Avocados", true )) < ZERO ) { ... } if ( (gsI.compare( L"D'Anjou pears", true )) < ZERO ) { ... } // Case Insensitive: if ( (gsI.compare( gsL, false )) < ZERO ) { ... } // Locale-aware comparison: if ( (gsI.compcoll( gsL )) < ZERO ) { ... } // String Copy Examples: const char* green_apple = "Eat green apples."; wchar_t wbuff[32]; // UTF-32 Target Buffer char ubuff[32]; // UTF-8 Target Buffer: gsI = green_apple ; // load the data gsI.copy( wbuff, 32 ); // write max. 32 characters gsI.copy( ubuff, 32 );) // write max. 32 bytes

For a full discussion of the gString class, please see the documentation for the author's NcDialog API package, or the stand-alone gString text-analysis-and-formatting package. gString Documentation

Command-line Options

Invocation:
Usage: bubsort --dir==[a | d] [OPTIONAL ARGS]

Options may be specified in any order.
Options are case sensitive.
All options except the ‘– –dir’ option are optional.
‘– –dir’ : sort direction:
- ‘a’: ascending, sort from low to high
- ‘d’: descending, sort from high to low
‘– –type’ : type of source data (optional)
- ‘t’ : text data pointers (default)
  The array of sample text records remains unmodified, while an array of pointers to the records is sorted.
- ‘T’ : text data direct
  The array of sample text records is sorted directly.
- ‘a’ : alternate-text data pointers
  The array of sample text records remains unmodified, while an array of pointers to the records is sorted.
- ‘A’ : alternate-text data direct
  The array of sample text records is sorted directly.
- ‘r’ : complex record pointers
  The array of sample class-object records remains unmodified, while an array of pointers to the records is sorted.
- ‘R’ : complex records direct
  The array of class-object records is sorted directly.
- ‘n’ : numeric (integer) data
  The array of sample numeric data is sorted directly.
‘– –case’ : specify case sensitivity for sorting (optional)
- ‘y’ : yes, case-sensitive sort (default)
- ‘n’ : no, case-insensitive sort
‘– –src=filename’ : source-data filename (optional)
The name of a plain-text file containing the data to be sorted.

./bubsort --dir=a --src='test_data.txt'
Each line of the file is interpreted as a single record, and the sorted data are written to ‘stdout’.
If desired the output can be redirected to a target file.
./bubsort --dir=a --src='source_file' 1>>'target_file'
‘– –shuffle=value’ : (debugging option)
This option reorders the source text data BEFORE the sort is executed. The intent of this option is to exercise each possible comparison in concert with both the type=t and type=T options.
The option takes a numeric argument which is a seed value for the shuffle.
Range: 1 <= value < srcRECORDS (srcRECORDS currently defined as ten(10)).
(This option is not listed in the command-line help.)
‘– –compcoll’ : (debugging option)
This option invokes the gString-class “compcoll” function to perform the string comparisons.
The library functions used for this type of sort are aware of the application locale, and therefore handle
uppercase/lowercase and language-specific characters differently from a straight numeric sort.
See the next section for a discussion of the application locale. (This option is not listed in the command-line help.)
‘– –sand’ : (debugging option)
This is the sandbox. It can be used for ad-hoc testing. (This option is not listed in the command-line help.)

Application “Locale”

On startup, the Bubblesort application sets the application locale (if any) from the environment. While this locale has no direct effect on the standard sorting processes used by this application, it does come into play for the
“– –compcoll” debugging option.
The author recommends that each non-trivial application should explicitly initialize the locale on startup. This is accomplished by creating an instance of the std::locale object as shown: #include std::locale* ioLocale = new std::locale ( "" ) ; ioLocale->global( *ioLocale ) ;
For information on performing a "collated" (locale-aware) sort, please see the standard library 'strcoll' and 'wcscoll' functions. For a simple example of this sort, see the 'SortCollated' method in BubbleSort.cpp, which in turn calls the 'compcoll' method of the gString class. The author has found this type of sort to be almost entirely worthless, but your mileage may vary.
Specifically, the C-library ‘wcscoll’ function seems to be unstable and may return an incorrect value for some comparisons. The ‘wcscoll’ documentation says:

Collation order is the dictionary order: the position of the letter in the national alphabet (its equivalence class)
has higher priority than its case or variant. Within an equivalence class, lowercase characters collate before
their uppercase equivalents and locale-specific order may apply to the characters with diacritics. In some locales,
groups of characters compare as single collation units. For example, “ch” in Czech follows “h” and precedes “i”,
and “dzs” in Hungarian follows “dz” and precedes “g”. https://en.cppreference.com/w/c/string/wide/wcscoll

In the American English locale, however, the comparison seems to be case-insensitive.
This needs further research.