gustavo-depaula/stalin-sort

Add a stalin sort algorithm in any language you like ❣️ if you like give us a ⭐️

Welcome to the Stalin Sort Repo 📋

What is Stalin Sort? ❓

Introduction

Stalin Sort is an efficient sorting algorithm, serving as a systematic method for placing the elements of a random access file or an array in order. Stalin Sort is also know as the best sorting algorithm of all times because of its AMAZING capacity of always ordering an array with an O(n) performance.

How it works?

It's simple, all you need to do is iterate through the array, checking if its elements are in order. Any element that isn't in order you pull out, in other words, you send it to Gulag.

Step-by-step example

1. (1 2 5 3 5 7) -> (1 2 5 3 5 7) Here the algorithm stores the first of element of the array
2. (1 2 5 3 5 7) -> (1 2 5 3 5 7) Now it will compare the stored element with the second one, if this is bigger than the stored, it replaces the stored element by this
3. (1 2 5 3 5 7) -> (1 2 5 3 5 7) Repeats step 2
4. (1 2 5 3 5 7) -> (1 2 5 5 7) Since the 4th element is smaller than the 3rd one, the 4th element will be eliminated.
5. (1 2 5 5 7) -> (1 2 5 5 7) Equal elements are preserved
6. (1 2 5 5 7) Ordered array!

Pseudocode implementation

Keep in mind that this is pseudocode, and is just an example. We strongly encourage you to code a different approach.

FUNCTION stalinSort(A : list OF sortable items)
    n := length(A)
    bigger := 0
    B SET empty list

    FOR i := 0 TO n NOT inclusive DO
        IF A[i] >= bigger THEN
          bigger := A[i]
          B.push(A[i])
        END IF
    END FOR

    RETURN B
END FUNCTION

Want to help? 🙌

Please check the CONTRIBUTING.md

Give this Project a Star! ⭐

About

Stalin sort began first as a Hacktoberfest 2018 repo

Hacktoberfest is a program organised by Digital Ocean and Github, where you can easily win a T-Shirt just by making 5 pull requests in the month of October to any open source projects on Github.

stalin-sort's Issues

Peer Review

It seems like you have implemented StalinSort in more than 30 languages. But have the source codes been peer reviewed enough so that they only contain generic template classes that permits the development of general programs, and do not depend on the underlying container.

I really like this idea because it avoids function overhead and pays strict attention to time complexity of algorithm (always O(N)). But I hope this repository actually provide a structured generic components that can actually be used in a seamless way.

More precise algorithm definition

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.

Test folder

I belive that would be good to have a folder with some default inputs and outputs, so anyone that wants to add some solution in any given language must post with it the outputs of his code too, its kind important to have some sort of validation to the added codes.

My idea is to create a folder with numbered folders in it, related to the number of the test, so if exists 20 tests, the folder tests will contain 20 folders numbered from 1 to 20.

stalin-sort/tests/1...20

In each of this folders will exist 2 .txt files, one called input and other one called output. This files will contain numbers with pipes ( | ) between them.

EXAMPLE

stalin-sort/tests/1

input.txt

1|2|3|4|5|2

output.txt

1|2|3|4|5

hitler>satalin

Proposal: LeninSort

Example

1. (1 2 5 3 5 7) -> total = 23, avg = 3.8
2. (1 2 5 3 5 7) -> low < 3.8
3. (1 2 5 3 5 7) -> high > 3.8
4. (1 2 5 3 5 7) -> (1 2 3) save low in source, (5 5 7) move high to other container

Additional steps:
5. Try sort other containers with LeninSort
6. Merge all first containers
7. You can sort merged container with StalinSort

Python code is incorrect

It gives unsorted array on input 1,5,2,4

Why do we need this shit?

:)

So 3, 4, 5, 6, 7, 8 and 9 are out of order in this array? [1, 2, 50, 3, 4, 5, 6, 7, 8, 9]

Any element which is out of order is eliminated

The 50 is the asshole here, why did the others have to die? Whyyy god whyy?

Other sorting algorithms?

I wonder how other sorting algorithms like: TrumpSort, PutinSort, BidenSort will look like? ))

BogoStalinSort

I propose addition of a new sorting algorithm which combines the best features of both stalinsort and bogosort.

The algorithm is fairly simple:
Just randomly remove elements until the array is in order.

Complexity ranges from O(n) to O(n²)

Hope this will make the world a better place!