정렬(1)-선택, 삽입 정렬

정렬

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

정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능하다.

정렬 중에서 많이 사용하는 것은 선택, 삽입, 퀵, 계수 정렬 등이 있다.

파이썬에서는 리스트의 원소를 뒤집는 메서드를 제공하고 이 것은 O(N) 복잡도로 간단하게 수행된다.

 

선택 정렬

데이터가 무작위로 여러 개 있을 때, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것이 선택 정렬이다.

 

이렇게 데이터가 있으면 처음엔 0이 선택되어 맨 앞의 7과 자리가 바뀌게된다.

 

그 다음엔 제일 작은 1이 선택되어 5와 자리를 바꾼다.

 

이런식으로 하다보면 정렬이 가능하다. 

이 과정에서 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하면 정렬이 완료된다.

 

-선택 정렬 코드 예시

ary = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(ary)):
  min_idx = i
  for j in range(i+1, len(ary)):  
    if ary[min_idx] > ary[j]: 
      min_idx = j
  ary[i], ary[min_idx] = ary[min_idx], ary[i]

print(ary)

처음부터 비교하면서 인덱스 번호를 기록한다. 그리고 맨 앞보다 작은 것이 있다면 스와프해준다.

스와프는 파이썬에선 ary[i], ary[min_idx] = ary[min_idx], ary[i] 이런식으로 할 수 있다.

 

-시간 복잡도

선택 정렬은 N-1번 만큼 가장 작은 수를 맨 앞으로 보내야 한다. 그리고 매번 가장 작은 수를 찾기 위한 연산이 필요하다.

연산 횟수는 N + (N-1) + (N-2) + ... + 2로 볼 수 있다. 근사치로 N * (N+1)이다.

따라서 빅오 표기법으로 O(N^2)라고 표현할 수 있다.

직관적으로 이해하면 소스코드 상으로 간단한 형태의 2중 반복문이 사용되어서 이다.

 

삽입 정렬

선택 정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편이다.

삽입 정렬은 필요할 때만 위치를 바꿔서 데이터가 거의 정렬되어 있을 때 효율적이다.

 

삽입 정렬은 특정한 데이터를 적절한 위치에 삽입한다는 의미이다.

삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.

 

 

이렇게 있으면 삽입 정렬은 두 번째 데이터부터 시작한다. 왜냐면 첫 번째 데이터는 이미 정렬되었다고 판단하기 때문이다.

1. 두 번째 데이터인 5는 7의 왼쪽이나 오른쪽으로 가는 두 경우만 존재한다.

오름차순으로 정렬하면 7의 왼쪽에 삽입된다.

 

2. 그리고 9는 7보다 커서 그대로 내비둔다.

 

이런식으로 적절한 위치에 삽입하는 과정을 N-1번 반복하면 정렬이 완료된다.

 

-삽입 정렬 코드 예시

ary = [7,5,9,0,3,1,6,2,4,8]

for i in range(1, len(ary)):
  for j in range(i, 0, -1):
    if ary[j] < ary[j-1]:
      ary[j], ary[j-1] = ary[j-1], ary[j]
    else:
      break

print(ary)

1번째 인덱스부터 비교해서 첫번째 for문을 1부터 시작한다.

그리고 두번째 for문은 여태 훑어본거 끼리만 비교를 한다. 그래서 뒤에서부터 비교하면서 정렬을 해준다.

else는 자기보다 작은 데이터를 만나면 종료한다.

 

-시간 복잡도

삽입 정렬의 시간 복잡도는 O(N^2)이다. 반복문이 2번 사용되었기 때문이다. 

꼭 기억할 내용은 삽입 정렬은 데이터가 어느정도 정렬되어 있다면 매우 빠르게 동작한다.

최선의 경우 O(N) 시간 복잡도를 가진다.

퀵 정렬과 비교하면 비효율적이지만 정렬이 거의 되어있는 상태에서는 삽입 정렬이 더 빠르다.