More precise algorithm definition

[Dixtosa]

As this project gets larger and larger, lol, we may need a less vague algorithm definition than a tweet so that it is easier to know if a PR is wrong.

[gustavo-depaula]

This is definitively a good idea! Do you have any recommendation on how we can define it?

[Nekvin]

This is how i understood it:
Array[1,3,2,7,6,7,34]
Array.sort();

The remaining numbers would then be 1,3,7,7,34 or if you don't want the same numbers 1,3,7,34.

[luksamuk]

The remaining numbers would then be 1,3,7,7,34 or if you don't want the same numbers 1,3,7,34.

I believe that no extra information should be lost apart from what the algorithm instructs, so the double 7 seems like something that should remain. One other thing is that there should be some well-tested inputs and outputs for comparison.

[rnitta]

Any element which is out of order is eliminated.

There should be more precise definition of "eliminated".

For instance,

in javascript,

stalin-sort/javascript/stalin-sort.js

Line 5 in 174338d

return array.filter((el, i) => {

filtering elements by the functional way can be called "elimination", I think.

in php,

stalin-sort/php/function.php

Line 22 in 174338d

return sort([$x, ...$zs]);

the recursive way also may well be called "elimination".

in haxe,

stalin-sort/haxe/stalin_sort.hx

Line 8 in 2972fd3

sortedArray.push(maxValue = array[index]);

procedurally adding admitted elements to a new array is not appropriate, imo.

Thoughts?

[gabrielcarneiro97]

Any element which is out of order is eliminated.

There should be more precise definition of "eliminated".

For instance,

in javascript,

stalin-sort/javascript/stalin-sort.js

Line 5 in 174338d

return array.filter((el, i) => {

filtering elements by the functional way can be called "elimination", I think.
in php,

stalin-sort/php/function.php

Line 22 in 174338d

return sort([$x, ...$zs]);

the recursive way also may well be called "elimination".
in haxe,

stalin-sort/haxe/stalin_sort.hx

Line 8 in 2972fd3

sortedArray.push(maxValue = array[index]);

procedurally adding admitted elements to a new array is not appropriate, imo.

Thoughts?

I don't think that something so expecific needs to be a concern, for instance filtering in JS returns a new Array, so it's just like adding something to the a new Array, the way that some codes are doing.

[gabrielcarneiro97]

I divided my comment so we can discuss each proposal separately.

One important thing that I thought that needs to be pattern is the way that the function and the codes are written. For example, the Java and the C code have a main function that uses the funcion, this is one think that I see as bad. Look how many lines were used for this purpose:

stalin-sort/java/stalin.java

Lines 16 to 35 in 174338d

	public static void main(String[] args) {
	int arr1[] = new int[]{1, 2, 4, 3, 6, 8, 0, 9, 5, 7};
	int sorted1[] = stalinSort(arr1);
	int arr2[] = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
	int sorted2[] = stalinSort(arr2);
	int arr3[] = new int[]{1, 3, 2, 5, 4, 7, 0, 9, 8, 6};
	int sorted3[] = stalinSort(arr3);
	System.out.print("Original: ");
	System.out.println(Arrays.toString(arr1));
	System.out.print("Sorted: ");
	System.out.println(Arrays.toString(sorted1));
	System.out.print("Original: ");
	System.out.println(Arrays.toString(arr2));
	System.out.print("Sorted: ");
	System.out.println(Arrays.toString(sorted2));
	System.out.print("Original: ");
	System.out.println(Arrays.toString(arr3));
	System.out.print("Sorted: ");
	System.out.println(Arrays.toString(sorted3));
	}

I suggest that all codes needs to be a single function that is exported from the file at its end, just like the JS code. Of course that some languages don't have this feature of exporting a single function, so for this purposes, like Java I guess, the code just exports a class from the file. My point is that the files mustn't have the main function.

stalin-sort/javascript/stalin-sort.js

Lines 1 to 15 in 174338d

	function stalinSort(array) {
	if (!Array.isArray(array)) throw new TypeError('Argument must be an Array!');
	let [holder] = array;
	return array.filter((el, i) => {
	if (i === 0) return true;
	if(el >= holder) {
	holder = el;
	return true;
	}
	return false;
	});
	}
	module.exports = stalinSort

[gabrielcarneiro97]

I divided my comment so we can discuss each proposal separately.

Other point that I think that needs to be pattern is the number of the parameters and the return of the function. All functions must have one param, returns one value and the received argument mustn't be modified, it makes the code easier to understand in any given language.

Good example:

stalin-sort/python/stalin_sort.py

Lines 1 to 9 in 174338d

	def sort(l):
	max_val = l[0]
	def add_val(num):
	nonlocal max_val
	max_val = num
	return num
	return [add_val(x) for x in l if x >= max_val]

Bad example:

stalin-sort/C++/stalin_sort.cpp

Lines 4 to 15 in 174338d

	void stalinSort(std::vector<int> &arr, std::vector<int> &sorted)
	{
	sorted.push_back(arr[0]);
	for (int i = 1, j = 0; i < arr.size(); i++)
	{
	if (arr[i] > arr[j])
	{
	sorted.push_back(arr[i]);
	j++;
	}
	}
	}

[gabrielcarneiro97]

I divided my comment so we can discuss each proposal separately.

Other important thing is the validation and error throwing that needs to be done. Some codes simply don't check if the argument is really an array or a pointer, in some cases. I think that all codes needs to check this, just like here:

stalin-sort/javascript/stalin-sort.js

Line 2 in 174338d

if (!Array.isArray(array)) throw new TypeError('Argument must be an Array!');

Other good checking is check if the array is empty, it's a good improvement for all codes, just like here;

stalin-sort/ruby/stalin_sort.rb

Line 2 in 174338d

return [] if arr.empty?

[gabrielcarneiro97]

Hey mates, could you take a look at PR #68?

[Artoria2e5]

We talk about arrays a lot, but a good(?!) property of Stalin Sort is that it can be done in-place on a linked list, still in O(n) time. In-place sort using an array is also possible, but more complex as you'd need to keep track of the position offset from elimination.