What sort algorithm is this?

[Alex Sokolek]

Hi. Does anyone recognize this sort algorithm?

BOOL swap;
tagFileNode* TempNode;
int i, j, diff = 0;
for (j = _NodeCount / 2; j > 0; j /= 2)
{
swap = true;
while (swap)
{
swap = false;
for (i = 0; i + j < _NodeCount; ++i)
{
if (compare(_NodeList[i + 0]->Item, _NodeList[i + j]->Item) > 0)
{
swap = true;
TempNode = _NodeList[i+0];
_NodeList[i+0] = _NodeList[i + j];
_NodeList[i + j] = TempNode;
}
}
}
}


It is similar to a bubble-sort, except that it has an outer loop that runs the interval (j) from half the list, then a quarter of the list, then an eigth of the list, and so on until it is at an interval of 1. I get a factor of ten improvement in performance over the bubble-sort.

I think this is a merge-exchange-sort, but i'm not certain, so I'm asking for insight. Thanks.

p.s. Does anyone know how to include code and keep the indents. I tried tab and spaces - it did not work.

 

[ChatGPT]

Hello,

Your observation is close, but this algorithm is actually the Shellsort algorithm, not a merge-exchange sort. Yes, it is somewhat similar to bubble sort but with some significant improvements.

Shellsort, also known as Shell sort or Shell's method, was invented by Donald Shell in 1959. It is an in-place comparison sort that begins by sorting pairs of elements far apart from each other and progressively reduces the gap between elements being compared. By starting with far apart elements, it can quickly move some out-of-place elements into the right position faster than a simple nearest neighbor exchange.

The algorithm you posted adopts the simple version of Shellsort with a gap sequence [N/2, N/4, N/8, ..., 1]. It uses comparison to compare elements gap distance apart and swaps them if they are in the wrong order, repeating this process until the list is sorted.

Shellsort's performance highly depends on the gap sequence you choose. The 'half-half' sequence you posted is the original sequence used by Shell (worst-case time complexity O(N^2)), but some more complex sequences yield better time complexity (for example, the best known is O(N log^2 N)).

Therefore, you see a significant improvement over simple bubble sort, which has a worst-case and average time complexity of O(N^2) due to the fact that it only swaps adjacent items when they are out of order. Shell's method with the decrease by half sequence improves this by swapping items that are far apart, and then progressively reducing the gap, thus "compacting" the list quicker.

 

[Alex Sokolek]

Hi. Does anyone recognize this sort algorithm. I think it is called a merge exchange sort, but I'm not certain. I learned it many years ago, and I get a factor of ten improvement over the bubble sort. Thank you.

BOOL swap;
tagFileNode* TempNode;
int i, j, diff = 0;
for (j = _NodeCount / 2; j > 0; j /= 2)
{
swap = true;
while (swap)
{
swap = false;
for (i = 0; i + j < _NodeCount; ++i)
{
if (compare(_NodeList[i + 0]->Item, _NodeList[i + j]->Item) > 0)
{
swap = true;
TempNode = _NodeList[i + 0];
_NodeList[i + 0] = _NodeList[i + j];
_NodeList[i + j] = TempNode;
}
}
}
}

 

[ChatGPT]

The algorithm you posted is known as the Shell Sort algorithm, which is an in-place comparison sort. It is a generalized version of insertion sort that allows the exchange of items that are far apart.

The primary idea of the Shell Sort is that it reduces the distance (called the gap) between the elements gradually; hence, it overcomes the problem of traversing and shifting elements over a long distance in a one-go approach that happens in the simple insertion sort. The elements at a significant gap are sorted and the gap size keeps reducing until it becomes 1. When the gap size becomes 1, the algorithm effectively becomes an insertion sort, but by this time the list of elements is already almost sorted, which guarantees the algorithm's effectiveness.

Here's a brief walkthrough of how the algorithm runs:

1. It starts by initializing a gap size which is half of the total number of elements.
2. Then, it starts a loop where it initiates a flag for swapping and continues as long as swapping occurs.
3. Within this loop, another loop runs which iterates through the Nodes and checks if two elements at the gap distance are in the wrong order. If yes, it swaps them and sets the swap flag to true.
4. After going through all the elements once, it checks if any swapping occurred. If yes, it runs the loop again. If no, it reduces the gap size by half and repeats the process.

As you suggested, this is indeed an improvement over bubble sort. Shell Sort performs well on medium size lists and has an average time complexity of O(n(logn)^2), but can degrade to O(n^2) in the worst case.

 

[ChatGPT]

Hello,

The sorting algorithm you've outlined is known as the Shell Sort, invented by Donald L. Shell. This algorithm is indeed akin to the Bubble Sort, but with the enhancement of comparing elements that are a certain distance apart (hence the outer loop where 'j' goes from half the list to a quarter, and so forth). The method provides a performance improvement by minimizing the number of swaps required to sort the list.

Shell Sort's efficiency can fluctuate based on the 'gap sequence' used (the manner in which the distance between the compared elements decreases over time). Various sequences can be used - some provide better efficiency than others.

As for your question about preserving indentation in your code, typically spaces are used instead of tabs to ensure consistency across different editors and platforms. The best way to do this would depend on the text editor or IDE you are using. For many IDEs like Visual Studio Code or Atom, usage of ``` or ~~~ before and after your code snippet preserves the format.

e.g.

```c++
//your code here
```

or

~~~c++
//your code here
~~~

Please check the editor/settings in your specific case. If that doesn't resolve the issue, please provide more specifics about the environment you're using. I hope this helps!

 

[Alex Sokolek]

This is a test. I am testing my ability to provide code examples and retain white-space.

```c++
BOOL swap;
tagFileNode* TempNode;
int i, j, diff = 0;
for (j = _NodeCount / 2; j > 0; j /= 2)
{
swap = true;
while (swap)
{
swap = false;
for (i = 0; i + j < _NodeCount; ++i)
{
switch (SortMode)
{
case 0: // By FileHash, then by FileName
diff = HashCompare(_NodeList->FileHash->c_str(), _NodeList[i + j]->FileHash->c_str());
if (diff == 0) diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
case 1: // By FileName alone
diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
case 2: // By FileDate, then by FileTime, then by FileName
diff = DateCompare(_NodeList->FileDate->c_str(), _NodeList[i + j]->FileDate->c_str());
if (diff == 0) diff = TimeCompare(_NodeList->FileTime->c_str(), _NodeList[i + j]->FileTime->c_str());
if (diff == 0) diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
case 3: // By FileSize, then by FileName
diff = SizeCompare(_NodeList->FileSize->c_str(), _NodeList[i + j]->FileSize->c_str());
if (diff == 0) diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
}
```

 

[Alex Sokolek]

This is also a test.

~~~C++
BOOL swap;
tagFileNode* TempNode;
int i, j, diff = 0;
for (j = _NodeCount / 2; j > 0; j /= 2)
{
swap = true;
while (swap)
{
swap = false;
for (i = 0; i + j < _NodeCount; ++i)
{
switch (SortMode)
{
case 0: // By FileHash, then by FileName
diff = HashCompare(_NodeList->FileHash->c_str(), _NodeList[i + j]->FileHash->c_str());
if (diff == 0) diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
case 1: // By FileName alone
diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
case 2: // By FileDate, then by FileTime, then by FileName
diff = DateCompare(_NodeList->FileDate->c_str(), _NodeList[i + j]->FileDate->c_str());
if (diff == 0) diff = TimeCompare(_NodeList->FileTime->c_str(), _NodeList[i + j]->FileTime->c_str());
if (diff == 0) diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
case 3: // By FileSize, then by FileName
diff = SizeCompare(_NodeList->FileSize->c_str(), _NodeList[i + j]->FileSize->c_str());
if (diff == 0) diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
}
~~~

 

[Alex Sokolek]

This is a third test.

\```
BOOL swap;
tagFileNode* TempNode;
int i, j, diff = 0;
for (j = _NodeCount / 2; j > 0; j /= 2)
{
swap = true;
while (swap)
{
swap = false;
for (i = 0; i + j < _NodeCount; ++i)
{
switch (SortMode)
{
case 0: // By FileHash, then by FileName
diff = HashCompare(_NodeList->FileHash->c_str(), _NodeList[i + j]->FileHash->c_str());
if (diff == 0) diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
case 1: // By FileName alone
diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
case 2: // By FileDate, then by FileTime, then by FileName
diff = DateCompare(_NodeList->FileDate->c_str(), _NodeList[i + j]->FileDate->c_str());
if (diff == 0) diff = TimeCompare(_NodeList->FileTime->c_str(), _NodeList[i + j]->FileTime->c_str());
if (diff == 0) diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
case 3: // By FileSize, then by FileName
diff = SizeCompare(_NodeList->FileSize->c_str(), _NodeList[i + j]->FileSize->c_str());
if (diff == 0) diff = FileCompare(_NodeList->FileName->c_str(), _NodeList[i + j]->FileName->c_str());
break;
}
\```