スタート-バブルの位置合わせ、挿入位置合わせ

バブルソートアルゴリズム

# 거품 정렬
# 입력: 리스트 a
# 출력: 없음(입력으로 주어진 a가 정렬됨)
 
def bubble_sort(a):
    n = len(a)
    for i in range(n):          
        for j in range(0, n - i - 1):
            if a[j] > a[j + 1]: # 앞이 뒤보다 크면
                print(a)            # 정렬 과정 출력(참고용)
                a[j], a[j + 1] = a[j + 1], a[j] # 두 자료의 위치를 맞바꿈

 
d = [2, 4, 5, 1, 3]
bubble_sort(d)
print(d)				  # 실행결과: [1, 2, 3, 4, 5]

運転結果

[2, 4, 5, 1, 3]
[2, 4, 1, 5, 3]
[2, 4, 1, 3, 5]
[2, 1, 4, 3, 5]
[2, 1, 3, 4, 5]
[1, 2, 3, 4, 5]

[2 4 5 1 3]←2<4なのでそのまま置いておきましょう
[2 4 5 1 3]←4<5なのでそのまま置いておきましょう
[2 4 5 1 3]←5>1なので、5と1の位置を互いに交換する.
[2 4 1 5 3]←5>3なので、5と3の位置を互いに交換する.
[24 1 3 5]←改めて前から繰り返し、2<4なのでそのまま
[24 1 3 5]←4>1だから位置を入れ替える
[2 1 4 3 5]←4>3だから位置を入れ替える
[2 1 3 4 5]←4<5なのでそのまま置いておきましょう
[21 3 4 5]←改めて前から繰り返し、2>1なので位置を入れ替えます.
[12 3 4 5]←何も変わらないので並べ替え(最終結果)を終了する.

アルゴリズム解析

入力泡配列の計算複雑度はO(n二乗)であった.しかし、バブルソートの欠点は、データの交換位置の回数が選択ソートまたは挿入ソートよりも大きいため、実際の実行速度が遅いことである.

昇順ソート

# 거품 정렬
# 입력: 리스트 a
# 출력: 없음(입력으로 주어진 a가 정렬됨)
 
def bubble_sort(a):
    n = len(a)
    for i in range(n):          
        for j in range(0, n - i - 1):
            if a[j] < a[j + 1]: # 뒤가 앞보다 크면
                print(a)            # 정렬 과정 출력(참고용)
                a[j], a[j + 1] = a[j + 1], a[j] # 두 자료의 위치를 맞바꿈

 
d = [2, 4, 5, 1, 3]
bubble_sort(d)
print(d)				  # 실행결과: [5, 4, 3, 2, 1]

List[2,5,6,3,1]を泡順に並べ替える

[2, 5, 6, 3, 1]
[5, 2, 6, 3, 1]
[5, 6, 2, 3, 1]
[5, 6, 3, 2, 1]
[6, 5, 3, 2, 1]

整列挿入

先生は10人の学生が集まったグラウンドに現れた.
2|先生は10人の中で一番前の承圭を列に並ばせた.スンギュは外に出たが、まだ9人の学生が残っている.
3|今度の先生は俊浩に身長を押して並ばせた.ジュンホはソン・スンギュより背が低いことを確認し、スンギュの前に立った.
4|残り8人のうち、今回は民成が選ばれた.民成は俊浩より承奎より大きい.だからジュンホとスンギュの間に空間を作る(挿入)
5|同様に、キューに並んでいる学生間でキーを繰り返して残りの学生を挿入します.最後に残った生徒も選んで並んだら、全員がその場で並んでいます.

簡単に説明する挿入ソートアルゴリズム

# 쉽게 설명한 삽입 정렬
# 입력: 리스트 a
# 출력: 정렬된 새 리스트
 
# 리스트 r에서 v가 들어가야 할 위치를 돌려주는 함수
def find_ins_idx(r, v):
    # 이미 정렬된 리스트 r의 자료를 앞에서부터 차례로 확인하여
    for i in range(0, len(r)):
        # v 값보다 i번 위치에 있는 자료 값이 크면
        # v가 그 값 바로 앞에 놓여야 정렬 순서가 유지됨
        if v < r[i]:
            return i
    # 적절한 위치를 못 찾았을 때는
    # v가 r의 모든 자료보다 크다는 뜻이므로 맨 뒤에 삽입
    return len(r)
 
def ins_sort(a):
    result = []  # 새 리스트를 만들어 정렬된 값을 저장
    while a:     # 기존 리스트에 값이 남아 있는 동안 반복
        value = a.pop(0) # 기존 리스트에서 한 개를 꺼냄
        ins_idx = find_ins_idx(result, value) # 꺼낸 값이 들어갈 적당한 위치 찾기
        result.insert(ins_idx, value) # 찾은 위치에 값 삽입(이후 값은 한 칸씩 밀려남)
    return result
 
d = [2, 4, 5, 1, 3]
print(ins_sort(d))				  # 실행결과: [1, 2, 3, 4, 5]

1|リストaにデータが残っている場合→while a:
2|残りの資料から一番前の値を抽出します.→ value = a.pop(0)
3|この値が結果のどの位置にあるべきかを決定します.
→ ins_idx = find_ins_idx(result, value)
抽出した値をプロシージャ4|3で見つけた場所に挿入します.
→ result.insert(ins_idx, value)
5|1番のコースを返し、資料がないまで繰り返します.

[2,4,5,1,3]並べ替えプロセス

①開始
a = [2 4 5 1 3]
result = []
②aから2を引いて現在空の結果に入れる.
a = [4 5 1 3]
result = [2]
③aから4を引いて、結果の2の後ろに置く(2<4).
a = [5 1 3]
result = [2 4]
④aから5を減算し、結果の最後(4<5)に置く.
a = [1 3]
result = [2 4 5]
⑤aから1を引いて、結果の一番前に置く(1<2).
a = [3]
result = [1 2 4 5]
⑥aから最後の値3を減算し、結果の2と4の間に置く(2<3<4).
a=[]
result = [1 2 3 4 5]
|aは空です.終了してください.
結果=[12 3 4 5]→最終結果

挿入方法

一般的な挿入ソートアルゴリズム

# 삽입 정렬
# 입력: 리스트 a
# 출력: 없음(입력으로 주어진 a가 정렬됨)
 
def ins_sort(a):
    n = len(a)
    for i in range(1, n): # 1부터 n -1까지
        key = a[i] # i번 위치에 있는 값을 key에 저장
        # j를 i 바로 왼쪽 위치로 저장
        j = i - 1
        # 리스트의 j번 위치에 있는 값과 key를 비교해 key가 삽입될 적절한 위치를 찾음
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j] # 삽입할 공간이 생기도록 값을 오른쪽으로 한 칸 이동
            j -= 1
        a[j + 1] = key # 찾은 삽입 위치에 key를 저장
 
d = [2, 4, 5, 1, 3]
ins_sort(d)
print(d)				  # 실행결과: [1, 2, 3, 4, 5]

アルゴリズム解析

ソートアルゴリズムを挿入する計算の複雑さにはいくつかの考慮すべき点がある.最良の場合、少しユニークな結果が出るからです.ソートアルゴリズムを挿入する入力の下に,[1,2,3,4,5]のような完了したソートのリストを加えると,O(n)の計算複雑度ソートが完了する.しかし、このような状況は特殊な状況だ.
一般入力の場合,挿入ソートの計算複雑度は選択ソートのO(n二乗)に等しい.したがって、ソートを選択するのと同様に、ソートする入力サイズが大きい場合は、ソートに時間がかかります.

降順ソート

# 삽입 정렬
# 입력: 리스트 a
# 출력: 없음(입력으로 주어진 a가 정렬됨)
 
def ins_sort(a):
    n = len(a)
    for i in range(1, n): # 1부터 n -1까지
        key = a[i] # i번 위치에 있는 값을 key에 저장
        # j를 i 바로 왼쪽 위치로 저장
        j = i - 1
        # 리스트의 j번 위치에 있는 값과 key를 비교해 key가 삽입될 적절한 위치를 찾음
        while j >= 0 and a[j] < key:
            a[j + 1] = a[j] # 삽입할 공간이 생기도록 값을 오른쪽으로 한 칸 이동
            j -= 1
        a[j + 1] = key # 찾은 삽입 위치에 key를 저장
 
d = [2, 4, 5, 1, 3]
ins_sort(d)
print(d)				  # 실행결과: [5, 4, 3, 2, 1]