Stalin Sort
Algorithms
I just saw this picture the other day and it gave me an idea on how to implement this algorithm. Instead of completely getting rid of the elements that are not in order, why not attempt to do StalinSort again on that list of elements that was just removed?
I decided to implement my algorithm in C because I think C is fun and I wanted to play around with C pointers. And with pointers that means I'm going to use a linked list. I didn't need anything complicated for the linked lists so I just made a node struct with two members: An int called "data", and a pointer to the next node.
struct node
{
int data;
struct node* next;
};
In my main function I generate the linked list and then I call my function sendToGulag to weed out the nodes that are not following the rules and "Send them to the gulag".
struct node* sendToGulag(struct node* head)
{
struct node* cur = head;
struct node* gulagHead = NULL;
struct node* gulagCur = NULL;
while(cur->next != NULL)
{
if(cur->data > cur->next->data)
{
if(gulagHead == NULL)
{
gulagHead = cur->next;
gulagCur = cur->next;
}
else
{
gulagCur->next = cur->next;
gulagCur = gulagCur->next;
}
cur->next = cur->next->next;
gulagCur->next = NULL;
}
else
{
cur = cur->next;
}
}
if(gulagHead != NULL)
{
return conscript(sendToGulag(gulagHead), head);
}
else
{
return head;
}
}
As you can see the sendToGulag function recursively calls itself on the nodes that were removed until theres are no more nodes to send to the gulag. Once there are no more dissenters left it's time to conscript everyone!
struct node* conscript(struct node* head1, struct node* head2)
{
struct node* conHead = NULL;
struct node* conCur = NULL;
struct node* cur1 = head1;
struct node* cur2 = head2;
if(cur1->data < cur2->data)
{
conHead = head1;
conCur = head1;
cur1 = cur1->next;
}
else
{
conHead = head2;
conCur = head2;
cur2 = cur2->next;
}
while(cur1 != NULL && cur2 != NULL)
{
if(cur1->data < cur2->data)
{
conCur->next = cur1;
cur1 = cur1->next;
}
else
{
conCur->next = cur2;
cur2 = cur2->next;
}
conCur = conCur->next;
}
if(cur1 != NULL)
{
conCur->next = cur1;
}
else
{
conCur->next = cur2;
}
return conHead;
}
The conscript method is pretty simple. It just takes two nodes that are the heads of two sorted linked lists and combines them together into one sorted linked list. Once all the dissenters are weeded out and everyone is conscripted and a nice big sorted red army is returned.
You can view my full source code here with some added printf statements to show what's going on. Here's a small demo below:
./stalin 1 3 5 7 2 6 3 Line up for headcount! --------- 1 3 5 7 2 6 3 --------- Law abiding comrades: --------- 1 3 5 7 --------- Dissenting criminals: --------- 2 6 3 --------- Line up for headcount! --------- 2 6 3 --------- Law abiding comrades: --------- 2 6 --------- Dissenting criminals: --------- 3 --------- Line up for headcount! --------- 3 --------- Law abiding comrades: --------- 3 --------- Dissenting criminals: --------- --------- Final conscripted headcount: 1 2 3 3 5 6 7
Overall it is a pretty silly algorithm. It's not a divide and conquer algorithm, rather it's a subtract and conquer algorithm. The time complexity of this algorithm can be described with the following recurrence relation:
Where k is the number of law abiding comrades there are. T(n - k) is there because there is one subproblem created with k elements removed from the problem, and + n is there because the extra work of having to conscript the lists together is there.
Though this recurrence relation is not in the form that can be solved using the Master theorem, there is a very similar theorem called the Muster Theorem which can be used to solved this recurrence relation for the worst possible time complexity. I found a pdf that explains more about the Muster Theorem which you can download here.
In short the Muster Theorem states that this algorithm has an upper bound complexity of O(n^2). That makes sense though if you consider the problem of a list being in reverse order. Every person after the first person would be sent to the gulag, and the algorithm would go through the whole list minus one node every time.
The best case scenario would be Ω(n). Because the algorithm would only have to go through the list once and see that everyone is a law abiding comrade.