Mutaz Rasmi Abu Sara
Taibah University

Published : 2 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 2 Documents
Search

A Parallel Implementation of Dual-Pivot Quick Sort for Computers with Small Number of Processors Mohammad F. J. Klaib; Mutaz Rasmi Abu Sara; Masud Hasan
Indonesia Journal on Computing (Indo-JC) Vol. 5 No. 2 (2020): September, 2020
Publisher : School of Computing, Telkom University

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.34818/INDOJC.2020.5.2.487

Abstract

Sorting algorithms are heavily used. Quicksort is one of the fastest comparison-based sorting algorithms. These days almost all computing devices have multiple processors. There is a strong need of finding efficient parallel versions of the most common algorithms that are widely used. The basic version of quick sort is sequential and uses only one pivot.  Recently, Yaroslavsky has proposed a modified version of the quick sort that uses two pivots and runs much faster than the single-pivot quick sort. Since then Java has incorporated this dual-pivot quick sort into its standard library for sorting. Although there are many parallel versions of the original single-pivot quick sort, there is a very few for the dual-pivot. Those few parallel versions of the dual-pivot quick sorts are compared with standard sort functions, rather than the dual-pivot quick sort itself. In this paper, we provide a parallel version of the dual-pivot quick sort algorithm of Yaroslavsky and implement it in Java. For comparison, we run both in small number of parallel processors. The experimental results show that our algorithm runs significantly faster than the Yaroslavsky’s algorithm. Moreover, our algorithm performs gradually better as the number of processors and the input size increase.
Hybrid Array List: An Efficient Dynamic Array with Linked List Structure Mutaz Rasmi Abu Sara; Mohammad F. J. Klaib; Masud Hasan
Indonesia Journal on Computing (Indo-JC) Vol. 5 No. 3 (2020): December, 2020
Publisher : School of Computing, Telkom University

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.34818/INDOJC.2020.5.3.527

Abstract

In this paper, we present an efficient dynamic array, called hybrid array list (HAL), whose structure is a linked list and each node is an array. In a HAL H, each node, called a chunk, is an array of size at most 2c, where c is an initial array size determined by the user. As the elements are added or deleted in H, it grows or shrinks by the number of nodes in the linked list as well as by the sizes of the chunks. We consider the operations append, insert and delete as well as a helping operation actual position in H. These operations run in O(1), O(m+c), O(m+c) and O(m) time, respectively, in worst case, where m is the number of chunks in H. These running times are much less than the worst case running time, which is O(n), where n is the total number of elements in H, taken by these operations in linked list or array. We implement HAL and compare these operations with similar operations in array list of Java and vector of C++. Our results show that H can perform substantially better when c is about half of the total number of elements.