[알고리즘] 정렬

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열 나열하는 것

 

선택 정렬❓

1. 주어진 리스트에서 가장 작은 값을 찾는다.

2. 찾은 값을 맨 앞 인덱스의 값과 교체

3. 맨 앞 값을 제외한 나머지 값들 중 최소값을 찾고 반복, 교체

시간복잡도: O(n^2)

 

 구현🔻

list = [2, 4, 7, 3, 6]

for i in range(0, len(list)):
    min_index = i
    for j in range(i + 1, len(list)):
        if list[min_index] > list[j]:
            min_index = j
    list[i], list[min_index] = list[min_index] , list[i]

print(list)

 

버블 정렬❓

1. 인접한 두 수를 비교 

2. 큰 수를 뒤로 보낸다.

시간 복잡도: O(n^2)

 

구현🔻

list = [3,2,5,7,1]
n = len(list)
for i in range(n -1):
    for j in range(n - 1 -i):
        if list[j] > list[j+1]:
            list[j], list[j+1] = list[j+1], list[j]
    
print(list)

 

삽입 정렬❓

1. 주어진 배열의 모든 요소를 앞에서 부터 차례로 비교

2. 자신의 위치를 찾아 삽입 

시간 복잡도: O(n^2)

 

구현🔻

list = [3, 2, 5, 7, 1]
n = len(list)
for i in range(1, n):
    for j in range(i, 0, -1):
        if list[j -1] > list[j]:
            list[j-1], list[j] = list[j], list[j-1]

print(list)

 

병합 정렬❓

1. 정렬되지 않은 리스트를 원소가 하나씩 남을 때 까지 분할

2. 각 분할된 리스트를 재귀적으로 합병정렬을 이용해 정렬

3. 정렬된 부분 리스트들을 하나로 합침

 

시간 복잡도: O(n log n)

 

구현🔻

list = [3, 2, 5, 7, 1]

def merge_sort(list):
    if len(list) < 2:
        return list
    mid = len(list) // 2
    low_list = merge_sort(list[:mid])
    high_list = merge_sort(list[mid:])

    merged_list = []
    l = h = 0
    while l < len(low_list) and h < len(high_list):
        if low_list[l] < high_list[h]:
            merged_list.append(low_list[l])
            l += 1
        else:
            merged_list.append(high_list[h])
            h += 1

    merged_list += low_list[l:]
    merged_list += high_list[h:]
    return merged_list

list = merge_sort(list)
print(list)

 

힙 정렬❓