hong_mok

버블 정렬(Bubble Sort) - 시간 복잡도 : O(n^2) - 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식이다. 알고리즘 - 첫 번째 인덱스 요소부터 인접한 원소랑 비교하여 자료를 바꾸면서 마지막 인덱스 요소 까지 반복한다. - 한 단계가 끝날 시 가장 큰 원소가 마지막에 정렬된다. - 정렬된 부분을 제외하고 나머지 부분에 대하여 정렬을 반복한다. 정렬과정을 그림으로 나타내면 다음과 같다. 코드 def bubble_sort(arr): # 버블 정렬(오름차순) n = len(arr) # 배열의 길이 저장 # 한 스텝마다 정렬된 자료가 뒤부터 쌓이므로 # 정렬범위 n-1부터 0까지 1씩 줄여주기 for i in range(n-1, 0, -1): for j in range(i): # 인접..

합병 정렬(Merge Sort) - 시간 복잡도 : O(n log n) - 분할 정복 알고리즘 이다. 알고리즘 - 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 - 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. - 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. - 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병(merge) 한다. - 복사(copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다. 과정 합병 정렬 과정을 그림으로 나타내면 다음과 같다. - 상단의 붉은색 부분은 정렬되지 않은 리스트들을 나누는 분할(devide) 과정이다. 길이가 1이..