SHOW:
|
|
- or go back to the newest paste.
1 | def binary_search(numbers, target): | |
2 | left = 0 | |
3 | right = len(numbers) - 1 | |
4 | while left <= right: | |
5 | mid_index = (left + right) // 2 | |
6 | mid_el = numbers[mid_index] | |
7 | if mid_el == target: | |
8 | return mid_index | |
9 | ||
10 | if mid_el < target: | |
11 | left = mid_index + 1 | |
12 | else: | |
13 | right = mid_el - 1 | |
14 | ||
15 | return "Not Found" | |
16 | ||
17 | # //////////////////////////////////////////////// | |
18 | ||
19 | def selection_sort(numbers): | |
20 | for index in range(len(numbers)): | |
21 | min_index = index | |
22 | for curr_index in range(index + 1, len(numbers)): | |
23 | if numbers[curr_index] < numbers[min_index]: | |
24 | min_index = curr_index | |
25 | ||
26 | numbers[index], numbers[min_index] = numbers[min_index], numbers[index] | |
27 | ||
28 | return numbers | |
29 | ||
30 | # //////////////////////////////////////////////// | |
31 | ||
32 | def bubble_sort_1(numbers): | |
33 | is_sorted = False | |
34 | counter = 0 | |
35 | while not is_sorted: | |
36 | is_sorted = True | |
37 | for index in range(1, len(numbers) - counter): | |
38 | if numbers[index] < numbers[index - 1]: | |
39 | numbers[index], numbers[index - 1] = numbers[index - 1], numbers[index] | |
40 | is_sorted = False | |
41 | counter += 1 | |
42 | ||
43 | return numbers | |
44 | ||
45 | # //////////////////////////////////////////////// | |
46 | ||
47 | def bubble_sort_2(numbers): | |
48 | for i in range(len(numbers)): | |
49 | for j in range(1, len(numbers) - i): | |
50 | if numbers[j - 1] > numbers[j]: | |
51 | numbers[j], numbers[j - 1] = numbers[j - 1], numbers[j] | |
52 | return numbers | |
53 | ||
54 | # //////////////////////////////////////////////// | |
55 | ||
56 | def insertion_sort(numbers): | |
57 | for i in range(1, len(numbers)): | |
58 | for j in range(i, 0, -1): | |
59 | if numbers[j] < numbers[j - 1]: | |
60 | numbers[j], numbers[j - 1] = numbers[j - 1], numbers[j] | |
61 | else: | |
62 | break | |
63 | ||
64 | return numbers | |
65 | ||
66 | # //////////////////////////////////////////////// | |
67 | ||
68 | def quick_sort(start, end, nums): | |
69 | if start >= end: | |
70 | return | |
71 | ||
72 | pivot, left, right = start, start + 1, end | |
73 | ||
74 | while left <= right: | |
75 | if nums[left] > nums[pivot] > nums[right]: | |
76 | nums[left], nums[right] = nums[right], nums[left] | |
77 | if nums[left] <= nums[pivot]: | |
78 | left += 1 | |
79 | if nums[right] >= nums[pivot]: | |
80 | right -= 1 | |
81 | ||
82 | nums[pivot], nums[right] = nums[right], nums[pivot] | |
83 | quick_sort(start, right - 1, nums) | |
84 | quick_sort(left, end, nums) | |
85 | ||
86 | ||
87 | nums = [int(x) for x in input().split()] | |
88 | quick_sort(0, len(nums) - 1, nums) | |
89 | print(*nums, sep=' ') | |
90 | ||
91 | # //////////////////////////////////////////////// | |
92 | ||
93 | def merge_arrays(left, right): | |
94 | result = [None] * (len(left) + len(right)) | |
95 | left_idx = 0 | |
96 | right_idx = 0 | |
97 | result_idx = 0 | |
98 | ||
99 | while left_idx < len(left) and right_idx < len(right): | |
100 | if left[left_idx] < right[right_idx]: | |
101 | result[result_idx] = left[left_idx] | |
102 | left_idx += 1 | |
103 | else: | |
104 | result[result_idx] = right[right_idx] | |
105 | right_idx += 1 | |
106 | result_idx += 1 | |
107 | ||
108 | while left_idx < len(left): | |
109 | result[result_idx] = left[left_idx] | |
110 | left_idx += 1 | |
111 | result_idx += 1 | |
112 | ||
113 | while right_idx < len(right): | |
114 | result[result_idx] = right[right_idx] | |
115 | right_idx += 1 | |
116 | result_idx += 1 | |
117 | ||
118 | return result | |
119 | ||
120 | ||
121 | def merge_sort(nums): | |
122 | if len(nums) == 1: | |
123 | return nums | |
124 | ||
125 | mid_idx = len(nums) // 2 | |
126 | left = nums[:mid_idx] | |
127 | right = nums[mid_idx:] | |
128 | ||
129 | return merge_arrays(merge_sort(left), merge_sort(right)) | |
130 | ||
131 | ||
132 | nums = [int(x) for x in input().split()] | |
133 | result = merge_sort(nums) | |
134 | print(*result, sep=" ") |