알고리즘 - 정렬

정렬(Sorting)

• 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 것

• 정렬 알고리즘은 선택 정렬, 삽입 정렬 등등의 알고리즘이 있다.

• 파이썬에는 정렬을 위한 sorted() 내장함수와, sort() 리스트 메소드가 존재한다.

---

1. 선택 정렬(Selection Sort)

각 위치에 어떤 값이 들어갈지 찾는 방식
선택 정렬은 값을 첫번째 인덱스에 들어갈 값을 찾기위해 하나하나 비교해보면서 가장 작은 값을 찾고, 다음 인덱스에 들어갈 값을 또 하나하나 비교해보면서 찾고, 이러한 방식을 끝까지 반복해서 정렬을 하는 방식이다.

def selection_sort(list):
    for i in range(len(list)):
        min = list[i]   # 최소값을 구하기 위한 초기값 설정
        
        for j in range(i, len(list)):   # 반복문을 돌면서 값을 하나하나 비교해준다. 그러고 앞의 인덱스에 최소값이 들어갔으면 다음 인덱스부터 확인한다.
            if list[j] < min:           # 만약 리스트 요소가 최소값보다 작으면 값을 변경해준다.
                min = list[j]           # 최소값보다 작기 때문에 요소를 최소값으로 변경
                list[j] = list[i]       # list[j]에 list[i]값을 넣고
                list[i] = min           # list[i]에 최소값을 넣어 둘의 값을 바꾼다. 그러고 반복
    
    return list
            
s_list = [4, 2, 7, 1, 9, 3]
print(selection_sort(s_list))
s_list2 = [41, 12, 37, 1, 9, 13]
print(selection_sort(s_list2))

->
[1, 2, 3, 4, 7, 9]
[1, 9, 12, 13, 37, 41]

2. 삽입 정렬(Insertion Sort)

각 값이 어떤 위치에 들어갈지 찾는 방식
인덱스를 하나씩 늘려가면서 그 인덱스에 해당되는 값이 어느 위치에 들어갈지 전 인덱스 값과 비교해보면서 정렬하는 방식

def insertion_sort(list):
    for i in range(1, len(list)):     # 0번 인덱스는 비교할 값이 업기 때문에 넘어가고 1번 인덱스 부터 시작한다.
        for j in range(i, 0, -1):     # 특정 인덱스의 값을 가지고 비교 해야 하기 때문에 뒤에서 부터 앞으로 가면서 비교한다.
            if list[j] < list[j-1]:   # 특정 인덱스의 값이 전 인덱스의 값과 비교해서 작은지 확인
                list[j] = min  
                list[j] = list[j-1]
                list[j-1] = min       # 특정 인덱스의 값이 작다면 전 인덱스의 값과 바꿔주고 0번 인덱스의 값까지 반복
                
            else:
                break
                
    return list

s_list = [4, 2, 7, 1, 9, 3]
print(selection_sort(s_list))

s_list2 = [41, 12, 37, 1, 9, 13]
print(selection_sort(s_list2))

** 출처

• 코드잇 - 알고리즘의 정석