Computer Science – Artificial Intelligence
Scientific paper
2008-12-05
Computer Science
Artificial Intelligence
Contains 16 pages, 17 figures, 1 table. Text updated as of March 10, 2009. Submitted to a journal
Scientific paper
In this paper we examine sorting on the assumption that we do not know in advance which way to sort a sequence of numbers and we set at work simple local comparison and swap operators whose repeating application ends up in sorted sequences. These are the basic elements of Emerge-Sort, our approach to self-organizing sorting, which we then validate experimentally across a range of samples. Observing an O(n2) run-time behaviour, we note that the n/logn delay coefficient that differentiates Emerge-Sort from the classical comparison based algorithms is an instantiation of the price of anarchy we pay for not imposing a sorting order and for letting that order emerge through the local interactions.
Kalles Dimitris
Kaporis Alexis
No associations
LandOfFree
Emerge-Sort: Converging to Ordered Sequences by Simple Local Operators does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Emerge-Sort: Converging to Ordered Sequences by Simple Local Operators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Emerge-Sort: Converging to Ordered Sequences by Simple Local Operators will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-365637