Is this a true shell sort??

[PolteRGeisT]

A textbook explained the concept and I created the algorithm, however, the book's code for the sort was a bit more complicated than mine. Here is mine (including a driver program):


#include <iostream.h>

inline void swap(int &, int &);
void shell_sort(int *, int);

int main(void)
{
int *list;
int i, size;

cout << "Enter the size of the array : ";
cin >> size;
list = new int[size];
cout << "\nEnter the array now: " << endl;
for(i=0; i<size; i++) {
cout << i+1 << ":";
cin >> list[i];
}

shell_sort(list, size);

for(i=0; i<size; i++)
cout << list[i] << endl;

return 0;
}

inline void swap(int &a, int &b)
{
a ^= b;
b ^= a;
a ^= b;
}

void shell_sort(int list[], int size)
{
int gap[5] = { 9, 5, 3, 2, 1 };
register int i, j;

for(i=0; i<5; i++) {
for(j=0; (j + gap[i]) < size; j++)
if(list[j] > list[j + gap[i]])
swap(list[j], list[j + gap[i]]);
}
}


Can anyone tell me if I got it right?

[PolteRGeisT]

Arg, just tried it again and it misplaced one of the numbers somehow... I'll repost when I get it right.

[PolteRGeisT]

I think I'm sacrificing some effeciency in the way I'm fixing this bug, but here it is anyway...


#include <iostream.h>

inline void swap(int &, int &);
void shell_sort(int *, int);

int main(void)
{
int *list;
int i, size;

cout << "Enter the size of the array : ";
cin >> size;
list = new int[size];
cout << "\nEnter the array now: " << endl;
for(i=0; i<size; i++) {
cout << i+1 << ":";
cin >> list[i];
}

shell_sort(list, size);

for(i=0; i<size; i++)
cout << list[i] << endl;

return 0;
}

inline void swap(int &a, int &b)
{
a ^= b;
b ^= a;
a ^= b;
}

void shell_sort(int list[], int size)
{
int gap[5] = { 9, 5, 3, 2, 1 };
register int i, j;

for(i=0; i<5; i++) {
for(j=0; (j + gap[i]) < size; j++)
if(list[j] > list[j + gap[i]]) {
swap(list[j], list[j + gap[i]]);
--i; // fix here
break; // and here
}
}
}

[mingshun]

A true shell sort is such that two direct neighbours would swap positions if they are in the wrong positions. The shell sort will only stop sorting if and only if no two neighbours in a list want to sort. This indicates that the list is already sorted.

This is analgous to a tube of liquids that have different density. The higher density liquid will switch position with the lower one til everyone gets to its correct position. (I hope I remembered it correctly as I don't use such an inefficient sort most of the time.)

Hence stricting speaking, yours isn't exactly a shell sort because you did not compare exactly the exact two direct neighbours of a list.

Correct me if I am wrong :p

[PolteRGeisT]

you're thinking of a bubble sort... I think... I don't know anymore...