[Pythonアルゴリズム]ソート
ツールバーの
:データを特定の基準で順番にリストする
Pythonのソートライブラリ
sorted() VS .sort()
ソート()関数
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
result = sorted(array)
print(result)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(array)
# [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
.sort()リストオブジェクトの組み込み関数array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
array.sort()
print(array)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
ソート・ライブラリの時間的複雑さ
最悪の場合でも,
バブルソート(Bubble Sort)
Idea
注意:https://visualgo.net/en/sorting
ソース:https://en.wikipedia.org/wiki/Bubble_sort
How To
Code
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(array)-1):
for j in range(len(array)-i-1):
if array[j] > array[j+1]: # 두개의 인접 데이터 비교
array[j], array[j+1] = array[j+1], array[j] # swap
print(array)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Analysis
選択ソート(Selection Sort)
Idea
注意:https://visualgo.net/en/sorting
ソース:https://en.wikipedia.org/wiki/Selection_sort
How To
Code
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(array)):
min_idx = i # 가장 작은 원소의 인덱스
for j in range(i+1, len(array)):
if array[min_idx] > array[j]:
min_idx = j
array[i], array[min_idx] = array[min_idx], array[i] # Swap
print(array)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Analysis
1.N-1は最小の数字を見つけて一番前に送る必要があります
2.小数を検索するたびに比較演算が必要
ソートの挿入(Insertion Sort)
Idea
注意:https://visualgo.net/en/sorting
ソース:https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif
How To
Code
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)):
for j in range(i, 0, -1): # i부터 1까지 역으로 확인
if array[j] < array[j-1]: # 자기보다 크다면 한 칸씩 왼쪽으로 이동
array[j], array[j-1] = array[j-1], array[j]
else: # 자기보다 작은 수를 만나면 멈춤
break
print(array)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Analysis
-完全整列時の時間的複雑度=O(N)O(N)O(N)O(N)
Reference
この問題について([Pythonアルゴリズム]ソート), 我々は、より多くの情報をここで見つけました https://velog.io/@ruwan9/Python-알고리즘-Selection-Sort선택-정렬テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol