Timeline for Sort or data structure with fewest comparisons if list is mostly sorted
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 8, 2020 at 15:00 | history | tweeted | twitter.com/StackSoftEng/status/1214924844162277380 | ||
| Nov 25, 2019 at 18:47 | history | edited | dx_over_dt | CC BY-SA 4.0 |
added 296 characters in body
|
| Nov 23, 2019 at 19:33 | vote | accept | dx_over_dt | ||
| Nov 23, 2019 at 0:03 | answer | added | maaartinus | timeline score: 2 | |
| Nov 22, 2019 at 20:00 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Oct 23, 2019 at 19:29 | history | edited | dx_over_dt | CC BY-SA 4.0 |
added 245 characters in body
|
| Oct 23, 2019 at 3:59 | comment | added | Turksarama | You might want to give an example in your question, things like sorting algorithm efficiency are extremely dependent on context. The obvious answer to me is to simply make a note that your list is sorted, and if so just do an insertion sort, if you can't do the obvious thing you should explain why. | |
| Oct 23, 2019 at 3:04 | comment | added | dx_over_dt | That's exactly right. | |
| Oct 23, 2019 at 3:03 | comment | added | Filip Milovanović | Oh, are you saying you are generating a "quiz" based on the possible branching paths of the underlying sorting algorithm that will be presented to the user so that they can interactively provide their choices through the UI, that you will then feed to the underlying code as a data structure to perform the actual sort? And you want to minimize the number of questions they have to answer? | |
| Oct 23, 2019 at 2:26 | comment | added | dx_over_dt | As is stated in the OP, the comparisons are subjective. One person's answer may not be anyone else's over the same data set. I want to minimize the length of the "quiz" that is produced when the user inputs data to sort. The fewer the comparisons, the fewer the clicks. | |
| Oct 23, 2019 at 2:23 | comment | added | Filip Milovanović | P.P.S. "why do you think performance presents an issue at all" - more specifically; suppose you just put all the data in an ordinary array (or a similar structure continuous in memory), and just use a sort method from a standard library of your language to sort the whole thing every time, and not worry about using the most algorithmically efficient way to do it. What makes you think this wouldn't be a perfectly viable solution with good performance? (Furthermore, it might even perform better in practice then the alternatives.) | |
| Oct 23, 2019 at 2:13 | comment | added | Filip Milovanović | P.S. If you can provide more context - it's better to edit the question itself (and maybe just mention that you have done so in the comment section), so that people who didn't read the comments can get the additional info as well. | |
| Oct 23, 2019 at 2:13 | comment | added | Filip Milovanović | I'm sorry if I'm being obtuse, but I'm just trying to better understand what you are trying to do - please be aware that we lack context other then what you provide in your question. You've given us a lot of info on your current train of thought, but not enough on the motivating problem. Your comment doesn't really answer any of my questions. I'm interested in what these two choices are (conceptually, in terms of their role in the application logic), and why do you think performance presents an issue at all. Not really sure what you were trying to say with your physical click remark. | |
| Oct 23, 2019 at 1:55 | comment | added | dx_over_dt | The users click a button give two choices. The number of items won't ever exceed values great enough that a physical click will be faster than doing some data structure operations. | |
| Oct 23, 2019 at 0:39 | comment | added | Filip Milovanović | "In this use case, the comparisons are the only amount of processing time that matters since it requires user input." - not sure what you mean, could you expand a bit? Specifically, what sort of user input, and in what format? Are the users just supplying the comparator function, or is there some more complicated logic involved? Also, have you verified the assumption that the number of comparisons is a good indicator of performance? Have you measured and compared the actual times for different implementations? Because the way you layout data may be more important due to cache (un)friendliness. | |
| Oct 22, 2019 at 19:53 | answer | added | Andrew | timeline score: 1 | |
| Oct 22, 2019 at 19:13 | history | edited | dx_over_dt | CC BY-SA 4.0 |
added 76 characters in body
|
| Oct 22, 2019 at 19:07 | history | asked | dx_over_dt | CC BY-SA 4.0 |