Timeline for Median Calculation of List of Integers without using heap
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 13, 2022 at 9:50 | history | edited | Toby Speight |
edited tags
|
|
| Aug 20, 2018 at 0:00 | history | tweeted | twitter.com/StackCodeReview/status/1031330082776920064 | ||
| Aug 16, 2018 at 19:51 | answer | added | Abdur-Rahmaan Janhangeer | timeline score: 0 | |
| Aug 16, 2018 at 16:33 | comment | added | danieltakeshi | @DanielLenz Oh, It was to reuse the number as Integer. Just as the data type of the input. However, if the precision of the program is needed for decimal numbers, then it can be done. | |
| Aug 16, 2018 at 16:18 | comment | added | Daniel Lenz |
@danieltakeshi What do you mean by regular division? The // operator conducts integer division, i.e. 5.5 // 2 = 2. That's not how the median is defined.
|
|
| Aug 16, 2018 at 11:58 | comment | added | Ant | Timsort is a sorting algorithm, and it takes O(n log n) time. Quickselect is not a sorting algorithm, and it takes O(n) time. Quickselect is much faster than timsort for this use case; the key observation is that to get the median you don't need to sort the whole vector, just as if you want to compute the minimum you don't need to sort the whole vector, you can just do one pass over the elements. With the median (and in general with order statistics) it's more complicated, so you use quickselect, but it still has a O(n) performance, much better than your sorting approach which is O(n log n) | |
| Aug 16, 2018 at 11:15 | comment | added | danieltakeshi | @Ant Thanks, i think I misunderstood It. Will study more about heaps. I think that TimSort is already the best algorithm for my case. Just need to use the correct sorting for the data structure that is being used (still learning, so i can be incorrect). | |
| Aug 15, 2018 at 22:39 | comment | added | Ant | I think there is a misunderstanding; the use of heaps and such clever data structures is needed to maintain a rolling median, i.e. you have to return the current median after every number in the input. If you want to call it only once on the final list, then a simple quickselect is enough - that gets you to O(n) time. (If you were to use this algorithm for the rolling mean case, you would need O(1+2+..+n) = O(n^2) time, which is why heaps and other structures are used.) | |
| Aug 15, 2018 at 21:34 | comment | added | Daniel Lenz | Why do you use integer division for a list with even length? Shouldn't it be a regular division of the two center values in the sorted list? | |
| Aug 15, 2018 at 19:47 | answer | added | Acccumulation | timeline score: 4 | |
| Aug 15, 2018 at 19:20 | comment | added | Andre Holzner |
sorting has time complexity O(n log n). You may want to look into Medians of Medians (scroll down for a python implementation) which has linear time complexity.
|
|
| Aug 15, 2018 at 17:34 | answer | added | danieltakeshi | timeline score: 2 | |
| Aug 15, 2018 at 16:47 | vote | accept | danieltakeshi | ||
| Aug 15, 2018 at 13:39 | answer | added | Toby Speight | timeline score: 5 | |
| Aug 15, 2018 at 13:10 | review | First posts | |||
| Aug 15, 2018 at 13:43 | |||||
| Aug 15, 2018 at 13:08 | history | asked | danieltakeshi | CC BY-SA 4.0 |