クイックソートアルゴリズムの計算量について

概要

論文の詳細を見る
In computer science,especially for the algorithmic theory of information,the research of sorting algorithm is very important thema and from computational experiments,the quick sort algorithm,which is discoverd by Hoare[2]is known as fastest ones. However,the worst complexity of this sorting method is very large and for the sort of special data,which include much same data,its performance is less than other sorting method,for example merge sort. So,in this note,first,we analyse the complexity of quick sort and merge sort form theoritical aspect and show that quick sort algorithm is faster than merge sort algorithm,when each data are different. Secondly,we introduce the hash sort algorithm,which can sort numbers very fast. The complexity of sorting n numbers is O(n)and it is smaller than O(n log n),which is the complexity of quick sort or merge sort. Strictly saying,hash sort algorithm is not a sorting algorithm,since it treats only numbers. In this note,we apply the idea of hash sort to general data and propose an algorithm that dividing given general data into the sets of same data. Finally,we use this technic to quick sort algorithm and propose a new sorting method whose worst complexity is faster than that of quick sort.
関東学院大学工学部工学会の論文