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.
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.
ok retard
mercurylang.org
just look at how horrifying this TOC is.
This must be the hardest language in the world to learn.
Right?
no, because C++ exists.
It's easier to think you know C++, but you're going to be wrong: youtube.com
That's not O(n).
What other homework do you wish to show us?
>It's easier to think you know C++, but you're going to be wrong: youtube.com
Is there a dress code for these events that requires speakers to dress as faggily as possible? He looks decent in the photo when he's wearing a suit, but he looks just awful on stage. No wonder the field or programming gets no respect when its members act like overgrown toddlers. Sage for OT
12 hours to overturn a fundamental rule of computer science is nothing. Be proud of yourself, OP, and remember us when you collect your ACM award.
This. You seem to have a version of insertion sort, which is O(n^2). You have a while loop inside a for loop.
I'm not sure it's even possible to sort in O(n) time with a linked list, unless you do counting sort with an array and then convert it to a linked list.
Why are you using a linked list in the first place? Also if you do know the length of the list, couldn't you allocate shit at once outside the for loop? I'm thinking it'd be faster since your memory is in one place and you'd avoid some caching bullshit, but if it's a linked list it might not matter anyways.
It's because he's fat. The only way fat people can look okay is wearing a well tailored suit. Donald Trump is a good example of this. In his suits he looks like an absolute boss, but if you see him golf attire, you notice he's quite obese.
It is a convention about C++. Who do you think is the audience? Faggots that care about how other faggots dress or men who care about C++?
spotted the LARPer
___ eye for the C++ guy.
what language is it?
Imagine a Rustcon. Nothing but neckbeard dudes in female cosplay outfits blowing each other.
Typical
Which definition of TOC did you mean?
acronymfinder.com
...
table of contents.
All that shit following the line you quote is taken from the table of contents of the manual linked there.
It's ok user, we all do dumb stuff
Did you come up with any crazy explanations you'd like to share?