Sorting of Numbers in a Graph-Theoretic Approach

Main Article Content

Sinchan Sengupta
Ritwika Law

Abstract

Till now we have not come across any algorithm that uses graphs to sort any set of numbers (only topological sorts like-Breadth First Search and Depth First Search exist). Our aim in this paper is to sort a set of numbers in either ascending or descending order, using undirected weighted graphs and is based on already existing Kruskal’s algorithm. This paper highlights this new application of the algorithm and the fact that it can be extended to sorting numbers as well. The given set of numbers to be sorted are assigned to the vertices of the graph and the edges incident to that ordered pair of vertices are assigned some integer value(weights) based on which the sorting is done. The complexity of the algorithm in this paper is in accordance with the complexities of already existing sorting algorithms.

 


Keywords: Graph completeness, ‘good’ graphs, sorting, Kruskal’s Algorithm, complexity.

Downloads

Download data is not yet available.

Article Details

Section
Articles