Twin sort algorithm
| Class | Sorting algorithm |
|---|---|
| Data structure | Array |
| Worst-case performance | O(n log n) |
| Best-case performance | O(n - 1) |
| Average performance | O(n log n) |
| Worst-case space complexity | O(n log n) |
Twin Sort
In computer science, various sorting algorithms exist because all sorting methods have varying efficiencies depending on the data structure. As one of the sorting algorithms, Twin Sort Algorithm enables efficient and simple sorting of data structure elements through minimal comparisons and iterations. Twin sorting is an iteration and comparison algorithm introduced by Veeresh Devireddy, Thimmaraju S. N, and Ravish G. K. in the International Journal of Combined Research & Development (IJCRD)[1] in 2014.
Algorithm
Conceptually, the twin sort works in a data structure as follows:
- From the unsorted input data (i.e. array or list), create iterations unequal to the number of elements divided by two.
- The iterations will check every element in the data structure.
- During each iteration, pair elements and then swap elements in the pair if a difference exists.
- If the input data is ordered, finish the sorting process.
- Example of the sorting process:
With the twin sort, the elements of an integer array are sorted into ascending order. Input integer array: 5, 4, 3, 2, 1
Pairing elements 2 by 2: (5, 4) (3, 2), 1 The paired elements are swapped during Iteration 0: (5, 4) (3, 2), 1 → (4, 5) (2, 3), 1 The result after Iteration 0: 4, 5, 2, 3, 1
Iteration 1: 4, (5, 2) (3, 1) → 4, (2, 5) (1, 3) The result after Iteration 1: 4, 2, 5, 1, 3
Iteration 2: (4, 2) (5, 1), 3 → (2, 4) (1, 5), 3 The result after Iteration 2: 2, 4, 1, 5, 3
Iteration 3: 2, (4, 1) (5, 3) → 2, (1, 4) (3, 5) The result after Iteration 3: 2, 1, 4, 3, 5
Iteration 4: (2, 1) (4, 3), 5 → (1, 2) (3, 4), 5 The result after Iteration 4: 1, 2, 3, 4, 5
Analysis of Efficiencies
Two algorithmic complexities check the efficiency of any sorting algorithm:
Time complexity estimates how fast an algorithm executes and the total execution time. Space complexity is the memory an algorithm requires to execute and produce output. The Twin sort algorithm halves the data structure's size, reducing the execution time for comparisons in each iteration. Space complexity indicates the memory needed for calculation depending on the input size.[2] The Twin sort algorithm requires no extra memory during sorting because it uses iteration, which doesn't need stack memory during compiling. This differs from recursion-based sorting algorithms (Quick sort and Merge sort). Pairing only two elements and swapping within those pairs optimizes the algorithm's efficiency.
- Best-case efficiency: For all n input sizes: C (n) = O (n-1)[3]
- Worst-case efficiency: For all n input sizes: C (n) = O ((n-1)*(n/2)) → O (n Log n)[4]
- Average case efficiency: For all n input sizes: C (n) = O ([(n-1)*(n/2)]/2) → O (n Log n)[5]
Scope and Life
Algorithms solve problems. They are crucial in modern technology, forming the core of many computer applications.[6] Sorting algorithms are used in various fields, including computer science and engineering. Some applications of the Twin sort algorithm include:
- Sorting elements or names in Binary Search algorithms.
- Ordering table data structures like DBMS or Hash Tables.
- Ordering files and directories in operating systems like Windows, Linux, and MAC.
- Sorting data frames at the receiver side in Graph Theory and communication networks.
Note
- ↑ Devireddy (2014, p. 35)
- ↑ (Introduction to Algorithms 2008)
- ↑ Devireddy & 20014, p. 36)
- ↑ Devireddy (2014, p. 36)
- ↑ Devireddy (2014, p. 36)
- ↑ (Introduction to Algorithms 2008, p. 14)
References
- Devireddy, Veeresh; S. N, Thimmaraju; G. K., Ravish (2017-11-22). "Twin Sort technique". International Journal of Advance Engineering and Research Development. 3 (4): 370–379. arXiv:1710.07992. Bibcode:2017arXiv171007992D. ISSN 2321-2241.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4. Search this book on
- Skiena, Steven S. (2008). "4.5: Mergesort: Sorting by Divide-and-Conquer". The Algorithm Design Manual (2nd ed.). Springer. pp. 120–125. Bibcode:2008adm..book.....S. ISBN 978-1-84800-069-8. Search this book on
- Knuth, Donald (1998). "Section 5.2.4: Sorting by Merging". Sorting and Searching. The Art of Computer Programming. 3 (2nd ed.). Addison-Wesley. pp. 158–168. ISBN 0-201-89685-0. Search this book on
External links
 |
Wikibooks has a book on the topic of: Algorithm implementation |
- "Animated Sorting Algorithms: Merge Sort". Archived from the original on 6 March 2015. Retrieved 4 June 2019.CS1 maint: BOT: original-url status unknown (link) – merge sort graphical demonstration
This article "Twin sort algorithm" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Twin sort algorithm. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
