Does anyone know what a gap sort is? Can someone do an example of one?

I know that a gap sort is a variation of a bubble sort. Instead of comparing neighboring elements each time through a list, it compares elements that are some number of positions apart, where the number of positions apart is less then n (number of positions). For example, the first element would be compared to the (i+1) element, the second element would be compared to the (i+2) element, the nth element would be compared to the (n-i) element, etcetera. A sin开发者_开发技巧gle iteration is completed when all of the elements can and are compared. The next iteration i is reduced by some number greater than one and process continues until i is less than one.

This is my understanding of a gap sort but I am having trouble implementing it. Any kind of help would be appreciated.

---

Gap sort is actually a Shell sort. In Bubble sort, that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. Shell sort, instead, works by comparing each element with another element n-gap steps away and this gap reduces by n/2 in next iteration as per shell sort description in link. Last step, n=1, you can do bubble/insertion sort, and thus it is variation of bubble sort.