Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Elmasry, Amr
Hammad, Abdelrahman

dblp
dblp

Not MPG Author(s):

Hammad, Abdelrahman

BibTeX cite key*:

Elmasry2008a

Title

Title*:

Inversion-Sensitive Sorting Algorithms in Practice


ACM-final.pdf (655.66 KB)

Journal

Journal Title*:

ACM Journal of Experimental Algorithmics

Journal's URL:

http://www.jea.acm.org/

Download URL
for the article:

http://delivery.acm.org/10.1145/1460000/1455267/a1_11-elmasry.pdf?key1=1455267&key2=3769984321&coll=GUIDE&dl=GUIDE&CFID=22962513&CFTOKEN=77626302

Language:

English

Publisher

Publisher's
Name:

Association for Computing Machinery

Publisher's URL:

http://www.acm.org/

Publisher's
Address:

New York, USA

ISSN:

1084-6654

Vol, No, pp, Date

Volume*:

13

Number:

1

Publishing Date:

December 2008

Pages*:

1-18

Number of
VG Pages:

18

Page Start:

1

Page End:

18

Sequence Number:

11

DOI:

10.1145/1412228.1455267

Note, Abstract, ©

Note:


(LaTeX) Abstract:

We study the performance of the most practical inversion-sensitive internal sorting algorithms. Experimental results illustrate that adaptive AVL sort consumes the fewest number of comparisons unless the number of inversions is less than $1\%$; in such case Splaysort consumes the fewest number of comparisons. On the other hand, the running time of Quicksort is superior unless the number of inversions is less than $1.5\%$; in such case Splaysort has the shortest running time.
Another interesting result is that although the number of cache misses for the cache-optimal Greedysort algorithm was the least, compared to other adaptive sorting algorithms under investigation, it was outperformed by Quicksort.

URL for the Abstract:

http://portal.acm.org/citation.cfm?id=1412228.1455267

Categories,
Keywords:

Algorithms, Adaptive Sorting, Inversions, Experimentation

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

popular

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{Elmasry2008a,
AUTHOR = {Elmasry, Amr and Hammad, Abdelrahman},
TITLE = {Inversion-Sensitive Sorting Algorithms in Practice},
JOURNAL = {ACM Journal of Experimental Algorithmics},
PUBLISHER = {Association for Computing Machinery},
YEAR = {2008},
NUMBER = {1},
VOLUME = {13},
PAGES = {1--18},
ADDRESS = {New York, USA},
MONTH = {December},
ISBN = {1084-6654},
DOI = {10.1145/1412228.1455267},
}


Entry last modified by Amr Elmasry, 04/07/2009
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Amr Elmassry
Created
02/17/2009 07:44:13 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Amr Elmasry
Anja Becker
Amr Elmasry
Amr Elmasry
Amr Elmasry
Edit Dates
04/07/2009 04:25:59 PM
03/24/2009 12:50:26 PM
03/17/2009 04:41:03 PM
03/17/2009 04:35:59 PM
02/17/2009 08:37:10 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
ACM-final.pdf