Low level native sort and eliminate duplicates

Ex. (189) - Low level native sort and eliminate duplicates (I), is presented here in three programming languages: Python, MATLAB, and JavaScript. Although the implementations differ in syntax, the underlying concept remains identical across all three versions. Each code sample is reproduced from its respective volume of the series Coding Examples from Simple to Complex (Springer, 2024).

The example initializes two arrays, a and b, with a initially being an empty array and b containing some numerical values. It then defines two variables, r and n, where r is set to 0, and n is assigned the length of array b. The code proceeds to enter a loop that iterates through the elements of array b using a for-loop, where i serves as the loop counter. Inside the loop, it assigns the value of b[i] to a[b[i]]. This effectively creates a new array a where the indices correspond to the values of b, and the values in a are the same as the corresponding values in b. After that, the code calculates the length of the array a by getting the maximum value among the elements (as the maximum value is equal to the number of elements), and stores it in the variable m.

A second for-loop begins, with j as the loop counter, iterating through the indices of array a. Inside this loop, it checks if there is a non-falsy value at index j in array a. If a non-falsy value is found, it assigns that value to b[r] and increments the value of r. Next, the code prints the contents of array b.

Note that this native sorting method works well for number sequences of short ranges and is written for this book. To my knowledge it is not published anywhere but here. Note that the time spent by this method to sort the values of an array is n + m, where m represents the maximum value over elements of the array.

Example in Python:

a = {}
b = [3, 6, 2, 78, 99, 1, 4]

r = 0
n = len(b)

for i in range(n):
    a[b[i]] = b[i]

m = max(a.keys()) + 1

for j in range(m):
    if j in a:
        b[r] = a[j]
        r += 1

print(b)

Python output:
[1, 2, 3, 4, 6, 78, 99]

Example in Javascript:

let a = [];
let b = [3, 6, 2, 78, 99, 1, 4];

let r = 0;
let n = b.length;
    
for (let i=0; i<n; i++) {
    a[b[i]] = b[i];
}
    
let m = a.length; // max val
    
for (let j=0; j<m; j++) {
    if(a[j]){b[r] = a[j]; r++}
}

print(b);

Javascript output:
[1, 2, 3, 4, 6, 78, 99]

Example in Matlab:

b = [3, 6, 2, 78, 99, 1, 4];
n = length(b);

% Initialize array a with 
% zeros up to the maximum 
% value in b.

a = zeros(1, max(b));

% Fill a using values 
% from b as indices.

for i = 1:n
    a(b(i)) = b(i);
end

% Compact a back into b, 
% effectively sorting it r = 1;

for j = 1:length(a)
    if a(j) ~= 0
        b(r) = a(j);
        r = r + 1;
    end
end

% Truncate b to the new 
% size r - 1 to remove 
% trailing zeros.

b = b(1:r-1);

disp(b);

Matlab output:
[1, 2, 3, 4, 6, 78, 99]

References

Paul A. Gagniuc. Coding Examples from Simple to Complex - Applications in Python, Springer, 2024, pp. 1-245.
Paul A. Gagniuc. Coding Examples from Simple to Complex - Applications in MATLAB, Springer, 2024, pp. 1-255.
Paul A. Gagniuc. Coding Examples from Simple to Complex - Applications in Javascript, Springer, 2024, pp. 1-240.

Gagniuc/Low-level-native-sort-and-eliminate-duplicates

Low level native sort and eliminate duplicates

Example in Python:

Example in Javascript:

Example in Matlab:

References