정렬 알고리즘

이진 탐색을 사용하기 위해선, 정렬된 리스트를 사용해야 한다고 했다. 

그러면 그냥 sort 메소드나 sorted 함수를 사용하면 될탠데... 

이런 기능이 어떻게 작동하는지 알아보자!

 

선택 정렬

선택 정렬은 기준 값을 하나 선택해서 모든 다른 리스트의 값과 비교해가며 더 작은 값들을 찾아서 정렬해가는 알고리즘을 사용한다.

-> 각 위치에 어떤 값이 들어갈지 찾는 것.

 

def selectSort(list_):

    for i in range(len(list_)):
        minIndex = i
        for j in range(i+1,len(list_)):
            if list_[i] < list_[j]:
                continue
            elif list_[i] > list_[j]:
                minIndex = j
        temp = list_[i]        
        list_[i] = list_[minIndex]
        list_[minIndex] = temp
    return list_

리스트의 i 번째 값을 가지고 살펴보기 시작하는데, i+1~끝 까지 값들과 i 값을 비교해가면서 i값이 더 작으면, 아무런 행동을 취하지 않는다.

 

그러나 i의 값이 더 크면, i보다 더 작은 값이 존재하는 것이므로 리스트의 i 번째 값은 뒤로 보내져야 하므로 minIndex를 해당 최소값 인덱스로 바꾸어준다.

 

그렇게 내부 for문이 끝난 후, 값을 치환해주는 과정을 모든 리스트에서 시행한다.

 

그러면 정렬된 리스트가 하나 나오게 된다.

 

1. 기준 값을 하나 선택
2. 기준 값보다 다음에 있는 모든 값들을 살펴보면서 최소값의 인덱스를 갱신
3. 모두 살펴본 뒤 기준값과 최소값 인덱스의 값을 교환
4. 1~3을 모든 값들에 대해서 시행

 

시간복잡도는?

 

처음부터 끝까지 하나씩 모두 비교해가며 돌아가기 때문에

O(n^2)

 

 

삽입 정렬

각 값이 어떤 위치에 들어갈지 찾는 것으로 선택 정렬의 역이라고  할 수 있겠다.

 

예를 들어서 k 인덱스에 있는 값이 들어갈 위치를 찾아야 한다고 해보자. 기본적으로 자신의 값보다 더 큰 값이 있으면 그 값과 자리를 바꾸어야 하는데 진행방향은 자신보다 인덱스가 작은 방향이다.

 

따라서 우리는 k-1~0번 인덱스를 조사하며 k인덱스 값의 위치를 지정해주어야 한다.

이를 중첩 for문을 이용해서 나타낸다면

def insertSort(list_):
    for i in range(1,len(list_)):
        for idx in range(0,i):
            if list_[idx] > list_[i]:
                list_[idx], list_[i] = list_[i], list_[idx]
    
    return list_

1. i index는 위치를 찾고자 하는 값의 인덱스이다.
2. i index 보다 작은 값을 참조하기 위해 range(0,i)를 사용했다
3. i index값보다 큰 값을 만나면 그 값을 교환해준다.

 

시간복잡도는?

 

최선의 경우는 정렬된 리스트를 삽입 정렬하는 경우로 O(n)

최악의 경우는 내림차순으로 정렬된 리스트를 정렬하는 경우로 O(n^2) 

---

이외에도 merge sort, quick sort등이 있지만 이는 다른 구현 방식을 사용하기 때문에 다른 글에서 다루어보도록 하자!