Timeline for Sort a linked-list with only three distinct values
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 16, 2018 at 18:02 | answer | added | ensc | timeline score: 2 | |
| Jun 16, 2018 at 4:11 | history | edited | JDługosz |
change tags
|
|
| Jun 14, 2018 at 23:25 | answer | added | Loki Astari | timeline score: 3 | |
| Jun 14, 2018 at 16:22 | comment | added | Abascus | @Mike Borkland What would be the approach if I were to solve this problem using a single linked list only ? | |
| S Jun 13, 2018 at 16:39 | history | suggested | JVApen |
No c++ specific code in it, especially no c++11. As already contains a good c++ answer, keeping the c++ for now. Adding c as this is c code
|
|
| Jun 13, 2018 at 16:25 | review | Suggested edits | |||
| S Jun 13, 2018 at 16:39 | |||||
| Jun 13, 2018 at 13:32 | answer | added | Incomputable | timeline score: 3 | |
| Jun 13, 2018 at 12:45 | comment | added | Mike Borkland | Yes, counting sort would be ideal for this type of sorting problem, in general. My algorithm takes advantage of the fact that there are only 3 values in the list and also that insertion at the front and back of a doubly linked list is very easy. If you take each 0 and 2 and put them at the front and back of the list, respectively, the 1's are all left in the middle and the list is sorted. | |
| Jun 13, 2018 at 11:55 | comment | added | Incomputable | @MikeBorkland, I believe the easiest is to delpoy counting sort. Writing up an answer on it. Yours would be great too, if algorithm is explained in more detail. | |
| Jun 13, 2018 at 11:54 | comment | added | Mike Borkland |
A better solution: use a doubly linked list. Iterate through the list one time. Whenever a zero is found, splice it out of the list and insert it at the front. Whenever a two is found, splice it out of the list and insert it at the back. You could write splice, insert_front, and insert_back functions and the code would be very simple and elegant.
|
|
| Jun 13, 2018 at 11:16 | history | tweeted | twitter.com/StackCodeReview/status/1006857854765142016 | ||
| Jun 13, 2018 at 9:59 | comment | added | yuri | This looks entirely like ANSI C not like C++ and certainly not like C++11. | |
| Jun 13, 2018 at 9:19 | history | edited | t3chb0t |
edited tags
|
|
| Jun 13, 2018 at 9:07 | history | edited | t3chb0t | CC BY-SA 4.0 |
edited tags & title
|
| Jun 13, 2018 at 9:05 | history | edited | Abascus | CC BY-SA 4.0 |
Added problem description.
|
| Jun 13, 2018 at 9:04 | history | edited | Billal Begueradj | CC BY-SA 4.0 |
inserted your problem statement
|
| Jun 13, 2018 at 8:53 | review | First posts | |||
| Jun 13, 2018 at 9:28 | |||||
| Jun 13, 2018 at 8:50 | history | asked | Abascus | CC BY-SA 4.0 |