[python] 선택정렬(Selection Sort) & 삽입정렬(Insertion Sort)

정렬(Sort)이란

정렬(Sorting)알고리즘에 대해 배워보자

정렬(Sorting)이란 리스트의 원소들을 특정 순서로 정리하는 것으로 크게 아래의 세 가지로 나누기가 가능하다.

1. 오름차순 정렬(갈수록 커짐)
2. 내림차순 정렬
3. 알파벳순 정렬

 

---

파이썬에는 sorted 내장함수와 리스트에 있는 sort() method도 있다.

파이썬에도 정렬을하는 내장함수와 메서드가 있다.

1. 내장함수 sorted
2. list의 method인 sort()

# 사용법
data = [12, 6, 4, 17, 11, 15, 1, 30]
sorted(data)
data.sort()

# [1, 4, 6, 11, 12, 15, 17, 30]

#숫자 뿐만 아니라 영어도 정렬 된다.

Q. 그냥 sorted나 sort()를 쓰면 되는데 왜 정렬에 대해서 배워야 하나?

정렬은 알고리즘의 기초!
즉, 정렬을 배우면서 문제 해결의 기초를 다질 수 있습니다.

---

1. 선택 정렬(Selection Sort)

• 직관적이 정렬
• 가장 먼저 생각이 날 수 있는 자연스러운 정렬 알고리즘

가장 작은 값을 찾아서 0번 인덱스에 놓고,
두번째로 작은 값을 찾아서 1번 인덱스에 놓고,
세번째로 작은 값을 찾아서 2번 인덱스에 놓고
....

0인덱스 부터 하나씩 보면서 제일 작은 값을 찾고 0번 인덱스와 교체.
그 후 1인덱스 부터 하나씩 보면서 작은 값 찾고 1번 인덱스와 교체
마지막 앞에까지만 정렬 하면 정렬 끝남

선택정렬 구현

def selectionSort(data):
    for i in range(0, len(a)-1):
        minV = i
        for j in range(i+1, len(a)):
            if a[min] > a[j]:
                minV = j
        a[i], a[min] = a[min], a[i]

• data는 정렬하고자 하는 list이다.
• i를 기준으로 j로 i 보다 작은 값이 있는가 찾는거다.
• if a[min] > a[j]:
  • 착은 값이 있는가 찾는 코드
• a[i], a[min] = a[min], a[i]
  • 위치를 바꿔준다. (파이썬만 이렇게 바꾸기 가능)

선택 정렬은 교환의 횟수가 버블 정렬이나 삽입 정렬 보다 작다

---

2. 삽입정렬(Insertion Sort)

선택 정렬	삽입 정렬
각 위치에 어떤 값이 들어갈지 찾는다.	각 값이 어떤 위치에 들어갈지 찾는다.

카드게임을 하고있다. 정렬되어 있는 카드를 들고 있는데 새로운 카드 한장이 더 들어오면 그 카드를 올바른 위치에 삽입하면 된다. 인덱스를 하나씩 늘려가면서 추가된 값을 맞는자리에 넣어준다.

 

0번 인덱스 와 1번 인덱스를 비교 후에 순서 맞게 교체. 2번 인덱스 값을 빼서 비교 후에 맞는 자리에 넣음.... 5번인덱스를 빼서 비교후에 큰 숫자들을 오른쪽으로 밀고 비는 자리에 들어감..

배열에서 비교 하는 값(3)을 빼고 그 값의 왼쪽 값(9)과 비교하여 왼쪽 값이 크면 오른쪽으로 한칸 움직임. 그리고 그 외쪽 값(7)과 비교하여 외쪽 값이 크면 7을 오른쪽으로 한칸움직임. 반복하다 작은 값이 나오면 빈자리에 들어가면된다.

 

정리하면 index 1부터 비교를 시작한다. 왼쪽 값과 비교해서 큰 값이 있으면 한칸씩 자리를 바꾼다. 아래의 예로 이해하자. 아래의 코드를 보면서 아래의 예시를 이해해보자.

4 2 3 5 1
2 4 3 5 1
2 3 4 5 1
2 3 4 5 1
2 3 4 1 5
2 3 1 4 5
2 1 3 4 5
1 2 3 4 5

삽입정렬 구현

def insertionSort(data):
    for i in range(1, len(data)):
        for j in range(i-1, -1, -1):
            if data[i]<data[j]:
                data[i], data[j] = data[j], data[i]
                i -= 1
            else:
                break

파이썬의 특징에 맞게 작성했다.

• for j in range(i-1, -1, -1):
  • i-1값부터 0까지 1씩 작은 값을 j에 대입
• data[i], data[j] = data[j], data[i]
  • i와 j위치의 인덱스 값을 변경
  • i -= 1은 기준값을 바꿔서 j 오른쪽으로 옮기기 위함이다.

---

3. 정렬 알고리즘 비교

https://www.toptal.com/developers/sorting-algorithms

들어가면 빨리되는 순서 알수있다.

• 거의 정렬된 리스트를 정렬할 때는 삽입 정렬(Insert Sort)이 가장 빠름

• 무작위 순서의 리스트를 정렬할 때는 힙 정렬(Heapsort)가 먼저 끝남

• 정반대로 정렬된 리스트는 삽입정렬이 매우오래 걸림

• 선택정렬(Selection Sort)와 합병 정렬(Merge Sort)는 상황에 영향을 받지 않고 일정한 시간이 소요.

무엇을 써야할까?? 각 알고리즘 마다 장단점을 파알 해야 올바른 알고리즘을 선택 가능하다.

알고리즘을 평가하는 방법이 바로 알고리즘 평가하는 법이다.

평가하는 방법은 다음 포스트에서 나중에 알아보자.