Does this look like shell sort to you?

[Sputnik]

/* shellsort: sort v[0]...v[n-1] into increasing order */
void shellsort(int v[], int n)
{
int gap, i, j, temp;
for (gap = n/2; gap > 0; gap /= 2)
for (i = gap; i < n; i++)
for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap) {
temp = v[j];
v[j] = v[j+gap];
v[j+gap] = temp;
}
}

It keeps dividing gap size by 2 which is the correct algorithm, but the next 2 for loops I dont get. Say it chooses gap size of three and compares every third element, how does it sort THOSE elements out? Using bubble sort?
If it eventually uses gap size of, say, three, there could be several elements if you count in 3's within the array. To sort THOSE you must use insertion sort, but this?? All it does is swap ADJACENT elements, so I dont see how you return a completely sorted array. Yet when I run it, its completely sorted???

This code is killing me.

[Sputnik]

Hmmm on second thoughts I maybe answered my own question. It does compare adjascent elements in the innermost for loop but it runs through the entire array (j-=gap) comparing every adjascent element, so its using something like a "sink sort".

[Sputnik]

No it doesnt make sense, no way. On the innermost loop, suppose it has {1,2,4,1,7,2} in the array. It will keep "sinking" "2" in the last element until it hits 1 at which point it will look like {1,2,4,1,2,7}. I'm not getting this code. Ive spent days trying to understand and normally I have no trouble with tripple for loops

[Sputnik]

Loooool i keep double reversing myself into confusion. the array {1,2,4,1,7,2} couldnt have been there in the first place because it sorts one element at a time so it wouldve been built first with, say, example:

Input 2,1 swap = 1,2
Input 1,2,1 swap 1,1,2
Input 1,1,2,5 no action
Input 1,1,2,5,7 no action
Input 1,1,2,5,7,1 swap 1,1,2,5,1,7
Again 1,1,2,1,5,7
Agian 1,1,1,2,5,7

It actually is a "sink sort" in the two innermost loops. But it builds it up from 2 elements upwards.

[ne555]

Indent your code.

for (i = gap; i < n; i++)
	for (j=i-gap; j>=0 && v[j]>v[j+gap]; j-=gap)
		std::swap(v[j], v[j+gap]);

That is insertion sort. You've got a sorted portion, you pick up a value from the unsorted range and put it in the position that it should be in the sorted range.
However you don't have contiguos cells, but separated by a gap. The gap eventually shrink to 1 when it performs the classic insertion sort.

[Sputnik]

ne555 wrote:

That is insertion sort. You've got a sorted portion, you pick up a value from the unsorted range and put it in the position that it should be in the sorted range.
However you don't have contiguos cells, but separated by a gap. The gap eventually shrink to 1 when it performs the classic insertion sort.

Youre correct. It is an insertion sort. You said it perfect, it starts from a small (2 array) sorted portion and then keeps adding an element in and inserting it in the sorted portion.

Just curious... How does this shell sort/insertion sort compare to quicksort? (this forum should have an algorithm section because programming and algorithms go hand in hand. Moderators take note pls!)

[hanst99]

http://en.wikipedia.org/wiki/Sorting_algorithm

This is a C++ forum, not an algorithm forum.