Relating bubble sort to birthday problem
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909321583919104 |
|---|---|
| author | Jiang, Jichu |
| author_facet | Jiang, Jichu |
| contents | Birthday problem is a well-known classic problem in probability theory widely applied in cryptography, and bubble sort is a popular sorting algorithm leading to some interesting theoretical problems in computer science. However, the relation between bubble sort and birthday problem has not been discovered. By relating bubble sort to birthday problem, based on a generalization of Poisson limit theorem for dissociated random variables, this paper offers an intuitive explanation to naturally indicate that $\displaystyle \frac{n - P_{n}}{\sqrt{n}}$ converges in distribution to the standard Rayleigh distribution, where $P_{n}$ is the number of passes required to bubble sort $n$ distinct elements. Then asymptotic distributions and statistical characteristics of bubble sort and birthday problem are presented. Moreover, this paper discovers that some common optimizations of bubble sort could lead to average performance degradation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_11170 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Relating bubble sort to birthday problem Jiang, Jichu Probability 60C02 (Primary), 68R02 (Secondary) G.3; G.1.2; G.2.1 Birthday problem is a well-known classic problem in probability theory widely applied in cryptography, and bubble sort is a popular sorting algorithm leading to some interesting theoretical problems in computer science. However, the relation between bubble sort and birthday problem has not been discovered. By relating bubble sort to birthday problem, based on a generalization of Poisson limit theorem for dissociated random variables, this paper offers an intuitive explanation to naturally indicate that $\displaystyle \frac{n - P_{n}}{\sqrt{n}}$ converges in distribution to the standard Rayleigh distribution, where $P_{n}$ is the number of passes required to bubble sort $n$ distinct elements. Then asymptotic distributions and statistical characteristics of bubble sort and birthday problem are presented. Moreover, this paper discovers that some common optimizations of bubble sort could lead to average performance degradation. |
| title | Relating bubble sort to birthday problem |
| topic | Probability 60C02 (Primary), 68R02 (Secondary) G.3; G.1.2; G.2.1 |
| url | https://arxiv.org/abs/2404.11170 |