StalinSort

stalinsort.c

#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;
}