explain xkcd - User contributions [en]

3026: Linear Sort

2024-12-18T14:19:53Z

Kazim27: /* Explanation */

{{comic
| number = 3026
| date = December 18, 2024
| title = Linear Sort
| image = linear_sort_2x.png
| imagesize = 385x181px
| noexpand = true
| titletext = The best case is O(n), and the worst case is that someone checks why.
}}

==Explanation==
{{incomplete|Created in Θ(N) TIME by a recursive Bubble Sorter working on a multidimensional array - Please change this comment when editing this page. Do NOT delete this tag too soon.}}
A common task in programming is to sort a list, a list being a collection of related elements of data that are stored in a linear fashion. There are dozens of algorithms that have been created through the years, from simple to complex, and each has its own merits with regards to how easy it is to understand / implement vs. how efficient it operates on the data.

The efficiency of an algorithm is measured in terms of O(), commonly referred to as "Big-O", which classifies the amount of time needed to execute the algorithm with respect to the size of the data. Specifically, the Big-O assignment describes the change in execution time when the size of the data set changes (typically, when it doubles). There are various measures of efficiency, such as:
<ul><li>O(1) - Constant, which means the execution time is independent of the size of the data</li>
<li>O(n) - Linear, which means the execution time varies in direct proportion to the size of the data</li>
<li>O(n log n) - "n log n", usually assigned to the fastest sorting algorithms</li>
<li>O(n2) - Quadratic", meaning the execution time is proportional to the square of the size of the data.</li></ul>
An algorithm that sorts data in Linear time would be a fantastic discovery, as the best general-purpose sorting methods are "n log n".

In computer science, the complexity of a problem can be described using {{w|Big O Notation}}. Operations generally take longer when they act on more elements (notated as "n"). A linear algorithm would be very simple: each element would take a short amount of time on its own, so the time it takes would be a multiple of the size of the list. For instance, if it takes one second to look at a picture, it would take ten seconds to look at ten pictures. So "look at a list of pictures" is a linear operation and would be described as having complexity O(n).

Sorting is more complex. The time it takes to sort a list of items grows quickly as you add more items to the list. The complexity of sorting algorithms generally ranges from O(n^2) to O(n*log n). For example, one way to sort is to look at all the values to find the first item, then look at all the values to find the second item, and so on until you've positioned every item in the right place. If "looking at a number" takes one second, then you could sort a list of 2 numbers in 4 seconds: look at both numbers, then look at them a second time. Sorting 3 numbers would take 9 seconds: look at all 3 numbers 3 times to find the right position. Sorting a deck of cards this way would take 52*52 seconds = about 45 minutes. You can probably read a card more quickly than that, but the point is that the amount of time it takes to sort a list grows faster the more items you are looking at. This is not the most efficient way to sort, but it gets the job done.

The 'linear' sort here uses the more efficient {{w|merge sort}}, which is linearithmic, taking O(n * log n) time. To give the illusion of taking linear time, it tries to make sure it takes 1e6 units of time (likely milliseconds) per item in the list by sleeping for that length of time minus the time it actually took. This will appear to be linear time for up to very large values of n, since linearithmic time will take a huge value of n to exceed the time buffer given by the `sleep()`.

In other words, sorting 20 items will take 10 times as long as sorting 2 items, because after quickly sorting the two items, you just sit around wasting a huge amount of time until it is as slow as sorting a longer list.

The title text refers to the {{w|Best, worst and average case|best and worst case}} of the sort. The best, average and worst case of a merge sort is O(n log n), but this 'linear' sort is pretending that the best case is O(n). The title text then treats 'worst case' as the worst case for the creator of the algorithm (i.e. someone finds out that the sort isn't actually linear), rather than the worst case of the algorithm.

==Transcript==
{{incomplete transcript|Do NOT delete this tag too soon.}}
:function LinearSort(list):
::StartTime=Time()
::MergeSort(list)
::Sleep(1e6*length(list)-(Time()-StartTime))
::return

:[Caption below the panel:]
:How to sort a list in linear time

{{comic discussion}}

[[Category:Programming]]

3026: Linear Sort

2024-12-18T14:12:26Z

Kazim27: /* Explanation */

3026: Linear Sort

2024-12-18T14:05:29Z

Kazim27: /* Explanation */