China
Africa
Explore chapters and articles related to this topic
Parametric Mesh Generation for Optimization
Published in S. Ratnajeevan H. Hoole, Yovahn Yesuraiyan R. Hoole, Finite Elements-based Optimization, 2019
S. Ratnajeevan H. Hoole, Yovahn Yesuraiyan R. Hoole
Sorting is a technique that arranges the elements in a certain order. There are many sorting algorithms such as counting sort, bucket sort, radix sort, merge sort, heapsort, quicksort, etc. (Cormen et al., 2011). Each algorithm has its own advantages. Merge sort is one of the best sort algorithms which has n log (n) time complexity for each average, best, and worst case time complexities (ibid.). Another very important reason for selecting merge sort is that this algorithm is easily parallelizable – parallelization on the GPU is the main theme taken up in a subsequent chapter. Figure 7.21 (Merge Sort, n.d.) describes the merge sort in a graphical way. First, the list is split into two pieces and then each is split into two further pieces. This process is repeated until arriving at the singleton list. Then we work our way back up the recursion by merging together the short arrays into larger arrays. Algorithms 7.2 and 7.3 describe merge sort.
External Memory Data Structures
Published in Suman Saha, Shailendra Shukla, Advanced Data Structures, 2019
Early work on I/O algorithms concentrated on algorithms for sorting and permutation-related problems in the single disk model, as well as in the extended version of the I/O model. In the single disk model, external sorting requires O(nlogmN) I/Os, which is the external equivalent of the well-known (N log N) internal sorting bound. Searching for an element among N elements requires O(logBN) I/Os. More recently external algorithms and data structures have been developed for a number of problems in different areas.
Parallel Structures
Published in M. Michael Vai, Vlsi Design, 2017
Before the end of this chapter, we present a parallel algorithm that sorts n numbers with n PEs connected in a linear array. The objective of this algorithm is to sort a series of n numbers into an ascending order or a descending order. Sorting algorithms implemented in a sequential architecture have complexity ranging from O(nlog2n) to O(n2). This parallel algorithm has a complexity of O(n).
A framework for recursive algorithms in low-energy broadcast networks
Published in International Journal of Parallel, Emergent and Distributed Systems, 2019
Timothy B. Lewis, Quentin F. Stout
Sorting is one of the most fundamental computational building blocks and is used in many important problems in a plethora of areas. An algorithm for sorting n values on n processors is provided in [4]. It requires only energy per processor, but takes time and hence is not optimal. A more practical algorithm was presented in [1] but it still requires time. Because of the broadcast capabilities of processor networks sorting can actually be done in O(n) time. Since at least processors must announce their values O(n) is time optimal. A simple algorithm that achieves this bound is just to have each processor one by one announce their value with every other processor listening and determining the rank of its element. This of course is not energy efficient as each processor is awake for O(n) time. A simple work analysis shows that sorting requires average energy per processor. We now provide a randomised sorting algorithm that meets both these bounds and is energy balanced. We will prove:
Binarily Gapped Binary Insertion Sorting Technique
Published in IETE Journal of Research, 2018
Swapan Kumar Ray, Surajeet Ghosh
Sorting of an array of data elements (DE) is a fundamental operation in computer science and is a basic requirement in many engineering and commercial systems that perform searching or displaying of data. It is also a key subroutine used in running many formal algorithms. A host of different sorting techniques exists [1,2] which often meet the various general performance criteria like sorting time, memory requirement, implementational simplicity, etc. of different applications. An important feature in a sorting technique is its in-place operation which implies that, during the process of sorting, a constant number of DEs of the input unsorted array is ever stored outside the array. Among the most well-known in-place sorting algorithms are the Heap Sort, the Quick Sort, and the Insertion Sort, which, respectively, sorts n numbers in O(nlog n), O(nlog n), and O(n2) time [1,2]. In spite of its relatively poor performance as an in-place sorting technique, the Insertion Sort counts among the popular sorting techniques because it is simple, incremental (i.e., on line), stable, more efficient than most of the other simple O(n2) algorithms like Selection Sort or Bubble Sort, and, finally, its output array remains sorted all the time – both before and after every insertion.
Big data processing with 1D-Crosspoint Arrays
Published in International Journal of Parallel, Emergent and Distributed Systems, 2023
Overall Execution Time: Adding all the terms together, we have which implies that reducing the searching or sorting time beyond offers no benefit. For searching, using a serial algorithm suffices to make the first term since searching each data set of n elements should take time. Therefore, would be equal to in this case. In the case of sorting, a parallel algorithm is required to sort a data set of n elements as a serial sorting algorithm is not sufficient, taking time at best. Parallel sorting algorithms with time complexity of or are well-known ( e.g., see [9, 26]), and sorting n elements with such algorithms will take or time. It is easy to verify that both these terms are less than and hence in this case. Although it may seem that the pursuit for a faster sorting algorithm is no longer needed, this assumes that the data channel width between the memory and the big data would be . If the data channel width can be increased, then can be reduced to or even , in which case, and become the dominating terms of . Under these circumstances, a parallel sorting algorithm with time complexity such as the 1D-Crosspoint Array sorting algorithm suffices to set to .