How does binary insert sort work?
I know how binary search works and also knows how insertion sort works, but this code is about binary insertion sort and I have a problem understanding how it works.
static void Main(string[] args)
{
int[] b = BinarySort(new[] { 4, 3, 7, 1, 9, 6, 2 });
foreach (var i in b)
Console.WriteLine(i);
}
public static int[] BinarySort(int[] list)
{
for (int i = 1; i < list.Length; i++)
{
int low = 0;
int high = i - 1;
int temp = list[i];
//Find
while (low <= high)
{
int mid = (low + high) / 2;
if (temp < list[mid])
high = mid - 1;
else
low = mid + 1;
}
//backward shift
for (int j = i - 1; j >= low; j--)
list[j + 1] = list[j];
list[low] = temp;
}
return list;
}
I don't understand what this part does:
//backward shift
for (int j = i - 1; j >= low; j--)
list[j + 1] = list[j];
list[low] = temp;
and what is the purpose of using binary search here? Can you tell me how binary insert sort works? (C # console)
code source: http://w3mentor.com/learn/asp-dot-net-c-sharp/asp-dot-net-language-basics/binary-insertion-sort-in-c-net/
source to share
Binary insertion sort works like insertion sort, but it separates the location of the insertion point from the actual insertion.
A sort insertion implemented for an array will move the elements at the same time as the insertion point is set. As it scrolls through the items to find the insertion point, it will also shift the items to make room for the insertion.
Binary insertion sort will take advantage of the fact that the sorted items are sorted, so it can use binary search to find the insertion point. Since binary search cannot also move elements to make room for insertion, this must be done in a separate step after the insertion point is found.
The code you want to explain is the code that moves elements to make room for insertion.
source to share