[Python] 선택 정렬 & 삽입 정렬

*해당 포스팅은 이것이 코딩 테스트다 with python(나동빈 지음) 교재를 공부하며 작성한 글입니다.

 

 

안녕하세요! 오늘은 정렬 알고리즘 중 선택 정렬과 삽입 정렬에 대해 알아보겠습니다.

 

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

 

문제 상황에 적절하지 않은 정렬 알고리즘을 이용하면 프로그램이 비효율적으로 동작하여 필요 이상으로 시간을 많이 소요하게 됩니다.

 

따라서 상황에 맞는 적절한 정렬 알고리즘을 사용하는 것이 중요하다고 할 수 있습니다.

 

 

정렬 알고리즘에 대해 공부하기 전에 알고리즘의 효율성을 나타내는 척도인 시간 복잡도에 대해 알아보겠습니다.

 

시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미합니다.

 

알고리즘의 성능을 평가할 때 최악의 경우, 평균의 경우, 최선의 경우가 존재하는데 최악의 경우의 시간 복잡도를 우선적으로 고려해야 합니다.

 

시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용합니다.

 

빅오 표기법이란 최고 차수의 항만 고려하는 표기법입니다.

 

빅오 표기법

 

빅오 표기법에 대해 이해하기 쉽게 예를 들어보겠습니다. 

 

for i in range(10):
  for j in range(10):
    result=i+j
    print(result)

 

이 코드의 경우 연산을 10*10 만큼의 연산을 해야 합니다.

 

이는 N*N 즉, N^2만큼의 연산이 필요하다는 것을 알 수 있고 이 코드의 시간 복잡도는 빅오 표기법으로 O(N^2) 임을 알 수 있습니다.

 

코딩 테스트에서는 시간제한이 존재하기 때문에 N의 크기가 엄청 커지면 효율적인 알고리즘을 사용하지 않는다면 시간 초과를 받을 수 있습니다.

 

따라서 N의 범위에 따라 적당한 시간 복잡도를 나타내면 다음과 같습니다.

 

 

 

 

시간 복잡도에 대해 알아보았고 이제 정렬 알고리즘에 대해 알아보겠습니다.

 

 

 

1. 선택 정렬

 

선택 정렬이란 가장 원시적인 방법으로 매번 가장 작은 것을 선택하는 알고리즘입니다. 

 

가장 작은 데이터를 선택해 앞으로 앞으로 보내는 과정을 반복하는 알고리즘입니다. 

 

파이썬 코드는 다음과 같습니다.

 

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

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

print(array)

 

min_index란 가장 작은 데이터의 위치를 저장하는 변수입니다.

 

array 리스트의 길이가 N이라 하면 i는 0부터 N-1까지 증가하는데

 

i가 0일 때는 array[1]부터 array[N-1]까지 반복하여 array[min_index]와 값을 비교합니다.

 

만약 array[min_index]보다 값이 작다면 그 위치의 index가 min_index가 됩니다.

 

반복이 끝난 후 array[min_index]와 array[i]의 값을 바꿔줍니다.

 

그다음에는 i가 1이 되고 같은 과정을 반복합니다.

 

이를 i가 N-1일 때까지 반복합니다.

 

 

이렇게 하면 리스트 안의 수는 정렬됩니다.

 

선택 정렬의 시간 복잡도를 알아보겠습니다.

 

선택 정렬의 연산 횟수는 N + (N-1) + (N-2) + ... + 2 임을 알 수 있습니다.

 

따라서 선택 정렬의 시간 복잡도는 O(N^2)이라고 표현할 수 있습니다.

 

 

2. 삽입 정렬

 

삽입 정렬이란 특정한 데이터를 적절한 위치에 삽입하여 정렬하는 알고리즘입니다.

 

특히 삽입 정렬은 데이터가 거의 정렬되어 있을 때 훨씬 효율적입니다.

 

파이썬 코드는 다음과 같습니다.

 

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

for i in range(1,len(array)):
  for j in range(i,0,-1):
    if array[j-1]>array[j]:
      array[j],array[j-1]=array[j-1],array[j]
    else:
      break
    
print(array)

 

삽입 정렬은 두 번째 데이터부터 시작합니다.

 

첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문이입니다.

 

j는 i부터 해서 1까지 1씩 감소합니다.

 

자신의 왼쪽 데이터가 자신보다 크다면 위치를 바꿔주고 자신의 왼쪽 데이터가 자신보다 작으면 그 자리에서 멈추고 반복문을 빠져나옵니다.

 

이를 i가 1부터 len(array)-1까지 반복합니다.

 

삽입 정렬의 시간 복잡도를 알아보겠습니다.

 

삽입 정렬도 반복문이 2번 중첩되었으므로 O(N^2) 임을 알 수 있습니다.

 

하지만 리스트의 데이터가 거의 정렬되어 있는 상태라면 O(N)의 시간 복잡도를 가질 수 있습니다.

 

따라서 거의 정렬되어 있는 상태로 입력이 주어지는 문제라면 여타 알고리즘보다 삽입 정렬 알고리즘을 이용하는 것이 효율적이라 할 수 있습니다.

 

 

 

지금까지 시간 복잡도에 대한 설명과 정렬 알고리즘 중 선택 정렬과 삽입 정렬에 대해 알아보았습니다.