1つの問題、複数のアルゴリズム-2(ソート)
44579 ワード
この文章はせつぞくせんのアルゴリズムの定義課程の受講と総括である.
不正確な内容や漏れがある場合がありますので、講義をお勧めします.
ソート(Sorting):リスト内の要素を特定の順序で並べ替えます.
のソートを学ぶことで、問題解決の基礎を築くことができます. は、すべての開発者が知っておくべき基本アルゴリズムです. 1.整列選択(Selection Sort)
不正確な内容や漏れがある場合がありますので、講義をお勧めします.
ソート(Sorting):リスト内の要素を特定の順序で並べ替えます.
sorted, .sort()を書けばいいのに、なぜソートを学ぶのですか?
1.整列選択(Selection Sort)
まず考えられるのは自然なソートアルゴリズムで,各位置の値を探すことである.가장 작은 값을 찾아서 0번 인덱스에 놓고,
두번째로 작은 값을 찾아서 1번 인덱스에 놓고,
세번째로 작은 값을 찾아서 2번 인덱스에 놓고
.
.
.
つまり、0番のインデックスの値を検索し、1番のインデックスの値を検索して、このように繰り返します.
ソート・プロシージャの選択
list1 = [4, 2, 7, 1, 9, 3]
0番のインデックスに入る値を探します。
[4, 2, 7, 1, 9, 3]
ㄴ 최솟값 인덱스 (0)
ㄴ 현재 인덱스 (0)
[4, 2, 7, 1, 9, 3]
ㄴ 최솟값 인덱스 (1)
ㄴ 현재 인덱스 (1)
[4, 2, 7, 1, 9, 3]
ㄴ 최솟값 인덱스 (1)
ㄴ 현재 인덱스 (2)
[4, 2, 7, 1, 9, 3]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (3)
[4, 2, 7, 1, 9, 3]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (4)
[4, 2, 7, 1, 9, 3]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (4)
巡回結果0番インデックスの値は3番インデックスの値です.したがって、3番インデックスと1番インデックスが変更されます.list1 = [1, 2, 7, 4, 9, 3]
インデックス番号1に入る値を探します。
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (1)
ㄴ 현재 인덱스 (1)
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (1)
ㄴ 현재 인덱스 (2)
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (1)
ㄴ 현재 인덱스 (3)
...
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (1)
ㄴ 현재 인덱스 (5)
巡回結果は1番インデックス値より小さい値がないため、変更は行われません.list1 = [1, 2, 7, 4, 9, 3]
インデックス2に入る値を探します。
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (2)
ㄴ 현재 인덱스 (2)
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (3)
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (4)
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (5)
ㄴ 현재 인덱스 (5)
巡回結果2番インデックスの値は5番インデックスの値です.したがって、2番インデックスと5番インデックスが変更されます.list1 = [1, 2, 3, 4, 9, 7]
3番のインデックスに入る値を探します。
[1, 2, 3, 4, 9, 7]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (3)
[1, 2, 3, 4, 9, 7]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (4)
[1, 2, 3, 4, 9, 7]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (5)
巡回結果はインデックス値3より小さい値がないため、変更は行われません.list1 = [1, 2, 3, 4, 9, 7]
4番のインデックスに入る値を探します。
[1, 2, 3, 4, 9, 7]
ㄴ 최솟값 인덱스 (4)
ㄴ 현재 인덱스 (4)
[1, 2, 3, 4, 9, 7]
ㄴ 최솟값 인덱스 (5)
ㄴ 현재 인덱스 (5)
巡回結果4番インデックスの値は5番インデックスの値です.したがって、4番インデックスと5番インデックスを変更します.list1 = [1, 2, 3, 4, 7, 9]
5番インデックスは?
合計6つの値があるため、5番のインデックスに最大の値が入力されました.ソートを終了すればいいです.
2.ソートの挿入
各値がどの位置に入るかを検索(挿入)します.
位置合わせアクションの挿入
list = [4, 2, 7, 1, 9, 3]
インデックス1番の値を探します。
# 1
[4 , (2), 7, 1, 9, 3]
# 2
[4 , (2), 7, 1, 9, 3]
ㄴ 비교 인덱스(0)
[( ) , 4(2), 7, 1, 9, 3] # 4가 2보다 크므로 4를 오른쪽으로 옮긴다.
# 3
[2, 4, 7, 1, 9, 3] # 2를 빈 자리에 채운다.
list = [2, 4, 7, 1, 9, 3]
インデックス2番の値を探します。
# 1
[2, 4, (7), 1, 9, 3]
# 2
[2, 4, (7), 1, 9, 3]
ㄴ 비교 인덱스(1)
[2, 4, (7), 1, 9, 3] # 4는 7보다 작기 때문에 그냥 넘어간다.
インデックス1以下の値はソートされているため、比較は行われません.list = [2, 4, 7, 1, 9, 3]
3番目のインデックスの値を探します。
# 1
[2, 4, 7, (1), 9, 3]
# 2
[2, 4, 7, (1), 9, 3]
ㄴ 비교 인덱스 (2)
[2, 4,( ), 7(1), 9, 3] # 7이 1보다 크므로 7을 오른쪽으로 옮긴다.
# 3
[2, 4, ( ), 7(1), 9, 3]
ㄴ 비교 인덱스 (1)
[2, ( ), 4, 7(1), 9, 3] # 4가 1보다 크므로 4를 오른쪽으로 옮긴다.
# 4
[2, ( ), 4, 7(1), 9, 3]
ㄴ 비교 인덱스 (0)
[( ), 2, 4, 7(1), 9, 3] # 2가 1보다 크므로 2를 오른쪽으로 옮긴다.
# 5
[(1), 2, 4, 7, 9, 3] # 비교 할 값이 없기 때문에 1을 빈자리에 채운다.
list = [1, 2, 4, 7, 9, 3]
4番のインデックスの値を探します。
# 1
[1, 2, 4, 7, (9), 3]
# 2
[1, 2, 4, 7, (9), 3]
ㄴ 비교 인덱스 (3)
[1, 2, 4, 7, (9), 3] # 7은 9보다 작기 때문에 그냥 넘어간다.
インデックス3以下の値はソートされ、比較は行われません.list = [1, 2, 4, 7, 9, 3]
5番目のインデックスの値を探します。
#1
[1, 2, 4, 7, 9, (3)]
#2
[1, 2, 4, 7, 9, (3)]
ㄴ 비교 인덱스(4)
[1, 2, 4, 7, ( ), 9(3)] # 9가 3보다 크므로 9를 오른쪽으로 옮긴다.
# 3
[1, 2, 4, 7, ( ), 9(3)]
ㄴ 비교 인덱스 (3)
[1, 2, 4, ( ), 7, 9(3)] # 7이 3보다 크므로 7을 오른쪽으로 옮긴다.
# 4
[1, 2, 4, ( ), 7, 9(3)]
ㄴ 비교 인덱스 (2)
[1, 2, ( ), 4, 7, 9(3)] # 4가 3보다 크므로 4를 오른쪽으로 옮긴다.
# 5
[1, 2, ( ), 4, 7, 9(3)]
ㄴ 비교 인덱스 (1)
[1, 2, (3), 4, 7, 9] # 2는 3보다 작으므로 빈 자리에 3을 채운다.
list = [1, 2, 3, 4, 7, 9]
並べ替えが完了しました.
3.比較ソートアルゴリズム
このサイトでは、ソートアルゴリズムのパフォーマンスを異なる環境で表示することができる.
ソート問題には絶対的な答えはなく、状況に応じて長所と短所を把握しなければならない.
4.実施
選択ソート、挿入ソートが実現しました.# 선택정렬 구현하기 (자리의 주인을 찾는다.)
def selection_sort(my_list):
for i in range(len(my_list)):
min_idx = i
for j in range(i + 1, len(my_list)):
if my_list[min_idx] > my_list[j]:
min_idx = j
my_list[i], my_list[min_idx] = my_list[min_idx], my_list[i]
# 삽입정렬 구현하기 (삽입할 자리를 찾는다.)
def insertion_sort(my_list):
for i in range(1, len(my_list)):
value = my_list[i]
insertion_idx = i
for j in range(i-1, -1, -1):
if my_list[j] < value:
break
my_list[j+1] = my_list[j]
insertion_idx = j
else:
my_list[insertion_idx] = value
if __name__ == '__main__':
testcase = [4, 2, 7, 1, 9, 3]
testcase2 = [4, 2, 7, 1, 9, 3]
print(testcase)
print(testcase2)
selection_sort(testcase)
insertion_sort(testcase2)
print(testcase)
print(testcase2)
# 콘솔 출력
[4, 2, 7, 1, 9, 3]
[4, 2, 7, 1, 9, 3]
[1, 2, 3, 4, 7, 9]
[1, 2, 4, 4, 7, 9]
Reference
この問題について(1つの問題、複数のアルゴリズム-2(ソート)), 我々は、より多くの情報をここで見つけました
https://velog.io/@joje/2.-하나의-문제-여러가지-알고리즘-2-정렬
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
가장 작은 값을 찾아서 0번 인덱스에 놓고,
두번째로 작은 값을 찾아서 1번 인덱스에 놓고,
세번째로 작은 값을 찾아서 2번 인덱스에 놓고
.
.
.
[4, 2, 7, 1, 9, 3]
ㄴ 최솟값 인덱스 (0)
ㄴ 현재 인덱스 (0)
[4, 2, 7, 1, 9, 3]
ㄴ 최솟값 인덱스 (1)
ㄴ 현재 인덱스 (1)
[4, 2, 7, 1, 9, 3]
ㄴ 최솟값 인덱스 (1)
ㄴ 현재 인덱스 (2)
[4, 2, 7, 1, 9, 3]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (3)
[4, 2, 7, 1, 9, 3]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (4)
[4, 2, 7, 1, 9, 3]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (4)
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (1)
ㄴ 현재 인덱스 (1)
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (1)
ㄴ 현재 인덱스 (2)
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (1)
ㄴ 현재 인덱스 (3)
...
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (1)
ㄴ 현재 인덱스 (5)
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (2)
ㄴ 현재 인덱스 (2)
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (3)
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (4)
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (5)
ㄴ 현재 인덱스 (5)
[1, 2, 3, 4, 9, 7]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (3)
[1, 2, 3, 4, 9, 7]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (4)
[1, 2, 3, 4, 9, 7]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (5)
[1, 2, 3, 4, 9, 7]
ㄴ 최솟값 인덱스 (4)
ㄴ 현재 인덱스 (4)
[1, 2, 3, 4, 9, 7]
ㄴ 최솟값 인덱스 (5)
ㄴ 현재 인덱스 (5)
各値がどの位置に入るかを検索(挿入)します.
位置合わせアクションの挿入
list = [4, 2, 7, 1, 9, 3]
インデックス1番の値を探します。
# 1
[4 , (2), 7, 1, 9, 3]
# 2
[4 , (2), 7, 1, 9, 3]
ㄴ 비교 인덱스(0)
[( ) , 4(2), 7, 1, 9, 3] # 4가 2보다 크므로 4를 오른쪽으로 옮긴다.
# 3
[2, 4, 7, 1, 9, 3] # 2를 빈 자리에 채운다.
list = [2, 4, 7, 1, 9, 3]
インデックス2番の値を探します。
# 1
[2, 4, (7), 1, 9, 3]
# 2
[2, 4, (7), 1, 9, 3]
ㄴ 비교 인덱스(1)
[2, 4, (7), 1, 9, 3] # 4는 7보다 작기 때문에 그냥 넘어간다.
インデックス1以下の値はソートされているため、比較は行われません.list = [2, 4, 7, 1, 9, 3]
3番目のインデックスの値を探します。
# 1
[2, 4, 7, (1), 9, 3]
# 2
[2, 4, 7, (1), 9, 3]
ㄴ 비교 인덱스 (2)
[2, 4,( ), 7(1), 9, 3] # 7이 1보다 크므로 7을 오른쪽으로 옮긴다.
# 3
[2, 4, ( ), 7(1), 9, 3]
ㄴ 비교 인덱스 (1)
[2, ( ), 4, 7(1), 9, 3] # 4가 1보다 크므로 4를 오른쪽으로 옮긴다.
# 4
[2, ( ), 4, 7(1), 9, 3]
ㄴ 비교 인덱스 (0)
[( ), 2, 4, 7(1), 9, 3] # 2가 1보다 크므로 2를 오른쪽으로 옮긴다.
# 5
[(1), 2, 4, 7, 9, 3] # 비교 할 값이 없기 때문에 1을 빈자리에 채운다.
list = [1, 2, 4, 7, 9, 3]
4番のインデックスの値を探します。
# 1
[1, 2, 4, 7, (9), 3]
# 2
[1, 2, 4, 7, (9), 3]
ㄴ 비교 인덱스 (3)
[1, 2, 4, 7, (9), 3] # 7은 9보다 작기 때문에 그냥 넘어간다.
インデックス3以下の値はソートされ、比較は行われません.list = [1, 2, 4, 7, 9, 3]
5番目のインデックスの値を探します。
#1
[1, 2, 4, 7, 9, (3)]
#2
[1, 2, 4, 7, 9, (3)]
ㄴ 비교 인덱스(4)
[1, 2, 4, 7, ( ), 9(3)] # 9가 3보다 크므로 9를 오른쪽으로 옮긴다.
# 3
[1, 2, 4, 7, ( ), 9(3)]
ㄴ 비교 인덱스 (3)
[1, 2, 4, ( ), 7, 9(3)] # 7이 3보다 크므로 7을 오른쪽으로 옮긴다.
# 4
[1, 2, 4, ( ), 7, 9(3)]
ㄴ 비교 인덱스 (2)
[1, 2, ( ), 4, 7, 9(3)] # 4가 3보다 크므로 4를 오른쪽으로 옮긴다.
# 5
[1, 2, ( ), 4, 7, 9(3)]
ㄴ 비교 인덱스 (1)
[1, 2, (3), 4, 7, 9] # 2는 3보다 작으므로 빈 자리에 3을 채운다.
list = [1, 2, 3, 4, 7, 9]
並べ替えが完了しました.3.比較ソートアルゴリズム
このサイトでは、ソートアルゴリズムのパフォーマンスを異なる環境で表示することができる.
ソート問題には絶対的な答えはなく、状況に応じて長所と短所を把握しなければならない.
4.実施
選択ソート、挿入ソートが実現しました.# 선택정렬 구현하기 (자리의 주인을 찾는다.)
def selection_sort(my_list):
for i in range(len(my_list)):
min_idx = i
for j in range(i + 1, len(my_list)):
if my_list[min_idx] > my_list[j]:
min_idx = j
my_list[i], my_list[min_idx] = my_list[min_idx], my_list[i]
# 삽입정렬 구현하기 (삽입할 자리를 찾는다.)
def insertion_sort(my_list):
for i in range(1, len(my_list)):
value = my_list[i]
insertion_idx = i
for j in range(i-1, -1, -1):
if my_list[j] < value:
break
my_list[j+1] = my_list[j]
insertion_idx = j
else:
my_list[insertion_idx] = value
if __name__ == '__main__':
testcase = [4, 2, 7, 1, 9, 3]
testcase2 = [4, 2, 7, 1, 9, 3]
print(testcase)
print(testcase2)
selection_sort(testcase)
insertion_sort(testcase2)
print(testcase)
print(testcase2)
# 콘솔 출력
[4, 2, 7, 1, 9, 3]
[4, 2, 7, 1, 9, 3]
[1, 2, 3, 4, 7, 9]
[1, 2, 4, 4, 7, 9]
Reference
この問題について(1つの問題、複数のアルゴリズム-2(ソート)), 我々は、より多くの情報をここで見つけました
https://velog.io/@joje/2.-하나의-문제-여러가지-알고리즘-2-정렬
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
選択ソート、挿入ソートが実現しました.
# 선택정렬 구현하기 (자리의 주인을 찾는다.)
def selection_sort(my_list):
for i in range(len(my_list)):
min_idx = i
for j in range(i + 1, len(my_list)):
if my_list[min_idx] > my_list[j]:
min_idx = j
my_list[i], my_list[min_idx] = my_list[min_idx], my_list[i]
# 삽입정렬 구현하기 (삽입할 자리를 찾는다.)
def insertion_sort(my_list):
for i in range(1, len(my_list)):
value = my_list[i]
insertion_idx = i
for j in range(i-1, -1, -1):
if my_list[j] < value:
break
my_list[j+1] = my_list[j]
insertion_idx = j
else:
my_list[insertion_idx] = value
if __name__ == '__main__':
testcase = [4, 2, 7, 1, 9, 3]
testcase2 = [4, 2, 7, 1, 9, 3]
print(testcase)
print(testcase2)
selection_sort(testcase)
insertion_sort(testcase2)
print(testcase)
print(testcase2)
# 콘솔 출력
[4, 2, 7, 1, 9, 3]
[4, 2, 7, 1, 9, 3]
[1, 2, 3, 4, 7, 9]
[1, 2, 4, 4, 7, 9]
Reference
この問題について(1つの問題、複数のアルゴリズム-2(ソート)), 我々は、より多くの情報をここで見つけました https://velog.io/@joje/2.-하나의-문제-여러가지-알고리즘-2-정렬テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol