Created
April 23, 2017 16:43
-
-
Save tmessinis/42907a184beb9780b24a6e9f0f415dc6 to your computer and use it in GitHub Desktop.
Python recursive quicksort
This file contains 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
| import random | |
| test_list = [random.randint(0,100) for num in range(random.randint(10,50))] | |
| #test_list = [1,1,1] | |
| def quick_sort_v2(a_list): | |
| if len(a_list) == 2: | |
| if a_list[0] > a_list[1]: | |
| return [a_list[1], a_list[0]] | |
| else: | |
| return a_list | |
| else: | |
| pivot_val = a_list[0] | |
| left_list = [] | |
| right_list = [] | |
| equal_list = [] | |
| for idx in range(len(a_list)): | |
| if a_list[idx] == pivot_val: | |
| equal_list.append(a_list[idx]) | |
| elif a_list[idx] < pivot_val: | |
| left_list.append(a_list[idx]) | |
| else: | |
| right_list.append(a_list[idx]) | |
| if len(left_list) > 1: | |
| left_list = quick_sort_v2(left_list) | |
| if len(right_list) > 1: | |
| right_list = quick_sort_v2(right_list) | |
| return_list = left_list + equal_list + right_list | |
| return return_list | |
| print(len(test_list)) | |
| print(test_list) | |
| sorted_list = quick_sort_v2(test_list) | |
| print(len(sorted_list)) | |
| print(sorted_list) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment