파이썬으로 알고리즘, 자료구조 공부하기 - 삽입 정렬, 선택 정렬(selection sort, insertion sort)

파이썬으로 알고리즘, 자료구조 공부하기!

이번에는 삽입 정렬, 선택 정렬이다

정렬 알고리즘에서 많이 나오는 것들이 버블 정렬, 삽입 정렬, 선택 정렬 등이 있는데

당분간 이 정렬에 대해서 공부하고 정리하려고 한다!

 

먼저 선택 정렬(selection sort)이다

 

 

source : https://www.programiz.com/dsa/selection-sort

선택 정렬은 위 그림을 보면 이해가 편하다

매 step으로 나뉘어 진행하는데 첫 번째에 스탭을 돌면 가장 작은 값이 맨 처음으로 온다.

그리고 첫 번째 값을 fixed 시켜놓고 2번째 값 부터 시작하고 또 다시 비교한다.

그렇기 때문에 비교는 N * (N-1)만큼 비교를 하게 된다. 하지만 교환 횟수는 N - 1 정도이다

파이썬으로 코드를 구현해보자

 

이렇게 간단한 하나의 함수로 만들 수 있다.

2개의 for문을 돈다. N * (N -1)이므로 그렇다.

첫 번째 for문에선 기준이 되는 값을 가져온다. 그리고 인덱스 또한 가져온다.

두 번째 for문에선 첫 번째 for문 이후의 index에 접근하며 값을 비교한다. 기준점이 되는 값이 더 크면 min 값을 그 작은 값으로 바꿔준다(기준값이 아님. 기준 값보다 더 작은 값). 그리고 해당되는 인덱스를 minindex에 저장한다.

min이 더 작게 되면 조건에 걸리지 않는다. 그렇게 minindex를 구하게 되면

기준이 되는 index(sel) 값을 작은 값이 있었던 minindex에 넣어주고 작은 값(min)을 기준이 되는 index ( sel )에 넣어준다!

 

 

그래서 위와 같이 나온다.

1, 4, 5, 2, 3 이 있으면

맨 처음 기준은 1이다. 여기선 1이 제일 작으니 비교를 해도 문제가 없다. 

다음은 4이다. 5랑 비교를 하면 별 문제가 없는데, 2랑 비교를 하면 조건에 걸린다. 그리고 3은 2보다 덜 작으니까 조건에 걸리지 않는다. 이렇게 반복하면서 값을 바꿔주면 정렬이 된다!

이것이 선택 정렬이다

 

다음은 삽입 정렬(insertion sort)를 알아본다

삽입 정렬은 아래 그림과 같다.

 

source : https://www.w3resource.com/python-exercises/data-structures-and-algorithms/python-search-and-sorting-exercise-6.php

 

작은 값이 있으면 계속 앞으로 보내는 작업을 한다.

즉 값을 뽑아낸 뒤 작은 영역으로 삽입한다. 이것이 삽입 정렬의 알고리즘이다.

 

 

 

파이썬 코드로 보면 위와 같다.

배열을 입력 받고 첫 for문을 돌 때 1번 인덱스부터 진행한다. 그리고 그 값을 temp에 저장하고 index를 ins_idx에 넣어둔다.

다음 while문을 도는데 temp보다 현재 인덱스 - 1 값이 더 클 때까지 진행한다. 앞의 있는 값이 작은 값이면 이미 정렬이 되어 있기 때문에 의미가 없기 때문이다.

만약 앞의 값이 더 크면 앞의 값(index - 1의 값, ins_idx - 1)을 현재 인덱스( ins_idx )에 넣어준다. 그리고 idx를 감소 시키면서 계속 진행

그 while문이 끝나면 ins_idx가 변화가 있을 것이다. 앞의 값이 작았으면 계속 - 등이 되어서.

그 값에 이제 아까 저장해뒀던 temp를 넣어준다.

 

위와 같이 진행된다

혹시 헷갈릴까봐 print로 진행 상황을 볼 수 있도록 했다.

이걸로 파이썬으로 삽입 정렬, 선택 정렬 공부 끝!