Bit-index sort: A fast non-comparison integer sorting algorithm for permutations

L. F. Curi-Quintal; J. O. Cadenas; G. M. Megson

doi:10.1109/TAEECE.2013.6557200

Bit-index sort: A fast non-comparison integer sorting algorithm for permutations

L. F. Curi-Quintal, J. O. Cadenas, G. M. Megson

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Citations (Scopus)

Abstract

This paper describes a fast integer sorting algorithm, herein referred to as Bit-index sort, which does not use comparisons and is intended to sort partial permutations. Experimental results exhibit linear complexity order in execution time. Bit-index sort uses a bit-array to classify input sequences of distinct integers, and exploits built-in bit functions in C compilers, supported by machine hardware, to retrieve the ordered output sequence. Results show that Bit-index sort outperforms quicksort and counting sort algorithms when compared in their execution time. A parallel approach for Bit-index sort using two simultaneous threads is also included, which obtains further speedups of up to 1.6 compared to its sequential case.

Original language	English
Title of host publication	2013 The International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013
Pages	83-87
Number of pages	5
DOIs	https://doi.org/10.1109/TAEECE.2013.6557200
Publication status	Published - 2013
Externally published	Yes
Event	2013 International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013 - Konya, Turkey Duration: 9 May 2013 → 11 May 2013

Publication series

Name	2013 The International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013

Conference

Conference	2013 International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013
Country/Territory	Turkey
City	Konya
Period	9/05/13 → 11/05/13

Keywords

bit-array index
counting leading zeros
counting trailing zeros
linear complexity
permutations
sorting algorithm

Access to Document

10.1109/TAEECE.2013.6557200

Cite this

Curi-Quintal, L. F., Cadenas, J. O., & Megson, G. M. (2013). Bit-index sort: A fast non-comparison integer sorting algorithm for permutations. In 2013 The International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013 (pp. 83-87). Article 6557200 (2013 The International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013). https://doi.org/10.1109/TAEECE.2013.6557200

Curi-Quintal, L. F. ; Cadenas, J. O. ; Megson, G. M. / Bit-index sort : A fast non-comparison integer sorting algorithm for permutations. 2013 The International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013. 2013. pp. 83-87 (2013 The International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013).

@inproceedings{7b92cbd80eb4454d8351c5af6b7f57a8,

title = "Bit-index sort: A fast non-comparison integer sorting algorithm for permutations",

abstract = "This paper describes a fast integer sorting algorithm, herein referred to as Bit-index sort, which does not use comparisons and is intended to sort partial permutations. Experimental results exhibit linear complexity order in execution time. Bit-index sort uses a bit-array to classify input sequences of distinct integers, and exploits built-in bit functions in C compilers, supported by machine hardware, to retrieve the ordered output sequence. Results show that Bit-index sort outperforms quicksort and counting sort algorithms when compared in their execution time. A parallel approach for Bit-index sort using two simultaneous threads is also included, which obtains further speedups of up to 1.6 compared to its sequential case.",

keywords = "bit-array index, counting leading zeros, counting trailing zeros, linear complexity, permutations, sorting algorithm",

author = "Curi-Quintal, {L. F.} and Cadenas, {J. O.} and Megson, {G. M.}",

year = "2013",

doi = "10.1109/TAEECE.2013.6557200",

language = "English",

isbn = "9781467356121",

series = "2013 The International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013",

pages = "83--87",

booktitle = "2013 The International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013",

note = "2013 International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013 ; Conference date: 09-05-2013 Through 11-05-2013",

}

Curi-Quintal, LF, Cadenas, JO & Megson, GM 2013, Bit-index sort: A fast non-comparison integer sorting algorithm for permutations. in 2013 The International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013., 6557200, 2013 The International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013, pp. 83-87, 2013 International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013, Konya, Turkey, 9/05/13. https://doi.org/10.1109/TAEECE.2013.6557200

Bit-index sort: A fast non-comparison integer sorting algorithm for permutations. / Curi-Quintal, L. F.; Cadenas, J. O.; Megson, G. M.
2013 The International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013. 2013. p. 83-87 6557200 (2013 The International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Bit-index sort

T2 - 2013 International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013

AU - Curi-Quintal, L. F.

AU - Cadenas, J. O.

AU - Megson, G. M.

PY - 2013

Y1 - 2013

N2 - This paper describes a fast integer sorting algorithm, herein referred to as Bit-index sort, which does not use comparisons and is intended to sort partial permutations. Experimental results exhibit linear complexity order in execution time. Bit-index sort uses a bit-array to classify input sequences of distinct integers, and exploits built-in bit functions in C compilers, supported by machine hardware, to retrieve the ordered output sequence. Results show that Bit-index sort outperforms quicksort and counting sort algorithms when compared in their execution time. A parallel approach for Bit-index sort using two simultaneous threads is also included, which obtains further speedups of up to 1.6 compared to its sequential case.

AB - This paper describes a fast integer sorting algorithm, herein referred to as Bit-index sort, which does not use comparisons and is intended to sort partial permutations. Experimental results exhibit linear complexity order in execution time. Bit-index sort uses a bit-array to classify input sequences of distinct integers, and exploits built-in bit functions in C compilers, supported by machine hardware, to retrieve the ordered output sequence. Results show that Bit-index sort outperforms quicksort and counting sort algorithms when compared in their execution time. A parallel approach for Bit-index sort using two simultaneous threads is also included, which obtains further speedups of up to 1.6 compared to its sequential case.

KW - bit-array index

KW - counting leading zeros

KW - counting trailing zeros

KW - linear complexity

KW - permutations

KW - sorting algorithm

UR - http://www.scopus.com/inward/record.url?scp=84882275174&partnerID=8YFLogxK

U2 - 10.1109/TAEECE.2013.6557200

DO - 10.1109/TAEECE.2013.6557200

M3 - Conference contribution

AN - SCOPUS:84882275174

SN - 9781467356121

T3 - 2013 The International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013

SP - 83

EP - 87

BT - 2013 The International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013

Y2 - 9 May 2013 through 11 May 2013

ER -

Curi-Quintal LF, Cadenas JO, Megson GM. Bit-index sort: A fast non-comparison integer sorting algorithm for permutations. In 2013 The International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013. 2013. p. 83-87. 6557200. (2013 The International Conference on Technological Advances in Electrical, Electronics and Computer Engineering, TAEECE 2013). doi: 10.1109/TAEECE.2013.6557200

Bit-index sort: A fast non-comparison integer sorting algorithm for permutations

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Cite this