Created
July 23, 2017 17:49
-
-
Save coderodde/1a764bd3d5f9cd313cf98a20da3fabf9 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from random import randint | |
| from time import time | |
| def insertionSort(lst): | |
| for i in range(1, len(lst)): | |
| if lst[i] < lst[i-1]: | |
| for j in range(i): | |
| if lst[i] < lst[j]: | |
| lst[i], lst[j] = lst[j], lst[i] | |
| return lst | |
| def straight_insertion_sort(lst): | |
| for i in range(1, len(lst)): | |
| save = lst[i] | |
| j = i | |
| while j > 0 and lst[j - 1] > save: | |
| lst[j] = lst[j - 1] | |
| j -= 1 | |
| lst[j] = save | |
| def create_array(): | |
| arr = [] | |
| for i in range(4000): | |
| arr.append(randint(0, 10000)) | |
| return arr | |
| def millis(): | |
| return int(round(time() * 1000)) | |
| arr1 = create_array() | |
| arr2 = arr1.copy() | |
| start = millis() | |
| insertionSort(arr1) | |
| end = millis() | |
| print("insertionSort in", end - start, "ms.") | |
| start = millis() | |
| straight_insertion_sort(arr2) | |
| end = millis() | |
| print("straight_insertion_sort in", end - start, "ms.") | |
| print("Algorithms agree:", arr1 == arr2) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment