{"action":"created","comment":{"url":"https://api.github.com/repos/jonathanstallings/data-structures/pulls/comments/36346120","id":36346120,"diff_hunk":"@@ -0,0 +1,48 @@\n+\"\"\"This module contains the insertion sort method, which performs an\n+in-place sort on a passed in list. Insertion sort has a best case timeit\n+complexity of O(n) when list is nearly sorted, and a worst case of O(n2)\n+when the incoming list is already reverse sorted. While this not always\n+the most efficient algorithm, it is still popular when the data is nearly\n+sorted (because it is adaptive) or when the problem size is small.\n+See the excellent 'sortingalgorithms.com' for more information.\n+\n+\"\"\"\n+\n+\n+def in_sort(un_list):\n+    \"\"\"Sort a list in place using insertion sort.\n+\n+    args:\n+        un_list: the list to sort\n+    \"\"\"\n+    if type(un_list) is not list:\n+        raise TypeError(\"You must pass a valid list as argument. Do it.\")\n+\n+    for idx in range(1, len(un_list)):\n+        current = un_list[idx]\n+        position = idx\n+\n+        while position > 0 and un_list[position-1] > current:\n+            un_list[position] = un_list[position-1]\n+            position = position - 1\n+\n+        un_list[position] = current\n+\n+if __name__ == '__main__':\n+    BEST_CASE = range(1000)\n+    WORST_CASE = BEST_CASE[::-1]\n+\n+    from timeit import Timer\n+\n+    best = Timer(\n+        'insertion_sort({})'.format(BEST_CASE),\n+        'from __main__ import BEST_CASE, insertion_sort').timeit(1000)\n+\n+    worst = Timer(\n+        'insertion_sort({})'.format(WORST_CASE),\n+        'from __main__ import WORST_CASE, insertion_sort').timeit(1000)\n+\n+    print(\"\"\"Best case represented as a list that is already sorted\\n\n+        Worst case represented as a list that is absolute reverse of sorted\"\"\")\n+    print('Best Case: {}'.format(best))\n+    print('Worst Case: {}'.format(worst))","path":"insertion_sort.py","position":48,"original_position":48,"commit_id":"57a02c9e3bb0ed82ee84a08dbadba0dac4e7f2f4","original_commit_id":"57a02c9e3bb0ed82ee84a08dbadba0dac4e7f2f4","user":{"login":"joelstanner","id":3937302,"avatar_url":"https://avatars.githubusercontent.com/u/3937302?v=3","gravatar_id":"","url":"https://api.github.com/users/joelstanner","html_url":"https://github.com/joelstanner","followers_url":"https://api.github.com/users/joelstanner/followers","following_url":"https://api.github.com/users/joelstanner/following{/other_user}","gists_url":"https://api.github.com/users/joelstanner/gists{/gist_id}","starred_url":"https://api.github.com/users/joelstanner/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/joelstanner/subscriptions","organizations_url":"https://api.github.com/users/joelstanner/orgs","repos_url":"https://api.github.com/users/joelstanner/repos","events_url":"https://api.github.com/users/joelstanner/events{/privacy}","received_events_url":"https://api.github.com/users/joelstanner/received_events","type":"User","site_admin":false},"body":"Assignment calls for multiple list lengths: \"demonstrates the performance characteristics of this sort _over a variety of lengths of input_ in both the best and worst-case scenarios.","created_at":"2015-08-05T19:51:13Z","updated_at":"2015-08-05T19:51:13Z","html_url":"https://github.com/jonathanstallings/data-structures/pull/50#discussion_r36346120","pull_request_url":"https://api.github.com/repos/jonathanstallings/data-structures/pulls/50","_links":{"self":{"href":"https://api.github.com/repos/jonathanstallings/data-structures/pulls/comments/36346120"},"html":{"href":"https://github.com/jonathanstallings/data-structures/pull/50#discussion_r36346120"},"pull_request":{"href":"https://api.github.com/repos/jonathanstallings/data-structures/pulls/50"}}},"pull_request":{"url":"https://api.github.com/repos/jonathanstallings/data-structures/pulls/50","id":41510095,"html_url":"https://github.com/jonathanstallings/data-structures/pull/50","diff_url":"https://github.com/jonathanstallings/data-structures/pull/50.diff","patch_url":"https://github.com/jonathanstallings/data-structures/pull/50.patch","issue_url":"https://api.github.com/repos/jonathanstallings/data-structures/issues/50","number":50,"state":"closed","locked":false,"title":"Insertion sort","user":{"login":"sjschmidt44","id":8696424,"avatar_url":"https://avatars.githubusercontent.com/u/8696424?v=3","gravatar_id":"","url":"https://api.github.com/users/sjschmidt44","html_url":"https://github.com/sjschmidt44","followers_url":"https://api.github.com/users/sjschmidt44/followers","following_url":"https://api.github.com/users/sjschmidt44/following{/other_user}","gists_url":"https://api.github.com/users/sjschmidt44/gists{/gist_id}","starred_url":"https://api.github.com/users/sjschmidt44/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/sjschmidt44/subscriptions","organizations_url":"https://api.github.com/users/sjschmidt44/orgs","repos_url":"https://api.github.com/users/sjschmidt44/repos","events_url":"https://api.github.com/users/sjschmidt44/events{/privacy}","received_events_url":"https://api.github.com/users/sjschmidt44/received_events","type":"User","site_admin":false},"body":"","created_at":"2015-08-03T21:08:51Z","updated_at":"2015-08-05T19:51:13Z","closed_at":"2015-08-04T19:55:35Z","merged_at":"2015-08-04T19:55:35Z","merge_commit_sha":"e0cdd0f5cc33366c4fc7b850c87f38acc878c691","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/jonathanstallings/data-structures/pulls/50/commits","review_comments_url":"https://api.github.com/repos/jonathanstallings/data-structures/pulls/50/comments","review_comment_url":"https://api.github.com/repos/jonathanstallings/data-structures/pulls/comments{/number}","comments_url":"https://api.github.com/repos/jonathanstallings/data-structures/issues/50/comments","statuses_url":"https://api.github.com/repos/jonathanstallings/data-structures/statuses/57a02c9e3bb0ed82ee84a08dbadba0dac4e7f2f4","head":{"label":"jonathanstallings:insertion_sort","ref":"insertion_sort","sha":"57a02c9e3bb0ed82ee84a08dbadba0dac4e7f2f4","user":{"login":"jonathanstallings","id":10945369,"avatar_url":"https://avatars.githubusercontent.com/u/10945369?v=3","gravatar_id":"","url":"https://api.github.com/users/jonathanstallings","html_url":"https://github.com/jonathanstallings","followers_url":"https://api.github.com/users/jonathanstallings/followers","following_url":"https://api.github.com/users/jonathanstallings/following{/other_user}","gists_url":"https://api.github.com/users/jonathanstallings/gists{/gist_id}","starred_url":"https://api.github.com/users/jonathanstallings/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jonathanstallings/subscriptions","organizations_url":"https://api.github.com/users/jonathanstallings/orgs","repos_url":"https://api.github.com/users/jonathanstallings/repos","events_url":"https://api.github.com/users/jonathanstallings/events{/privacy}","received_events_url":"https://api.github.com/users/jonathanstallings/received_events","type":"User","site_admin":false},"repo":{"id":38007754,"name":"data-structures","full_name":"jonathanstallings/data-structures","owner":{"login":"jonathanstallings","id":10945369,"avatar_url":"https://avatars.githubusercontent.com/u/10945369?v=3","gravatar_id":"","url":"https://api.github.com/users/jonathanstallings","html_url":"https://github.com/jonathanstallings","followers_url":"https://api.github.com/users/jonathanstallings/followers","following_url":"https://api.github.com/users/jonathanstallings/following{/other_user}","gists_url":"https://api.github.com/users/jonathanstallings/gists{/gist_id}","starred_url":"https://api.github.com/users/jonathanstallings/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jonathanstallings/subscriptions","organizations_url":"https://api.github.com/users/jonathanstallings/orgs","repos_url":"https://api.github.com/users/jonathanstallings/repos","events_url":"https://api.github.com/users/jonathanstallings/events{/privacy}","received_events_url":"https://api.github.com/users/jonathanstallings/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/jonathanstallings/data-structures","description":"An assignment to implement a singly-linked list in Python","fork":false,"url":"https://api.github.com/repos/jonathanstallings/data-structures","forks_url":"https://api.github.com/repos/jonathanstallings/data-structures/forks","keys_url":"https://api.github.com/repos/jonathanstallings/data-structures/keys{/key_id}","collaborators_url":"https://api.github.com/repos/jonathanstallings/data-structures/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/jonathanstallings/data-structures/teams","hooks_url":"https://api.github.com/repos/jonathanstallings/data-structures/hooks","issue_events_url":"https://api.github.com/repos/jonathanstallings/data-structures/issues/events{/number}","events_url":"https://api.github.com/repos/jonathanstallings/data-structures/events","assignees_url":"https://api.github.com/repos/jonathanstallings/data-structures/assignees{/user}","branches_url":"https://api.github.com/repos/jonathanstallings/data-structures/branches{/branch}","tags_url":"https://api.github.com/repos/jonathanstallings/data-structures/tags","blobs_url":"https://api.github.com/repos/jonathanstallings/data-structures/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/jonathanstallings/data-structures/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/jonathanstallings/data-structures/git/refs{/sha}","trees_url":"https://api.github.com/repos/jonathanstallings/data-structures/git/trees{/sha}","statuses_url":"https://api.github.com/repos/jonathanstallings/data-structures/statuses/{sha}","languages_url":"https://api.github.com/repos/jonathanstallings/data-structures/languages","stargazers_url":"https://api.github.com/repos/jonathanstallings/data-structures/stargazers","contributors_url":"https://api.github.com/repos/jonathanstallings/data-structures/contributors","subscribers_url":"https://api.github.com/repos/jonathanstallings/data-structures/subscribers","subscription_url":"https://api.github.com/repos/jonathanstallings/data-structures/subscription","commits_url":"https://api.github.com/repos/jonathanstallings/data-structures/commits{/sha}","git_commits_url":"https://api.github.com/repos/jonathanstallings/data-structures/git/commits{/sha}","comments_url":"https://api.github.com/repos/jonathanstallings/data-structures/comments{/number}","issue_comment_url":"https://api.github.com/repos/jonathanstallings/data-structures/issues/comments{/number}","contents_url":"https://api.github.com/repos/jonathanstallings/data-structures/contents/{+path}","compare_url":"https://api.github.com/repos/jonathanstallings/data-structures/compare/{base}...{head}","merges_url":"https://api.github.com/repos/jonathanstallings/data-structures/merges","archive_url":"https://api.github.com/repos/jonathanstallings/data-structures/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/jonathanstallings/data-structures/downloads","issues_url":"https://api.github.com/repos/jonathanstallings/data-structures/issues{/number}","pulls_url":"https://api.github.com/repos/jonathanstallings/data-structures/pulls{/number}","milestones_url":"https://api.github.com/repos/jonathanstallings/data-structures/milestones{/number}","notifications_url":"https://api.github.com/repos/jonathanstallings/data-structures/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/jonathanstallings/data-structures/labels{/name}","releases_url":"https://api.github.com/repos/jonathanstallings/data-structures/releases{/id}","created_at":"2015-06-24T19:57:09Z","updated_at":"2015-06-24T21:25:27Z","pushed_at":"2015-08-05T19:16:26Z","git_url":"git://github.com/jonathanstallings/data-structures.git","ssh_url":"git@github.com:jonathanstallings/data-structures.git","clone_url":"https://github.com/jonathanstallings/data-structures.git","svn_url":"https://github.com/jonathanstallings/data-structures","homepage":null,"size":882,"stargazers_count":0,"watchers_count":0,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1,"mirror_url":null,"open_issues_count":3,"forks":1,"open_issues":3,"watchers":0,"default_branch":"master"}},"base":{"label":"jonathanstallings:master","ref":"master","sha":"b68e277b8f0e69e958deb623c3ea18fea7297a57","user":{"login":"jonathanstallings","id":10945369,"avatar_url":"https://avatars.githubusercontent.com/u/10945369?v=3","gravatar_id":"","url":"https://api.github.com/users/jonathanstallings","html_url":"https://github.com/jonathanstallings","followers_url":"https://api.github.com/users/jonathanstallings/followers","following_url":"https://api.github.com/users/jonathanstallings/following{/other_user}","gists_url":"https://api.github.com/users/jonathanstallings/gists{/gist_id}","starred_url":"https://api.github.com/users/jonathanstallings/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jonathanstallings/subscriptions","organizations_url":"https://api.github.com/users/jonathanstallings/orgs","repos_url":"https://api.github.com/users/jonathanstallings/repos","events_url":"https://api.github.com/users/jonathanstallings/events{/privacy}","received_events_url":"https://api.github.com/users/jonathanstallings/received_events","type":"User","site_admin":false},"repo":{"id":38007754,"name":"data-structures","full_name":"jonathanstallings/data-structures","owner":{"login":"jonathanstallings","id":10945369,"avatar_url":"https://avatars.githubusercontent.com/u/10945369?v=3","gravatar_id":"","url":"https://api.github.com/users/jonathanstallings","html_url":"https://github.com/jonathanstallings","followers_url":"https://api.github.com/users/jonathanstallings/followers","following_url":"https://api.github.com/users/jonathanstallings/following{/other_user}","gists_url":"https://api.github.com/users/jonathanstallings/gists{/gist_id}","starred_url":"https://api.github.com/users/jonathanstallings/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jonathanstallings/subscriptions","organizations_url":"https://api.github.com/users/jonathanstallings/orgs","repos_url":"https://api.github.com/users/jonathanstallings/repos","events_url":"https://api.github.com/users/jonathanstallings/events{/privacy}","received_events_url":"https://api.github.com/users/jonathanstallings/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/jonathanstallings/data-structures","description":"An assignment to implement a singly-linked list in Python","fork":false,"url":"https://api.github.com/repos/jonathanstallings/data-structures","forks_url":"https://api.github.com/repos/jonathanstallings/data-structures/forks","keys_url":"https://api.github.com/repos/jonathanstallings/data-structures/keys{/key_id}","collaborators_url":"https://api.github.com/repos/jonathanstallings/data-structures/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/jonathanstallings/data-structures/teams","hooks_url":"https://api.github.com/repos/jonathanstallings/data-structures/hooks","issue_events_url":"https://api.github.com/repos/jonathanstallings/data-structures/issues/events{/number}","events_url":"https://api.github.com/repos/jonathanstallings/data-structures/events","assignees_url":"https://api.github.com/repos/jonathanstallings/data-structures/assignees{/user}","branches_url":"https://api.github.com/repos/jonathanstallings/data-structures/branches{/branch}","tags_url":"https://api.github.com/repos/jonathanstallings/data-structures/tags","blobs_url":"https://api.github.com/repos/jonathanstallings/data-structures/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/jonathanstallings/data-structures/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/jonathanstallings/data-structures/git/refs{/sha}","trees_url":"https://api.github.com/repos/jonathanstallings/data-structures/git/trees{/sha}","statuses_url":"https://api.github.com/repos/jonathanstallings/data-structures/statuses/{sha}","languages_url":"https://api.github.com/repos/jonathanstallings/data-structures/languages","stargazers_url":"https://api.github.com/repos/jonathanstallings/data-structures/stargazers","contributors_url":"https://api.github.com/repos/jonathanstallings/data-structures/contributors","subscribers_url":"https://api.github.com/repos/jonathanstallings/data-structures/subscribers","subscription_url":"https://api.github.com/repos/jonathanstallings/data-structures/subscription","commits_url":"https://api.github.com/repos/jonathanstallings/data-structures/commits{/sha}","git_commits_url":"https://api.github.com/repos/jonathanstallings/data-structures/git/commits{/sha}","comments_url":"https://api.github.com/repos/jonathanstallings/data-structures/comments{/number}","issue_comment_url":"https://api.github.com/repos/jonathanstallings/data-structures/issues/comments{/number}","contents_url":"https://api.github.com/repos/jonathanstallings/data-structures/contents/{+path}","compare_url":"https://api.github.com/repos/jonathanstallings/data-structures/compare/{base}...{head}","merges_url":"https://api.github.com/repos/jonathanstallings/data-structures/merges","archive_url":"https://api.github.com/repos/jonathanstallings/data-structures/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/jonathanstallings/data-structures/downloads","issues_url":"https://api.github.com/repos/jonathanstallings/data-structures/issues{/number}","pulls_url":"https://api.github.com/repos/jonathanstallings/data-structures/pulls{/number}","milestones_url":"https://api.github.com/repos/jonathanstallings/data-structures/milestones{/number}","notifications_url":"https://api.github.com/repos/jonathanstallings/data-structures/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/jonathanstallings/data-structures/labels{/name}","releases_url":"https://api.github.com/repos/jonathanstallings/data-structures/releases{/id}","created_at":"2015-06-24T19:57:09Z","updated_at":"2015-06-24T21:25:27Z","pushed_at":"2015-08-05T19:16:26Z","git_url":"git://github.com/jonathanstallings/data-structures.git","ssh_url":"git@github.com:jonathanstallings/data-structures.git","clone_url":"https://github.com/jonathanstallings/data-structures.git","svn_url":"https://github.com/jonathanstallings/data-structures","homepage":null,"size":882,"stargazers_count":0,"watchers_count":0,"language":"Python","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":1,"mirror_url":null,"open_issues_count":3,"forks":1,"open_issues":3,"watchers":0,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/jonathanstallings/data-structures/pulls/50"},"html":{"href":"https://github.com/jonathanstallings/data-structures/pull/50"},"issue":{"href":"https://api.github.com/repos/jonathanstallings/data-structures/issues/50"},"comments":{"href":"https://api.github.com/repos/jonathanstallings/data-structures/issues/50/comments"},"review_comments":{"href":"https://api.github.com/repos/jonathanstallings/data-structures/pulls/50/comments"},"review_comment":{"href":"https://api.github.com/repos/jonathanstallings/data-structures/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/jonathanstallings/data-structures/pulls/50/commits"},"statuses":{"href":"https://api.github.com/repos/jonathanstallings/data-structures/statuses/57a02c9e3bb0ed82ee84a08dbadba0dac4e7f2f4"}}}}