Skip to content

Instantly share code, notes, and snippets.

@Nimdoc

Nimdoc/stalinsort.c

Last active May 13, 2020
Embed
What would you like to do?
StalinSort
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node* conscript(struct node* head1, struct node* head2);
struct node* sendToGulag(struct node* head);
int main(int argc, char *argv[])
{
if(argc == 1)
{
printf("No args!\n");
return 0;
}
struct node* head = NULL;
head = (struct node*)malloc(sizeof(struct node));
head->data = atoi(argv[1]);
struct node* cur = head;
for(int i=2; i<argc; i++)
{
cur->next = (struct node*)malloc(sizeof(struct node));
cur = cur->next;
cur->data = atoi(argv[i]);
}
cur->next = NULL;
head = sendToGulag(head);
printf("\nFinal conscripted headcount:\n");
cur = head;
do
{
printf("%i ", cur->data);
cur = cur->next;
} while(cur != NULL);
printf("\n");
// Free memory
cur = head;
struct node *tmp = NULL;
do
{
tmp = cur;
cur = cur->next;
free(tmp);
} while(cur != NULL);
return 0;
}
/**
* sendToGulag
*
* This function takes a node that is the head of a
* linked list and returns a node that is the head of
* the sorted list.
*
* This function works by taking out nodes that don't conform
* to ascending order and recursively calling sendToGulag
* on those offending nodes.
*
*/
struct node* sendToGulag(struct node* head)
{
printf("Line up for headcount!\n---------\n");
struct node* prt = head;
while(prt != NULL)
{
printf("%i ", prt->data);
prt = prt->next;
}
printf("\n---------\n\n");
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;
}
}
printf("Law abiding comrades:\n---------\n");
prt = head;
while(prt != NULL)
{
printf("%i ", prt->data);
prt = prt->next;
}
printf("\n---------\nDissenting criminals:\n---------\n");
prt = gulagHead;
while(prt != NULL)
{
printf("%i ", prt->data);
prt = prt->next;
}
printf("\n---------\n\n");
if(gulagHead != NULL)
{
return conscript(sendToGulag(gulagHead), head);
}
else
{
return head;
}
}
/**
* conscript
*
* This function takes two nodes that are at the heads
* of two sorted linked lists and combines them together
* into a sorted linked list.
*/
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment