[코딩테스트] 정렬 알고리즘(1) 선택 정렬과 삽입 정렬

정렬(sorting) : 데이터를 특정 기준에 따라 순서대로 나열하는 것.

문제 상황에 따라 적절한 정렬 알고리즘을 공식처럼 쓰자.

 

사람이 보기에는 바로 정렬 결과를 알아볼 수 있겠지만, 컴퓨터는 구체적으로 어떠한 방식으로 정렬을 수행할지 코드를 짜줘야 한다.

 

선택 정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.

0~9까지 10개의 카드가 랜덤하게 놓여있다고 가정해보자.

1. 처리되지 않은 데이터 중 가장 작은 0을 선택해, 첫 번째 위치의 숫자와 서로 위치를 바꾼다.

2. 남은 9개의 카드 중에서 가장 작은 숫자인 1을 선택해, 두 번째 위치의 숫자와 서로 위치를 바꾼다.

3. 정렬되지 않은 데이터가 1개 남았을 때에는 앞쪽으로 보내봤자 자기 자신의 위치와 동일하므로 따로 처리하지 않는다.

탐색 범위는 반복할 때마다 줄어들게 되고, 매번 가장 작은 원소를 찾기 위해서 탐색 범위만큼 데이터를 확인해서 가장 작은 데이터를 찾아야 하기 때문에, 선형 탐색과 동일하다.

따라서 이중 반복문을 작성하면 된다.

 

선택 정렬 코드

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

for i in range(len(array)): #i는 가장 작은 데이터와 위치가 바뀔 인덱스.(가장 앞쪽 원소의 위치) 
	min_index = i #가장 작은 원소의 인덱스
	for j in range(i+1, len(array)): #j 루프가 끝났을 때, 가장 작은 원소 위치가 min_index에 담김.
    	if array[min_index]>array[j]: 
        	min_index=j
    array[i], array[min_index] = array[min_index], array[i] #서로 바뀌도록 할 수 있음.
    
print(array)

선택 정렬 시간 복잡도

N번만큼 가장 작은 수를 찾아 맨 앞으로 보내기 때문에, N + (N-1)+(N-2)+...+2 까지 등차수열 형태가 된다.

이는 (N²+N-2)/2로 표현할 수 있는데, 빅오표기법에 따라 계수 생략, 차수가 가장 높은 항만 고려하면

선택 정렬의 시간 복잡도는 O(N²)이다.

 

 

삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입

선택 정렬에 비해 구현 난이도가 높지만, 더 효율적으로 동작한다.

0~9까지 10개의 데이터가 있다.

앞쪽에 있는 원소가 이미 정렬되어 있다고 가정하고, 뒤쪽에 있는 요소를 앞쪽으로 들어가게끔 한다.

 

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

1. 7은 그 자체로 정렬이 되어 있다고 가정하고, 두 번째 데이터인 5가 7의 왼쪽으로 들어갈 것인지? 오른쪽으로 들어갈 것인지? 두 경우만 판단한다.

2. 세 번째 데이터인 9는, 차례대로 왼쪽에 있는 데이터와 비교해서 더 크다면 그대로 오른쪽에 있도록 한다.

3. 네 번째 데이터인 0은 매번 왼쪽에 있는 데이터들과 비교해서 제일 왼 쪽으로 차근차근 이동하도록 한다.

4. 이 과정을 반복한다.

 

삽입 정렬 코드

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

for i in range(1, len(array)): # 두 번째 원소부터 시작.
	for j in range(i,0,-1): #인덱스 i부터 0까지 1씩 감소하며 반복하는 것. 여기서 j는 삽입하고자 하는 원소를 의미.
    	if array[j]<array[j-1]: #왼 쪽에 있는 데이터와 비교해서, 더 작다면 위치를 바꿔준다.
        	array[j], array[j-1] = array[j-1], array[j]
        else : #자기보다 작은 데이터를 만나면 그 위치에서 멈춘다.
        	break
print(array)

삽입 정렬의 시간 복잡도

 

삽입 정렬의 시간 복잡도는 O(N²)이다. 선택 정렬처럼 반복문이 두 번 중첩되어 있는데, 이중 for문이 사용된다 해서 반드시 O(N²)인 것은 아니고, 반복문 안에 함수가 들어있다면 그 시간까지 고려해야 한다.

 

현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다!

이미 정렬되어 있는 상태에서 다시 삽입 정렬을 수행하면, 바로 왼쪽에 있는 원소와 비교했을 때 위치를 바꿀 필요가 없다. 따라서 멈추고 넘어가고, 멈추고 넘어가는 식이므로 단순히 상수 O(N)의 시간 복잡도만 가질 수도 있다.

 

정렬 알고리즘의 꽃인 퀵 정렬과 계수 정렬은 다음 포스팅에서 이어서 알아보자.

 

2023.01.24 - [Data Science] - [코딩테스트] DFS BFS 문제 풀이 실습

2023.01.23 - [Data Science] - [코딩 테스트] DFS BFS 개념 - 스택 큐 자료구조 재귀함수 기초

2022.12.24 - [Data Science] - [코딩테스트] 구현, 시뮬레이션과 완전 탐색

2022.12.23 - [Data Science] - [코딩테스트] 그리디 알고리즘(Greedy), 탐욕법

2022.12.20 - [Data Science] - [코딩테스트] 파이썬 문법 기초 복습 : 입출력부터 자주 쓰이는 라이브러리까지

2022.12.19 - [Data Science] - [코딩테스트] 파이썬 문법 기초 복습 : 자료형

2022.12.18 - [Data Science] - [코딩테스트] 코딩테스트 및 관련 알고리즘의 개요

 

 

https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC
*내용에 대한 모든 저작권은 해당 영상의 원저작자에게 있습니다.