{"id":3337,"date":"2022-07-29T11:07:42","date_gmt":"2022-07-29T08:07:42","guid":{"rendered":"https:\/\/demensdeum.com\/blog\/?p=3337"},"modified":"2024-12-16T22:32:18","modified_gmt":"2024-12-16T19:32:18","slug":"binary-insertion-sort","status":"publish","type":"post","link":"https:\/\/demensdeum.com\/blog\/2022\/07\/29\/binary-insertion-sort\/","title":{"rendered":"Binary Insertion Sort"},"content":{"rendered":"

Binary Insertion Sort is a variant of insertion sort in which the insertion position is determined using binary search. The time complexity of the algorithm is O(n2<\/sup>)<\/p>\n

The algorithm works like this:<\/p>\n

    \n
  1. Starts a loop from zero to the end of the list<\/li>\n
  2. In the loop, a number is selected for sorting, the number is saved in a separate variable<\/li>\n
  3. Binary search finds the index to insert this number compared to the numbers to the left<\/li>\n
  4. Once the index is found, the numbers on the left are shifted one position to the right, starting with the insertion index. The process will erase the number you want to sort.<\/li>\n
  5. The previously saved number is inserted at the insertion index<\/li>\n
  6. At the end of the loop, the entire list will be sorted<\/li>\n<\/ol>\n

    During binary search, a situation is possible when the number will not be found, but the index is not returned. Due to the peculiarity of binary search, the number closest to the desired one will be found, then to return the index it will be necessary to compare it with the desired one, if the desired one is less, then the desired one should be on the left by index, and if it is greater or equal, then on the right.<\/p>\n

    Go code:<\/p>\n

    \n
    \n
    \nimport (\n\t\"fmt\"\n\t\"math\/rand\"\n\t\"time\"\n)\n\nconst numbersCount = 20\nconst maximalNumber = 100\n\nfunc binarySearch(numbers []int, item int, low int, high int) int {\n\tfor high > low {\n\t\tcenter := (low + high) \/ 2\n\t\tif numbers[center] < item { low = center + 1 } else if numbers[center] > item {\n\t\t\thigh = center - 1\n\t\t} else {\n\t\t\treturn center\n\t\t}\n\t}\n\n\tif numbers[low] < item {\n\t\treturn low + 1\n\t} else {\n\t\treturn low\n\t}\n}\n\nfunc main() {\n\trand.Seed(time.Now().Unix())\n\tvar numbers [numbersCount]int\n\tfor i := 0; i < numbersCount; i++ {\n\t\tnumbers[i] = rand.Intn(maximalNumber)\n\t}\n\tfmt.Println(numbers)\n\n\tfor i := 1; i < len(numbers); i++ { searchAreaLastIndex := i - 1 insertNumber := numbers[i] insertIndex := binarySearch(numbers[:], insertNumber, 0, searchAreaLastIndex) for x := searchAreaLastIndex; x >= insertIndex; x-- {\n\t\t\tnumbers[x+1] = numbers[x]\n\t\t}\n\t\tnumbers[insertIndex] = insertNumber\n\t}\n\tfmt.Println(numbers)\n}\n<\/code><\/pre>\n<\/div>\n<\/div>\n
    Links<\/h3>\n
    https:\/\/gitlab.com\/demensdeum\/algorithms\/-\/blob\/master\/sortAlgorithms\/binaryInsertionSort\/binaryInsertionSort.go<\/a><\/p>\n
    Sources<\/h3>\n
    https:\/\/www.geeksforgeeks.org\/binary-insertion- sort\/<\/a>
    https:\/\/www.youtube.com\/watch?v=-OVB5pOZJug<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
    Binary Insertion Sort is a variant of insertion sort in which the insertion position is determined using binary search. The time complexity of the algorithm is O(n2) The algorithm works like this: Starts a loop from zero to the end of the list In the loop, a number is selected for sorting, the number isContinue reading “Binary Insertion Sort”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[61,52],"tags":[131,198,190],"class_list":["post-3337","post","type-post","status-publish","format-standard","hentry","category-techie","category-tutorials","tag-algorithms","tag-binary-insertion-sort","tag-sorting","entry"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"en","enabled_languages":["en","ru","zh","de","fr","ja","pt"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/posts\/3337","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/comments?post=3337"}],"version-history":[{"count":7,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/posts\/3337\/revisions"}],"predecessor-version":[{"id":3883,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/posts\/3337\/revisions\/3883"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/media?parent=3337"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/categories?post=3337"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/wp-json\/wp\/v2\/tags?post=3337"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}