Vectores

The International Arab Journal of Information Technology, Vol. 7, No. I. Jœmary 2010

55

An Enhancement of Major Sorting Algorithms
Jehad Alnihoud and Rami Mansi Department of Computer Science, Al al-Bayt University, Jordan
Abstract: One of the fundamental issues in computer .science is ordering a ILsi of items. Although there is a huge number of sorting algorithms, sorting problem hasattracted a great deal of research; becattse efftcient sorting is important to optimize the itse of other algorithms. This paper presents two nen- sorting algorithms, enhanced selection .sort atid enhanced bubble Sort algorithtns. Enhanced selection sort is an enhancement on selection sort by making it slightly faster atul stable sorting algorithm. Enhanced bubble sort is an enhancement on bothbubble sort and selection sort algorithms with O(nlgn) complexity in.stead of O(n') for bubble sort and selection sort algorithms. The two new algorithms are analyzed, implemented, tested, and compared and the results were promising. Keywords: Enhanced selection sort, enhanced bubble sort, selection sort, bubble sort, number of swaps, time complexity. Received May 27. 200H: accepted September I, 20081. Introduction
Information growth rapidly in our world and to search for this information, it should he ordered in some sensible order. Many years ago, it was estimated that more than half the time on many commercial computers was spent in sorting. Fortunately this is no longer true. since sophisticated methods have been devised for organizing data, methods which do not require that the databe kept in any special order [9]. Many algorithms are very well known for sorting the unordered lists. Most important of them are Heap sort. Bubble sort. Insertion sort and shell sort [17]. As stated in [5], sorting has been considered as a fundamental problem in the study of algorithms, that due to many reasons: • The need to sort information is inherent in many applications. • Algorithms oftenuse sorting as a key subroutine. • In algorithm design there are many essential techniques represented in the body of sorting algorithms. • Many engineering issues come to the fore when implementing sorting algorithms. Efficient sorting is important to optimize the use of other algorithms that require sorted lists to work correctly; it is also often in producing human-readable output. Formally, theoutput should satisfy two major conditions: • The output is in non-decreasing order. • The output is a pennutation. or reordering, of the input. Since the early beginning of computing, the sorting problem has attracted many researchers, perhaps due to

the complexity of solving it efficiently. Bubble sort was analyzed as early as 1956 [2], Many researchers considered sorting as a solved problem.Even so, useful new sorting algorithms arc still being invented, for example.. Iibrai-y sort was first published in 2004. Sotting algorithms are prevalent in introductory computer science classes, where the abundance of algorithms for the problem provides a gentle introduction to a variety of core algorithm concepts [1, 19]. In [1], they classified sorting algorithms by: • Computationalcomplexity (worst, average and best behavior) of element comparisons in terms of list size (H). For typical soiling algorithms good behavior is O(/7 log n) and bad behavior is Q.{n'^). Ideal behavior for a son is 0{n). Sort algorithms which only use an abstract key comparison operation always need Q(/ïlog«) comparisons in the worst case. • Number of swaps (for in-place algorithms). • Stability: stablesorting algorithms maintain the relative order of records with equal keys (values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list. • Usage of memory and other computer resources. Some sorting algorithms arc "in place", such that only O(l) or O(log n)...