I wrote my own sorting algorithm for one of the problems and after looking at the list of sorting algorithms on wikipedia, it looks like my algorithm has not been covered. Thing is, it's simple enough to make me believe that it should have been noticed before... I think it takes O(2) memory and about O(n log n) in terms of computation.
Anyway, the algorithm goes through the original list in sequential order and inserts them into a new list according to a rule based off of the Guessing Game (try to guess a number between x and y in fewest tries). Two bounds are updated as the algorithm progresses; the upper bound and lower bound. The upper bound starts at the length of the new list and the lower bound is 0. The "midpoint" (middle bound) of these two bounds is found and the number at that location in the new list is checked against the current number being inserted. If the midbound number is larger (or equal to) than the number being inserted, the upper bound becomes the middle bound. The lower bound is updated instead if the reverse is true. This process is repeated until the upper bound and lower bound are separated by 1, at which point the new number is inserted between those two indices. The whole process should take log_{2}n operations where n is the length of the new list. It is my experience that this process is rather fast and can also be used to find a member of the list.
A Possibly New Sorting Algorithm
- elendiastarman
- Posts: 410
- Joined: Sat Dec 22, 2007 8:15 pm
A Possibly New Sorting Algorithm
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
Re: A Possibly New Sorting Algorithm
Isn't this just a binary insertion sort?
ex ~100%'er... until the gf came along.
- elendiastarman
- Posts: 410
- Joined: Sat Dec 22, 2007 8:15 pm
Re: A Possibly New Sorting Algorithm
I thought about that too, but the description on wikipedia uses a binary tree and I don't quite see any possible resemblance... :/
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
Re: A Possibly New Sorting Algorithm
http://en.wikipedia.org/wiki/Insertion_sort#Variants discusses it briefly. This is not the same as tree sort.
ex ~100%'er... until the gf came along.
- elendiastarman
- Posts: 410
- Joined: Sat Dec 22, 2007 8:15 pm
Re: A Possibly New Sorting Algorithm
Indeed, that is it. I knew it couldn't have been new...
Want some
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?
3.14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679...?