Sorting Method

https://proglib.
io/p/kak-podruzhit-python-i-bazy-dannyh-sql-
podrobnoe-rukovodstvo-2020-02-27
Sorting is a skill that every software engineer and developer needs

some knowledge of. Not only to pass coding interviews but as a
general understanding of programming itself. The different sorting
algorithms are a perfect showcase of how algorithm design can have
such a strong effect on program complexity, speed, and efficiency.
Let’s take a tour of the top 6 sorting algorithms and see how we can
implement them in Python!
Bubble Sort
Bubble sort is the one usually taught in introductory CS classes since
it clearly demonstrates how sort works while being simple and easy
to understand. Bubble sort steps through the list and compares
adjacent pairs of elements. The elements are swapped if they are in
the wrong order. The pass through the unsorted portion of the list is
repeated until the list is sorted. Because Bubble sort repeatedly
passes through the unsorted part of the list, it has a worst case
complexity of O(n²).
def bubble_sort(arr):
def swap(i, j):
arr[i], arr[j] = arr[j], arr[i]
n = len(arr)
swapped = True
x = -1
while swapped:
swapped = False
x = x + 1
for i in range(1, n-x):
if arr[i - 1] > arr[i]:
swap(i - 1, i)
swapped = True
return arr
Selection Sort
Selection sort is also quite simple but frequently outperforms bubble
sort. If you are choosing between the two, it’s best to just default
right to selection sort. With Selection sort, we divide our input list /
array into two parts: the sublist of items already sorted and the
sublist of items remaining to be sorted that make up the rest of the
list. We first find the smallest element in the unsorted sublist and
place it at the end of the sorted sublist. Thus, we are continuously
grabbing the smallest unsorted element and placing it in sorted
order in the sorted sublist. This process continues iteratively until
the list is fully sorted.
def selection_sort(arr):
for i in range(len(arr)):
minimum = i
for j in range(i + 1, len(arr)):

# Select the smallest value
if arr[j] < arr[minimum]:
minimum = j
# Place it at the front of the

# sorted end of the array
arr[minimum], arr[i] = arr[i], arr[minimum]
return arr
Insertion Sort
Insertion sort is both faster and well-arguably more simplistic than
both bubble sort and selection sort. Funny enough, it’s how many
people sort their cards when playing a card game! On each loop
iteration, insertion sort removes one element from the array. It then
finds the location where that element belongs within
another sorted array and inserts it there. It repeats this process until
no input elements remain.
def insertion_sort(arr):
for i in range(len(arr)):
cursor = arr[i]
pos = i
while pos > 0 and arr[pos - 1] > cursor:

# Swap the number down the list
arr[pos] = arr[pos - 1]
pos = pos - 1
# Break and do the final swap
arr[pos] = cursor
return arr
Merge Sort
Merge sort is a perfectly elegant example of a Divide and Conquer
algorithm. It simple uses the 2 main steps of such an algorithm:
(1) Continuously divide the unsorted list until you have N sublists,

where each sublist has 1 element that is “unsorted” and N is the
number of elements in the original array.
(2) Repeatedly merge i.e conquer the sublists together 2 at a time to

produce new sorted sublists until all elements have been fully
merged into a single sorted array.
def merge_sort(arr):
# The last array split
if len(arr) <= 1:
return arr
mid = len(arr) // 2
# Perform merge_sort recursively on both halves
left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])
# Merge each side together

return merge(left, right, arr.copy())
def merge(left, right, merged):

left_cursor, right_cursor = 0, 0
while left_cursor < len(left) and right_cursor < len(right):
# Sort each one and place into the result

if left[left_cursor] <= right[right_cursor]:
merged[left_cursor+right_cursor]=left[left_cursor]
left_cursor += 1
else:
merged[left_cursor + right_cursor] = right[right_cursor]
right_cursor += 1
for left_cursor in range(left_cursor, len(left)):

merged[left_cursor + right_cursor] = left[left_cursor]
for right_cursor in range(right_cursor, len(right)):

merged[left_cursor + right_cursor] = right[right_cursor]
return merged
Quick Sort
Quick sort is also a divide and conquer algorithm like merge sort.
Although it’s a bit more complicated, in most standard
implementations it performs significantly faster than merge sort and
rarely reaches its worst case complexity of O(n²). It has 3 main
steps:
(1) We first select an element which we will call the pivot from the

array.
(2) Move all elements that are smaller than the pivot to the left of
the pivot; move all elements that are larger than the pivot to the
right of the pivot. This is called the partition operation.
(3) Recursively apply the above 2 steps separately to each of the sub-
arrays of elements with smaller and bigger values than the last pivot.
def partition(array, begin, end):

pivot_idx = begin
for i in xrange(begin+1, end+1):
if array[i] <= array[begin]:
pivot_idx += 1
array[i], array[pivot_idx] = array[pivot_idx], array[i]
array[pivot_idx], array[begin] = array[begin], array[pivot_idx]
return pivot_idx
def quick_sort_recursion(array, begin, end):

if begin >= end:
return
pivot_idx = partition(array, begin, end)
quick_sort_recursion(array, begin, pivot_idx-1)
quick_sort_recursion(array, pivot_idx+1, end)
def quick_sort(array, begin=0, end=None):

if end is None:
end = len(array) - 1
return quick_sort_recursion(array, begin, end)

Завжди керуюся принципом, що imagination and vision are the most powerful assets. The ability to see
new opportunities where no one else does is a defining trait among fearless innovators. У роботі та
відповідно - у житті, я завжди «апелюю» до креативного простору, де можна застосовувати
аналітичні здібності для імплементації нових ідей та надбань. Свій напрямок програмування я
розпочала із сертифікаційного тримісячного курсу по Пайтону, який успішно завершивши,
скоординував мою траєкторію руху саме у цю сферу діяльності. У подальшому, я також додатково
вдосконалювала свої математичні знання проходивши заняття із ментором, онлайн курси та
самостійно освоювала ази вищої математики. Насправді, спектр моїх інтересів досить багатогранний,
тобто, я досить «гнучка» до різного виду діяльності, що відповідно лише акумулює мою
зацікавленість та мотивацію . Наразі, я цілком поглибила свою самореалізацію у русло науки про
дані, а отже – максимально наблизила себе до моделей прогнозування та ml-related технологій.
Стосовно набутих знань то у моєму піврічному досвіді поки не було golden opportunity для
повноцінної або ж прямопобічної участі у розробці проєкту, а отже, набуття досвіду відбувалося
шляхом – self-taught. Останнє над чим мені довелося працювати, це був міні-проєкт по аналізу даних
стосовно результатів проведення нафтогазових ліцензійних раундів включаючи угоди про розподіл
продукції станом на 2020 рік. Характер виконання завдань частково охоплював технології та
інструменти data science а саме,(коефіцієнт використання зазначений у відсотках): Python 3.8 (100%);
OOP (70%); Matplotlib (90%); Numpy/SciPy (40%); Pandas (60%) Bokeh(20%); Anaconda/Jupyter Notebook
(100%).

Sorting Method

Uploaded by

Copyright:

Available Formats

Sorting Method

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Sorting Method

Uploaded by

Copyright:

Available Formats

https://proglib.

Sorting is a skill that every software engineer and developer needs

for j in range(i + 1, len(arr)):

# Place it at the front of the

while pos > 0 and arr[pos - 1] > cursor:

(1) Continuously divide the unsorted list until you have N sublists,

(2) Repeatedly merge i.e conquer the sublists together 2 at a time to

# Merge each side together

def merge(left, right, merged):

# Sort each one and place into the result

for left_cursor in range(left_cursor, len(left)):

for right_cursor in range(right_cursor, len(right)):

(1) We first select an element which we will call the pivot from the

def partition(array, begin, end):

def quick_sort_recursion(array, begin, end):

def quick_sort(array, begin=0, end=None):

return quick_sort_recursion(array, begin, end)

You might also like