• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Wang, Xiao-Dong (Wang, Xiao-Dong.) [1] | Wu, Ying-Jie (Wu, Ying-Jie.) [2]

Indexed by:

EI Scopus SCIE CSCD

Abstract:

A new variant of HEAPSORT is presented in this paper. The algorithm is not an internal sorting algorithm in the strong sense, since extra storage for n integers is necessary. The basic idea of the new algorithm is similar to the classical sorting algorithm HEAPSORT, but the algorithm rebuilds the heap in another way. The basic idea of the new algorithm is it uses only one comparison at each node. The new algorithm shift walks down a path in the heap until a leaf is reached. The request of placing the element in the root immediately to its destination is relaxed. The new algorithm requires about n log n -0.788928n comparisons in the worst case and n log n-n comparisons on the average which is only about 0.4n more than necessary. It beats on average even the clever variants of QUICKSORT, if n is not very small. The difference between the worst case and the best case indicates that there is still room for improvement of the new algorithm by constructing heap more carefully.

Keyword:

analysis of algorithms data structures heaps HEAPSORT

Community:

  • [ 1 ] Fuzhou Univ, Coll Math & Comp Sci, Fuzhou 350002, Peoples R China

Reprint 's Address:

  • 王晓东

    [Wang, Xiao-Dong]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou 350002, Peoples R China

Show more details

Related Keywords:

Related Article:

Source :

JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY

ISSN: 1000-9000

CN: 11-2296/TP

Year: 2007

Issue: 6

Volume: 22

Page: 898-903

0 . 4 4 1

JCR@2007

1 . 2 0 0

JCR@2023

ESI Discipline: COMPUTER SCIENCE;

JCR Journal Grade:3

Cited Count:

WoS CC Cited Count: 3

SCOPUS Cited Count: 7

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Online/Total:50/10034112
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1