Is it shell sorting or insertion sorting?

Question

I am just starting to learn sorting algorithms and discover one online. At first, I thought it was a kind of shell, but it skips this separate “k” interval and half the array, so I'm not sure if it is or not. My second guess is insertion sort, but I'm just here to double check:

for(n = 1; n < num; n++) { key = A[n]; k = n; while((k > 0) && (A[k-1] > key)) { A[k] = A[k-1]; k = k-1; } A[k] = key; } 

Also, if you can explain why this would be useful as well

Answer 1

Shell Sort consists of many insertion sorts that are performed on subarrays of the original array.

The code you provided is an insertion sort.

To get the look of the shell, it will roughly have a different for around your code, changing h (this space in the sorting of the shell) and the starting index of the sub-array and inside, instead of going from k to k-1 , you go from k to k+h (or kh depending on which direction you are inserting the sort)

Answer 2

I think you're right, this is very similar to sorting an insert .

This fragment assumes that A[0] already inserted. If n == 0 , then the check k > 0 will fail, and execution will continue to work in A[k] = key; by correctly storing the first element in the array.

This snippet also suggests that A[0:n-1] already sorted. It checks A[n] and starts scanning the array backward, moving forward in one place each element that is larger than the original A[n] .

As soon as the scan finds an element that is less than or equal to the key, it inserts it into this place.

Answer 3

It is called insertion sort, because the string A[k] = key inserts the current value into the correct position in a partially sorted array.