1

What sorting algorithm is this? I thought of this method last night and quickly drew up some code, and to my surprise worked perfectly. I've been looking through the Wikipedia article on sorting algorithms and have searched Stack Overflow but have been unable to find this or similar algorithm.

This is the algorithm's written process:

[3, 1, 0, 4]
 ^        ^  Check outermost items, swap if necessary
----------------
[3, 1, 0, 4]
 ^     ^     Check first pair of second farthest apart items, swap if necessary
[0, 1, 3, 4]
----------------
[0, 1, 3, 4]
    ^     ^  Check second pair of second farthest apart items, swap if necessary
----------------
[0, 1, 3, 4]
 ^  ^        Check first pair of third farthest apart items, swap if necessary
----------------
[0, 1, 3, 4]
    ^  ^     Check second pair of third farthest apart items, swap if necessary
----------------
[0, 1, 3, 4]
       ^  ^  Check third pair of third farthest apart items, swap if necessary
----------------
[0, 1, 3, 4]
             Cannot compare closer items (adjacent), done.

This is the algorithm in JavaScript:

var unsorted = [4, 9, 10, 2, 9, 4, 0];
var sorted = ianSort(unsorted);

function ianSort(array) {
    for(var j = array.length; j > 1; j--) {
        for(var i = 0; i < array.length - j + 1; i++) {
            if(array[i] > array[i + j - 1]) {
                var temp = array[i];
                array[i] = array[i + j - 1];
                array[i + j - 1] = temp;
            }
        }
    }
    return array;
}

(I've called the function IanSort here in the unlikely event that I'm the first person to think this up. ^_^)

5
  • @Ian- Are you sure this always works? That is, do you have a correctness proof to suggest that it will work correctly? Also as written I think that this is an O(n^2) sort, so unfortunately I don't think you'll become Rich and Famous from it. Still, it's really cool if it does work! :-) Commented Feb 11, 2011 at 2:25
  • No, it is not O(n^2), it is actually fairly effecient. And yes, I have tested my code thoroughly. Commented Feb 11, 2011 at 2:31
  • it looks quadratic though. The number of operations is 1 + 2 + 3 + ... + array.length, which adds up to O(n^2). Have you tested it on an array with a million elements, for example? Commented Feb 11, 2011 at 2:40
  • yes, it is O(n^2). You have for loops nested two-deep over n. It's not only O(n^2), it's Theta(n^2). Commented Feb 11, 2011 at 2:43
  • Comb sorts are O(n log n), like the quick sort. Commented Feb 11, 2011 at 4:20

4 Answers 4

2

I believe that what you've devised is related to comb sort, which is a generalization of bubble sort that initially starts with a large step size and then decays the step size over time. Traditionally, comb sort works by starting with a large size and then decaying the interval size by a constant factor on each iteration. Your algorithm essentially does this by choosing a constant such that the step size shrinks by one on each iteration.

Sign up to request clarification or add additional context in comments.

3 Comments

Could you care to show me how they are similar in a slightly more detailed way? Sorry, I'm having a hard time matching up the two algorithms.
@Ian: It's an extension of bubble sort in the same sense that Shell sort is an extension of insertion sort.
@Ian- In both comb sort and your sorting algorithm, the sort works by comparing elements at some distance and swapping them based on how they compare with one another. In your algorithm, this works by considering all possible spacings and all possible positions of those spacings. In comb sort, the spacing is initially chosen to be a large value, which is then decreased over time. The main different between your sort and comb sort is how the spacing decreases. Yours chooses all possible spacings, while comb sort decreases the spacing geometrically.
1

Looks like a Comb sort

Comments

0

I'm not quite sure, but it looks like the bubble sort algorithim to me.

Comments

0

This appears to be a form of the Comb Sort algorithm. I also thought I was the first to discover it several years ago and made up several variations to test against the quick sort and other sorting algorithms. You can read about my research here.

It's a fast algorithm that can compete with the quick sort, even beating it under some conditions.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.