ソートの詳細
12671 ワード
泡の位置合わせ
-->最初の値から始め、前後のデータを比較し、大きなデータを後ろに送信します.
-->完全比較で開始
ex)4個のデータ並べ替え
第1サイクル:0対1->1比2->2比3=>データ数-1
-->最初のサイクルが完了すると、最大データは最後になります.
2サイクル目:0対1->1対2=>データ数-2
3サイクル目:0対1=>3データサイクル
バブルソートの実施
## 클래스와 함수 선언 부분 ##
def bubbleSort(ary):
n = len9(ary)
for end in range(n-1, 0, -1): # cycle 크기가 전체에서 1개씩 점점 감소
for cur in range(0, end):
if (ary[cur] > ary[cur+1]):
ary[cur], ary[cur+1] = ary[cur+1], ary[cur]
return ary性能:挿入・選択ソートと同様に演算数はO(n^2)である.
Butは,既存の配列がある程度並べ替えられていると演算量が急激に減少する.
ソートされている場合は、バブルソートを実施してサイクルを終了します.
## 클래스와 함수 선언 부분 ##
def bubbleSort(ary):
n = len(ary)
for end in range(n-1, 0, -1):
changeYN = False # 자리 바꿈이 발생했는지 확인하는 변수
for cur in range(0, end):
if (ary[cur] > ary[cur+1]):
ary[cur], ary[cur+1] = ary[cur+1], ary[cur]
changeYN = True # 발생하면 True
if not changeYN:
break
return aryクイックソート
-->条件を選択し、条件より小さいグループと条件より大きいグループを分けて、各グループに並べ替えます.
-->グループを並べ替えるときに再帰コールを使用し、完了したらマージします.
-->まず基準(pivot)を設定することが重要->通常は中間位置
クイックソートの実装
## 클래스와 함수 선언 부분 ##
def quickSort(ary):
n = len(ary)
if n <= 1:
return ary # 정렬에 데이터가 1개 이하이면 정렬이 끝난 그룹
pivot = ary[n//2] # 기준 (pivot) 지정
leftAry, rightAry = [], []
for num in ary:
if num < pivot: # 기준보다 작으면 왼쪽으로 삽입
leftAry.append(num)
elif num > pivot: # 기준보다 크면 오른쪽으로 삽입
rightAry.append(num)
return quickSort(leftAry) + [pivot] + quickSort(rightAry)
# 재귀호출로 나뉜 그룹 정렬左Ary,中間Ary,右Aryの3つの空の配列.
迅速なソートの一般的な実装
-->既存の配列を使用したクイックソート
low:先頭(start)
high:エンディング(end)
## 클래스와 함수 선언 부분 ##
def qSort(arr, start, end):
if end <= start:
return
low = start
high = end
pivot = arr[(low+high) // 2]
while low <= high:
while arr[low] < pivot:
low += 1 # 첫 번째 데이터가 기준보다 작으면 +1
while arr[high] > pivot:
high -= 1 # 맨 끝 데이터가 기준보다 크면 -1
if low <= high: # 기준보다 큰 값이 왼쪽, 작은 값이 오른쪽에 있는 경우
arr[low], arr[high] = arr[high], arr[low]
low, high = low + 1, high + 1
mid = low
qSort(arr, start, mid-1)
qSort(arr, mid, end)
def quickSort(ary):
qSort(ary, 0, len(ary)-1)性能:算術-->O(n^2)
But、平均演算子はO(nlogn)
Reference
この問題について(ソートの詳細), 我々は、より多くの情報をここで見つけました https://velog.io/@yoojs1205/정렬-고급テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol