{"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\/fr\/2022\/07\/29\/binary-insertion-sort\/","title":{"rendered":"Tri par insertion binaire"},"content":{"rendered":"

Le tri par insertion binaire est une variante du tri par insertion dans laquelle la position d’insertion est d\u00e9termin\u00e9e \u00e0 l’aide d’une recherche binaire. La complexit\u00e9 temporelle de l’algorithme est O(n2<\/sup>)<\/p>\n

L’algorithme fonctionne comme ceci\u00a0:<\/p>\n

    \n
  1. Une boucle commence de z\u00e9ro jusqu’\u00e0 la fin de la liste<\/li>\n
  2. Dans la boucle, un nombre est s\u00e9lectionn\u00e9 pour le tri, le nombre est stock\u00e9 dans une variable distincte<\/li>\n
  3. La recherche binaire recherche l’index pour ins\u00e9rer ce num\u00e9ro par rapport aux chiffres de gauche<\/li>\n
  4. Une fois l’index trouv\u00e9, les nombres de gauche sont d\u00e9cal\u00e9s d’une position vers la droite, en commen\u00e7ant \u00e0 l’index d’insertion. Au cours du processus, le num\u00e9ro \u00e0 trier sera effac\u00e9.<\/li>\n
  5. Le num\u00e9ro pr\u00e9c\u00e9demment enregistr\u00e9 est ins\u00e9r\u00e9 \u00e0 l’index d’insertion<\/li>\n
  6. A la fin de la boucle, toute la liste sera tri\u00e9e<\/li>\n<\/ol>\n

    Lors d’une recherche binaire, il est possible que le num\u00e9ro ne soit pas trouv\u00e9 et que l’index ne soit pas renvoy\u00e9. En raison de la particularit\u00e9 de la recherche binaire, le nombre le plus proche de celui recherch\u00e9 sera trouv\u00e9, puis pour renvoyer l’index il faudra le comparer avec celui recherch\u00e9, si celui recherch\u00e9 est inf\u00e9rieur, alors celui recherch\u00e9 doit \u00eatre \u00e0 l’index \u00e0 gauche, et s’il est sup\u00e9rieur ou \u00e9gal, alors \u00e0 droite.<\/p >\n

    Allez code\u00a0:<\/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
    Liens<\/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- trier\/<\/a>
    https:\/\/www.youtube.com\/watch?v=-OVB5pOZJug<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
    Le tri par insertion binaire est une variante du tri par insertion dans laquelle la position d’insertion est d\u00e9termin\u00e9e \u00e0 l’aide d’une recherche binaire. La complexit\u00e9 temporelle de l’algorithme est O(n2) L’algorithme fonctionne comme ceci\u00a0: Une boucle commence de z\u00e9ro jusqu’\u00e0 la fin de la liste Dans la boucle, un nombre est s\u00e9lectionn\u00e9 pour leContinue reading “Tri par insertion binaire”<\/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":"fr","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\/fr\/wp-json\/wp\/v2\/posts\/3337","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/comments?post=3337"}],"version-history":[{"count":7,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/3337\/revisions"}],"predecessor-version":[{"id":3883,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/3337\/revisions\/3883"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/media?parent=3337"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/categories?post=3337"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/tags?post=3337"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}