Untitled Document
| |
|
| |
RAPID PARTITION SORT (RPS) –A NEW SORTING ALGORITHM |
| |
|
|
| |
|
International Conference on Infomration System, Computer Engineering & Application ( ICISCEA 2011 ) |
| |
|
© 2011 by OLS Journal - ISSN No : 2091-
0266 |
| |
|
Number 1 |
| |
|
Year of Publication : December Issue , 2011 |
| |
|
Authors : Naveen Kumar Goswami |
| |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| |
Citation |
Naveen Kumar Goswami : RAPID PARTITION SORT (RPS) –A NEW SORTING ALGORITHM : OLS Journals Special Isssue onInfomration System, Computer Engineering & Application , 2011 , Published by : OLS Journals |
| |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| |
Abstract |
|
| |
In this paper we are proposing a new sorting algorithm. This sort based on Divide and conquer paradigm with unique feature introducing Parallel Dual Detection which make Rapid Partition Sort much more faster than most of the conventional comparison sorting techniques which can detects data order only in one way either ascending or descending. RPS can detect the data order in both ascending and descending order in parallel and utilize them to maximal effect to reduce the sorting time. We have also shown in this research study comparison of very well known sorting techniques which based on divide and conquer paradigm Quick sort and Merge sort and also with comparison sorts like insertion sort, Selection Sort and Bubble Sort with RPS. And we have shown in this research study that on an average RPS outperform most of the sorting techniques and RPS is very efficient for most of the general cases in practical. |
| |
----------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| |
Keywords |
:Parallel Dual Detection, Comparison sort, Time taken, Partition, Lexicographic |
| |
References : |
|
| |
- http://en.wikipedia.org/wiki/Comparison_sort
- Donald Knuth. The Art of ComputerProgramming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201- 89685-0. pp. 106–110 of section 5.2.2: Sorting by Exchanging.
- Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0., pp. 138–141, of Section 5.2.3: Sorting by Selection.
- Seymour Lipschutz. Theory and Problems of Data Structures,Schaum’s Outline Series: International Edition, McGraw- Hill, 1986. ISBN 0-07-099130-8., pp. 324–325, of Section 9.4: Selection Sort.
- Seymour Lipschutz. Theory and Problems of Data Structures,Schaum’s Outline Series: International Edition, McGraw- Hill, 1986. ISBN 0-07-099130-8., pp. 322–323, of Section 9.3: Insertion Sort.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 7.1:Quicksort, pp.145–149.
- Hoare, C. A. R. "Partition: Algorithm 63," "Quicksort: Algorithm 64," and "Find: Algorithm 65." Comm. ACM 4(7), 321-322, 1961.
- http://en.wikipedia.org/wiki/Count_sort
- R. Cole, “Parallel Merge Sort,” <i>Proc. 27th IEEE Symp. FOCS,</i> pp. 511-516, 1986.
|
|
|
