Parallel Divide-and-Conquer Algorithms for Bubble Sort, Selection Sort and Insertion Sort
| Autor: | Rezaul Chowdhury, Pramod Ganapathi |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Divide and conquer algorithms
Insertion sort 020203 distributed computing Bubble sort Theoretical computer science Selection sort General Computer Science Computer science 0102 computer and information sciences 02 engineering and technology 01 natural sciences 010201 computation theory & mathematics Data_FILES 0202 electrical engineering electronic engineering information engineering |
| Zdroj: | The Computer Journal. |
| ISSN: | 1460-2067 0010-4620 |
| DOI: | 10.1093/comjnl/bxab107 |
| Popis: | We present efficient parallel recursive divide-and-conquer algorithms for bubble sort, selection sort, and insertion sort. Our algorithms have excellent data locality and are highly parallel. The computational complexity of our insertion sort is ${{\mathcal{O}}}\left ({n^{\log _2 3}}\right )$ in contrast to ${{\mathcal{O}}}\left ({n^2}\right )$ of standard insertion sort. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|