I'm a Senior Software Engineer and it took me 12 hours to implement an O(n) sorting algorithm using a linked list in C...

I'm a Senior Software Engineer and it took me 12 hours to implement an O(n) sorting algorithm using a linked list in C, a programming language I have been using for a decade now.

I kept on forgetting to reassign the contents of the head address when an item was being added to the head of the list.

I want to die inside.

Attached: hqdefault.jpg (480x360, 19.49K)

Other urls found in this thread:

mercurylang.org/information/doc-latest/mercury_ref/index.html
youtube.com/watch?v=PNRju6_yn3o
acronymfinder.com/TOC.html
twitter.com/NSFWRedditVideo

If it makes you feel any better, I feel like much less of a retard now.

Tell us more, user. Do you have some early buggy code and the final result? Why'd you sort the linked list directly instead of mapping it an array, sorting the array, and then mutating the original list according to the sorted array? How long did it take you notice that you were forgetting stuff and what did you do about that? Nothing and keep forgetting? Use a macro that would remember the task for you? How were you testing to see that your sort worked? Just call it from an existing application? Call it from a test suite?

I first wrote it into the existing software, and realized I fucked up. I then created a small test application that did what I wanted and It worked just fine for the inputs I gave it. I then went back and implemented the damn thing and it still didn't work.

so your tests were incomplete? or you broke it while moving it from the test code back into your application?

Yes I didn't consider one of the cases. Simply going back to my test code and using a different case would have solved my problem.

Here's my little shitty piece of code. Ignore the stuff that's not the actual sorting algorithm.

#include "stdio.h"#include "stdlib.h"#define LIST_SIZE 8struct instance_list { int idx; int pri; struct instance_list *next;};int list[LIST_SIZE] = { 2,8,3,4,6,7,1,9};int list_sorted[LIST_SIZE] = {0};void sort(int *list) { struct instance_list *node = NULL; struct instance_list *head = NULL; struct instance_list *curr = NULL; struct instance_list **pp = NULL; for(int i = 0; i < LIST_SIZE; i++) { node = (struct instance_list *)malloc(sizeof(struct instance_list)); node->idx = i; node->pri = list[i]; node->next = NULL; if(head == NULL) { head = node; } else { curr = head; pp = &head; while(curr != NULL) { if(node->pri < curr->pri) { *pp = node; node->next = curr; break; } pp = &curr->next; curr = curr->next; } if(curr == NULL) { *pp = node; } } } node = head; for(int i = 0; node != NULL; i++) { printf("%d ", node->pri); list_sorted[node->idx] = i; curr = node; node = node->next; free(curr); curr = NULL; } printf("\n");}int main(){ for(int i = 0; i < LIST_SIZE; i++) { printf("%d ", list[i]); } printf("\n"); sort(list); for(int i = 0; i < LIST_SIZE; i++) { printf("%d ", list_sorted[i]); }}

please put this god-tier cringe in its own thread.
why give the reader whiplash? use commas to assign node and i at the same time, and then to update i and node at the same time. actually I'd prefer int i = 0; for(node = head; node != NULL; node = node->next) { printf("%d ", node->pri); list_sorted[node->idx] = i++;the mixed variables just looks too much like an error to leave.
does your real code also know the length of the list in advance, or is that part of the arrays that you have for test purposes? if you wrote a cons() and didn't care about garbage collection it'd be just as easy to construct a test list as to use an array like this.
is this sort really O(N)?

The static array was only for testing purposes. I was iterating over a function call to get the contents to be sorted.

Try coding in an environment where an error is thrown if you don't cast the return from malloc.

I was being lazy, the final implementation is just a while(node) with the index being incremented separately.

Attached: no-thank-you.png (1440x810, 587.69K)