Parallel Implementation Of Sorting Algorithms

2y ago
689.61 KB
6 Pages
Last View : 9d ago
Last Download : 3m ago
Upload by : Kelvin Chao

IJCSI International Journal of Computer Science Issues, Vol. 9, Issue 4, No 3, July 2012ISSN (Online): 1694-0814www.IJCSI.org164Parallel Implementation of Sorting AlgorithmsMalika Dawra1, and Priti21Department of Computer Science & ApplicationsM.D. University, Rohtak-124001, Haryana, India2Department of Computer Science & ApplicationsM.D. University, Rohtak-124001, Haryana, IndiaAbstractA sorting algorithm is an efficient algorithm, whichperform an important task that puts elements of a list in acertain order or arrange a collection of elements into aparticular order. Sorting problem has attracted a greatdeal of research because efficient sorting is important tooptimize the use of other algorithms such as binarysearch. This paper presents a new algorithm that willsplit large array in sub parts and then all sub parts areprocessed in parallel using existing sorting algorithmsand finally outcome would be merged. To process subparts in parallel multithreading has been introduced.Keywords: sorting, algorithm, splitting, merging, Usage of memory and other computerresources is also a factor in classifying thesorting algorithms. Recursion: some algorithms are eitherrecursive or non recursive, while othersmay be both. Whether or not they are a comparison sortexamines the data only by comparing twoelements with a comparison operator.There are several sorting algorithms available tosort the elements of an array. Some of the sortingalgorithms are:multithreading.Bubble sort1. IntroductionIn the bubble sort, as elements are sorted theygradually “bubble” (or rise) to their proper locationin the array. Bubble sort was analyzed as early as1956 [1]. The bubble sort compares adjacentelements of an array until the complete list getssorted.Sorting is the process of putting data in order; eithernumerically or alphabetically. It is necessary toarrange the elements in an array in numerical orlexicographical order, sorting numerical values indescending order or ascending order andalphabetical value like addressee key [5, 6]. Manyexisting sorting algorithms were observed in termsof the efficiency of the algorithmic complexity [9].All sorting algorithms are appropriate for specifickinds of problems. Some sorting algorithms workon less number of elements, some are used for hugenumber of data, some are used if the list hasrepeated values, and some are suitable for floatingpoint numbers. Sorting is used in many importantapplications and there have been a plenty ofperformance analysis [7]Sorting algorithms are classified by: Computational complexity in terms ofnumber of swaps. Sorting methodsperform various numbers of swaps in orderto sort a data. System complexity of computational. Inthis case, each method of sorting algorithmhas different cases of performance. Theyare worst case, when the integers are not inorder and they have to be swapped at leastonce. The term best case is used todescribe the way an algorithm behavesunder optimal conditions.Selection SortThe selection sort is a combination of sorting andsearching. During each pass, the unsorted elementwith the smallest (or largest) value is moved to itsproper position in the array. The selection sort hasa complexity of O(n2) [3].Insertion SortThe insertion sort splits an array into two subarrays. The first sub-array is sorted and increases insize as the sort continues. The second sub-array isunsorted, contains all the elements yet to beinserted into the first sub-array, and decreases insize as the sort continues. If an application onlyneeds to sort smaller amount of data, then it issuitable to use this algorithm [2].Shell SortThe shell sort repeatedly compares elements thatare a certain distance away from each other. Theshell sort is a “diminishing increment sort”, betterknown as a “comb sort” [8]. The algorithm makesmultiple passes through the list, and each time sortsCopyright (c) 2012 International Journal of Computer Science Issues. All Rights Res

Classify the data in separate arrays on the basis of data type and number of digit Use sorting techniques on them in parallel. And parallel implementation is done using multithreading. Merge sorted array of 1 digit, 2digit, 3 digit ,4 digit, 5 digit , 6 digit and more digit integer and create a large array

Related Documents:

Sorting Algorithms One of the fundamental problems of computer science is ordering a list of items. There's a plethora of solutions to this problem, known as sorting algorithms. Some sorting algorithms are simple and intuitive, such as the bubble sort. Others, such as the quick sort are ex

Efficient Sorting Algorithms!mergesort!sorting complexity!quicksort!animations 2 Two classic sorting algorithms Critical components in the worldÕs computational infrastructure. Full scientific understanding of their properties has enabled us to develop them into practical system sorts. Q

1. Explain in detail about sorting and different types of sorting techniques Sorting is a technique to rearrange the elements of a list in ascending or descending order, which can be numerical, lexicographical, or any user-defined order. Sorting is a process through whi

Sorting: Overview One of the most commonly used and well-studied kernels. Sorting can be comparison-based or noncomparison-based. The fundamental operation of comparison-based sorting is compare-exchange. The lower bound on any comparison-based sort of n numbers is ( nlogn). We focus here

C Plus Data Structures 10 Sorting and Searching Algorithms. 2 Sorting means . . . zThe values stored in an array have keys of a type for which the relational operators are defined. (We also assume unique keys.) zSorting rearranges the

designing other parallel write-efficient algorithms. ACM Reference Format: Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun. 2018. Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry. In SPAA '18: 30th ACM Symposium on Parallelism in Algorithms and Architec-tures, July 16-18, 2018, Vienna, Austria.

3 Parallel Algorithms for Place- ment 3.1 Parallel Moves Approach M o v e 4 m m m Move 3 } Move 2 m Move ! Figure 2: Parallel Moves: Moves 1 and 4 can be done in parallel but not moves 2 and 3 The number of moves evaluated by simulated anneal- ing at each temperature is quite:large. The evaluation

The API commands in this guide are applicable to the Polycom RealPresence Group 300, Polycom RealPresence Group 500, and Polycom RealPresence Group 700 systems.