Source: https://github.com/LesleyPhillips/cs-LesleySort
I was tutoring myself in C# and .NET and thought it would be fun to try making a Bubble Sort. I simple sort I learned as a teenager.
I was tutoring myself in C# and .NET and thought it would be fun to try making a Bubble Sort. I simple sort I learned as a teenager.
After doing that, I was looking at it and thinking as I move the max value items to the to the right, I could keep track of the lowest value I find in the pass, and move it to the front of the list. Then I thought the process expense of all those shuffles to the max and figured why not just scan for the current max value and shuffle it only once as well.
What I came up with... so I started with a Bubble sort. Then a Bubble-Select hybrid. And crossed over to a Bi-Directional Select sort. From Wikipedia's Sorting Algorithm page, got to the Selection Sort and there you can read about this variant.
Diagrammed, it looks to work like this...
In each loop it finds the min and max values in the unsorted region. Then it shuffles them to the start and end of the unsorted region. and increment and decrements the starting and end point for the next scan. It keeps doing that until they meet in the middle.
While on short list BubbleSort wins. LesleySort wins on larger list. : )
Goodies
Some neat thing to pay attention too...
- I compare the speeds of LesleySort to a BubbleSort by ticks.
- I use LINQ.
- I use Generics.
- I test final sorted data for accuracy against Microsoft built-in OrderBy. (And, I'm assuming their brains are bigger than mine and have better stuff going on there!)
- I use testRepeats to switch from built in list or to let it randomly build large list for larger timing sequencies.
- There is a Shuffel() - good for card games.
- There is a RandomWord - good for making random 3-7 char strings.
I included lot of debug stuff (all the Console.Writelines and loopsCount lines that are REMd out). if you want to see it work make sure to unREM those lines. I recommend doing that only when testRepeats = 1.
Test
The test are loosely set up like this:
original random array
|
+---------+---------+
| |
v v
BubbleSort LesleySort
| |
v v
sorted array sorted array
| |
+---------+---------+
|
SequenceEqual()
|
v
Did they both agree?
LINQ can also provide:
OrderBy()
|
v
"known-good" sorted result
LesleySort results == BubbleSort results == LINQ OrderBy Results!
: D
Run
You're done! : )
![growing sorted growing sorted region unsorted region ↓ ↓ ↓ [ min, min, min | ....................... | max, max, max ] → ← startIndex endIndex](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEillgp4KfnvCp0qjStNwXuw1s0IkVvw_fRaJ-1MXrBSNEO9WI0QzQZ2opRIXctSGG8feAn3qqZxExm-NmJREomIrTWZ_UreDIfeKd8UP-rdRgG3Nls6RGXL7waQN1rnsiZhodTnJsGZbtu7XR-QCehMw0J48own6o53FFbN2E-dyDRTMC9ZjONKBywVcQ0/w665-h141/image.png)
