Сортировка выбором максимума python

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Алгоритмы сортировки и их реализация на Python

ViktorSalimonov/sorting-algorithms

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Алгоритмы сортировки на Python

Сортировка пузырьком (Bubble Sort)

Сортировка пузырьком проходит по массиву несколько раз. На каждом этапе алгоритм сравнивает два соседних элемента и, если левый элемент больше правого — меняет их местами. Такой проход гарантирует что самое больше число будет в конце массива. Этот процесс попарного сравнения повторяется до тех пор, пока каждый элемент не будет на своем месте.

def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr

Сортировка выбором (Selection Sort)

Основная идея — рассматривать последовательность как две части: первая включает отсортированные элементы, вторая — неотсортированные. Алгоритм находит наименьшее число из неотсортированной части и помещает его в конец отсортированной.

def selection_sort(arr): n = len(arr) for i in range(n-1): min_index = i for j in range(i+1, n): if arr[j]  arr[min_index]: min_index = j if min_index != i: arr[i], arr[min_index] = arr[min_index], arr[i] return arr

Сортировка вставками (Insertion Sort)

Этот алгоритм совмещает идеи первых двух алгоритмов. Как и в сортировке выбором представляем последовательность как две части: первая включает отсортированные элменты, вторая — неотсортированные. Алгоритм сортировки вставками последовательно помещает каждый элемент из неотсортированной части на правильную позицию отсортированной части.

def insertion_sort(arr): n = len(arr) for i in range(1, n): current_value = arr[i] j = i - 1 while j >= 0: if current_value  arr[j]: arr[j+1] = arr[j] arr[j] = current_value j = j - 1 else: break return arr

Быстрая сортировка (Quick Sort)

Рекурсивный алгоритм, который работает по следующему принципу:

1. Выбрать опорный элемент из массива. Это можно сделать разными способами, в данной реализации этой будет случайный элемент.
2. Сравнить все элементы с опорным и распределить их в подмассивы. Первый подмассив будет состоять из элементов, которые меньше опорного; второй — больше опорного или равные.
3. Рекурсивно выполнить шаги 1 и 2, пока в подмассиве есть хотя бы 2 элемента.

import random def quick_sort(arr): n = len(arr) if n  1: return arr else: pivot = random.choice(arr) less = [x for x in arr if x  pivot] greater_or_equal = [x for x in arr if x >= pivot] return quick_sort(less) + quick_sort(greater_or_equal)

• В худшем случае O(n²)
• В среднем случае O(n * log n)
• В лучшем случае O(n * log n)

Сортировка слиянием (Merge Sort)

Рекурсивный алгоритм, который работает по следующему принципу:

1. Разделить массив на две равные части
2. Отсортировать каждую половину
3. Из двух отсортированных массивов получить один (операция слияния)

def merge_sort(arr): n = len(arr) if n  1: return arr else: middle = int(len(arr) / 2) left = merge_sort(arr[:middle]) right = merge_sort(arr[middle:]) return merge(left, right) def merge(left, right): result = [] while len(left) > 0 and len(right) > 0: if left[0]  right[0]: result.append(left[0]) left = left[1:] else: result.append(right[0]) right = right[1:] if len(left) > 0: result += left if len(right) > 0: result += right return result

• В худшем случае O(n * log n)
• В среднем случае O(n * log n)
• В лучшем случае O(n * log n)

Источник

Selection Sort in Python

Today we will learn a simple and easy to visualize sorting algorithm called the Selection Sort in Python. Let’s get started.

The Selection Sort Algorithm

Similar to Insertion Sort, the insertion sort algorithm divides the list into two parts. The first part at the beginning of the list is the sorted part and the second part at the end of the list is unsorted.

Initially, the entire list is unsorted but with every iteration, the smallest item in the list is searched (for ascending list) and added to the sorted section.

How this happens is that one by one, we find the smallest item in the unsorted section and swap it with the item at its correct position.

So in the first iteration, the smallest item is swapped with the item at the first position. In the second iteration, the second smallest item is swapped with the item at the second position. And so on…

Implementing Selection Sort in Python

Below is a simple implementation of selection sort in Python.

def selection_sort(lst): n = len(lst) for i in range(n - 1): min = i for j in range(i + 1, n): if(lst[j] < lst[min]): min = j lst[i], lst[min] = lst[min], lst[i]

Notice that the function takes in a list and performs the sorting in-place, it is fairly simple to alter the algorithm to return a sorted list instead.

Explaining the Steps of the Selection Sort Algorithm

This algorithm sorts the list in increasing order, let us see how it works.

• The variable n is the number of items in the list.
• Now, i goes from 0 to n - 2 , which means that i points from the first item to the second-last item. The role of i is that it will always point to where the next smallest item will go, so we will find the smallest item from i to the end of the list, and it will be placed at i .
• We are considering the item at i to be the smallest one for now, because if we fail to find a smaller element after i , then i holds the correct item.
• Inside, j goes from i + 1 to n - 1 , which means that j will point to all the items after i , and it will be responsible to find the smallest item in that range.
• Now we compare the item at j to the smallest item we have found yet, and if the item at j is smaller, then it becomes the smallest item we have found yet.
• After the inner loop, we have found the smallest item from i to n - 1 , and it is swapped with the item at i so that it goes to its correct position.
• The outer loop will continue to select and place the next smallest items one after the other until the entire list is sorted.

Now we will try to dry-run this algorithm on an example and see how it affects the sequence.

Let’s consider the sequence as 12, 16, 11, 10, 14, 13.
Size of the given list (n): 6

12, 16, 11, 10 , 14, 13
10 , 16, 11 , 12, 14, 13
10 , 11 , 16, 12 , 14, 13
10 , 11 , 12 , 16, 14, 13
10 , 11 , 12 , 13 , 14 , 16
10 , 11 , 12 , 13 , 14 , 16

• The numbers in green are the ones that have been sorted.
• The numbers in blue are the smallest ones from the ones that are not sorted.
• The uncolored ones are to be sorted.

It can be seen that the algorithm finds the smallest items and then swaps them with the item at their correct place.

The Output

Running the same list on the algorithm will produce the following result:

Conclusion

In this tutorial, we saw how Selection Sort works, we implemented the algorithm in Python and verified the dry-run of an example using the actual output of the code.

Selection Sort, similar to Bubble and Insertion Sort, has a complexity of O(n 2 ). This means that if the input size is doubled, the time it takes to execute the algorithm increases by four times, and so, it is an inefficient sorting algorithm.

It is generally less efficient than Insertion Sort but it is much simpler to understand and implement. I hope you enjoyed learning about Selection Sort and see you in the next tutorial.

Источник