Review Shell sort and Comb sort descriptions in wikipedia. Your idea about Shell sort having 4 sorting lines is wrong. The two have very similar patterns, but Shell sort is a variation of Insertion sort and Comb sort is a variation of Bubble sort.
Comb/shell sort appears like a great way to make a randomly ordered list ALMOST sorted but not entirely. Like if you wanted to organize a library and called it good enough when every book was less than 5 places from its correct position, you could use comb/shell sort to sort more quickly than another sort that goes to completion.
Except comb/shell DOES go all the way. When it's almost sorted, both comb and shell swap over to what I believe to be Bubble Sort for the last few passes.
This seems reasonably fast in getting data "almost" sorted, but agonisingly slow in the final stages. What if you were to run a few passes on the data, then switch to quick sort - using the centre element of each partially sorted group as the pivot?
That makes things hugely bad for quicksort - the closer you get to "already sorted", the worse quicksort does. The better modern library implementations of quicksort will look at the recursion depth and switch to something like Shell or a simple insertion sort when it encounters the "almost sorted" - or worse, "already sorted" condition. (That is usually called "introsort", for "introspective sort".) This example doesn't really do shellsort justice either, since it uses horrible intervals and thus makes many more passes than necessary.
@@stanrogers5613 Thanks, Stan. You make good points. Most quick sorts use the end element as the pivot, which is a poor choice when (almost) sorted. I'm suggesting using the centre element instead.... but I suppose I'll have to put my money where my mouth is and code it up. No doubt, I'll discover that I'm wrong :-(
Using base 10 is a terrible idea, especially considering it requires the use of div instructions. The most practical is to use base 256, as it means you can simply read the whole byte without the need of any div instructions. Also lsd in place radix uses much more time than it's worth.
Technically possible, but there is no guarantee after each swap that you have finished sorting the list. Assuming 10 elements and only 2 elements are not in sorted order, you have a 1 in 45 chance of picking them. (1 in 10 chance of picking one of the two unsorted elements, 1 in 9 of picking the other unsorted element, * 2 because it won't matter the order) For a 100-long list with only 2 elements not in sorted order, it is 1 in 4950 (1 in 100, 1 in 99, *2)
I implemented Shell sort in 8080 assembler back in 1980 on an Apple ][+ with a Z-80 coprocessor with CP/M. In-memory. Ran like a scalded cat! And, yes, this is a Shell sort. Never heard of 'comb sort', but the logic is evidently similar enough to give some of you a wedgy over the terminology.
It's not shell sort. Shell sort is insertion sort, but with gaps larger than 1 that get smaller over time and eventually reach 1. Comb sort is bubble sort, but with gaps larger than 1 that get smaller over time and eventually reach 1.
Wasn't me, but why not use pretty much any graphics library under the sun? I used SDL to create my own things, which, like most libraries, has a draw line and draw point function.
where are the bleep bloops??
Wrong sort. Shellsort uses more than 2 sorting lines. The sort in the video is Comb sort.
Yeah, I'm pretty sure Shell sort uses 4 sorting lines.
How, why 4 sorting lines? If it compares 2 items...?
KooperSpeederYT
i thought shell sort was just insertion sort with distance
Review Shell sort and Comb sort descriptions in wikipedia. Your idea about Shell sort having 4 sorting lines is wrong. The two have very similar patterns, but Shell sort is a variation of Insertion sort and Comb sort is a variation of Bubble sort.
Actually no comb sort is the one to use multiple comparisons
Comb/shell sort appears like a great way to make a randomly ordered list ALMOST sorted but not entirely. Like if you wanted to organize a library and called it good enough when every book was less than 5 places from its correct position, you could use comb/shell sort to sort more quickly than another sort that goes to completion.
Except comb/shell DOES go all the way. When it's almost sorted, both comb and shell swap over to what I believe to be Bubble Sort for the last few passes.
@@ThePoketrix Or insertion sort
(how) would you use this on physical objects? might be a long way to travel between comparisons.
@@ThePoketrix Not really, they just are effectively the same at the minimum interval.
This isn't Shell Sort. It's just Comb Sort. Shell Sort is Insertion Sort on large intervals. Shell Sort is more sophisticated than this.
that is a comb sort, not a shell sort!
Daniel De Lizaur 昆布は草
@@sasoribi1341 昆布とシェルはどう違うんですか？
This is comb sort!
people in the comments: this is a comb sort!!!!!!!!
me: haha it do the thing and then vwoomp triangle hehe
now these points of data make a beautiful line...
We're out of beta and releasing on time
@@Errenium cuz of all the things we learned!
Is the last one simplified to reduce the comparison window by like 100 instead of one unit?
comb sort is bubble sort
shell sort is insertion sort
This seems reasonably fast in getting data "almost" sorted, but agonisingly slow in the final stages. What if you were to run a few passes on the data, then switch to quick sort - using the centre element of each partially sorted group as the pivot?
That makes things hugely bad for quicksort - the closer you get to "already sorted", the worse quicksort does. The better modern library implementations of quicksort will look at the recursion depth and switch to something like Shell or a simple insertion sort when it encounters the "almost sorted" - or worse, "already sorted" condition. (That is usually called "introsort", for "introspective sort".) This example doesn't really do shellsort justice either, since it uses horrible intervals and thus makes many more passes than necessary.
@@stanrogers5613 Thanks, Stan. You make good points. Most quick sorts use the end element as the pivot, which is a poor choice when (almost) sorted. I'm suggesting using the centre element instead.... but I suppose I'll have to put my money where my mouth is and code it up. No doubt, I'll discover that I'm wrong :-(
Its not lsd in place base 10
Therefore it is beneath me.
There can only be 1 sorting algorithm.
It can only be led in place base 10
Using base 10 is a terrible idea, especially considering it requires the use of div instructions. The most practical is to use base 256, as it means you can simply read the whole byte without the need of any div instructions. Also lsd in place radix uses much more time than it's worth.
I wonder if it is possible to sort a list of any size by randomly picking two numbers and swapping if they are out of order?
Glorified bogo
@@terradasher bogo but smarter
Technically possible, but there is no guarantee after each swap that you have finished sorting the list. Assuming 10 elements and only 2 elements are not in sorted order, you have a 1 in 45 chance of picking them. (1 in 10 chance of picking one of the two unsorted elements, 1 in 9 of picking the other unsorted element, * 2 because it won't matter the order)
For a 100-long list with only 2 elements not in sorted order, it is 1 in 4950 (1 in 100, 1 in 99, *2)
It’s called Exchange Bogo Sort.
I implemented Shell sort in 8080 assembler back in 1980 on an Apple ][+ with a Z-80 coprocessor with CP/M. In-memory. Ran like a scalded cat! And, yes, this is a Shell sort. Never heard of 'comb sort', but the logic is evidently similar enough to give some of you a wedgy over the terminology.
It's not shell sort. Shell sort is insertion sort, but with gaps larger than 1 that get smaller over time and eventually reach 1. Comb sort is bubble sort, but with gaps larger than 1 that get smaller over time and eventually reach 1.
@@SuperfieldCrUn not worth arguing over.
6 years ago... still watch this lol
How are the elements distributed (along which axis)??
Location left-right is their current order in the list, height is their value
isn’t that comb sort? correct me if i’m wrong.
yes it is
what software/program did you use to make this video? would be interested in trying it out myself. love the video
Wasn't me, but why not use pretty much any graphics library under the sun?
I used SDL to create my own things, which, like most libraries, has a draw line and draw point function.
okay, thanks :)
Think it can be made with processing too
Me too
Comments: [insert comments about sorts and stuff]
Me: haha funny line go mmmmm */*
Where sorting noises
Let me guess, you made this song with PaulStretch...
95% This is comb sort!
5% Other comments
This is comb sort, a n log base 1.3 n sort
the first sort is not shell sort its comb sort
Wrong. Its like insertion sort not bubble sort. Comb sort is like bubble.
C'è qualquadra che non cosa
Ha-ha
Shellsort is *_rad_*
This is wrong. Comb sorting is shown, not shellsorting.
Dude, is that a Combsort or a Shellsort?
this is comb sort
Comb lmao
Heh. My last name is Parsons. Neat video.
thats soo fucking smart
wth is going on
What you are watching is a sort visualization of "shell sort". It's actually not shell sort, this is comb sort.
Isr