[알고리즘] 정렬 알고리즘① : 선택정렬과 삽입정렬, 버블정렬(정의/특징/복잡도)

파이썬에는 sorted()나 sort()같은 메소드가 존재하는데, 굳이 정렬을 공부해야하는 이유는 무엇일까? 

> 그 이유는 정렬은 모든 알고리즘의 기본이자 문제해결의 기초가 되기 때문이다.

 

그래서 오늘은 정렬 알고리즘의 세가지 선택정렬과 삽입정렬 그리고 버블정렬에 대해서 공부하겠다.

 

 

선택정렬

선택 정렬(selection sort)은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다. 즉, 각 위치에 어떤값이 들어갈지 찾는방법과 유사하다.

다음과 같은 정렬되지 않은 리스트가 존재할 때,

 

 

1 ) 가장 작은 데이터인 1을 가장 앞에 위치한 15와 교환한다. 가장 작은 데이터가 가장 앞에 위치하게 된다.

 

2 ) 첫 번째 데이터를 제외한 나머지 데이터에서 가장 작은 데이터인 3을 두 번째 데이터인 11과 교환한다.

 

3 ) 첫 번째, 두 번째 데이터를 제외한 나머지 데이터에서 가장 작은 데이터인 8을 세 번째 데이터인 15와 교환한다.

4 ) 첫 번째, 두 번째, 세 번째 데이터를 제외한 나머지 데이터에서 가장 작은 데이터인 11을 네 번째 데이터인 11과 교환한다. 같은 데이터이므로 위치의 변화는 없다.

 

 

5) 데이터들에 대한 정렬이 완료된다.

 

 

 

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

 

 

삽입정렬

삽입 정렬(insertion sort)은 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식이다. 즉, 각 값이 어떤 위치로 들어갈지찾는 방법과 유사하다.

다음과 같은 정렬되지 않은 리스트가 존재할 때,

 

1) 두 번째 데이터 11과 바로 앞에 위치한 15의 크기를 비교한다. 두 번째 데이터가 작으므로 15를 한 칸 뒤로 보내고 11을 15 앞에 위치시킨다.

 

 

2) 세 번째 데이터인 1과 앞에 위치한 11, 15의 크기를 비교한다. 1이 가장 작으므로 11과 15를 한 칸씩 뒤로 보내고 1을 가장 앞에 위치시킨다.

 

 

3) 네 번째 데이터인 3과 앞에 위치한 1, 11, 15의 크기를 비교한다. 3은 1보다 크고 11, 15보다 작으므로 11과 15를 한 칸씩 뒤로 보내고 3을 11 앞에 위치시킨다.

 

4)  마지막 데이터인 8과 앞에 위치한 1, 3, 11, 15의 크기를 비교한다. 1, 3보다 크고 11, 15보다 작으므로 11과 15를 한 칸씩 뒤로 보내고 8을 11 앞에 위치시킨다.

 

 

5) 데이터들에 대한 정렬이 완료된다.

 

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

 

 

버블정렬

버블 정렬(bubble sort)은 서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식이다.

다음과 같은 정렬되지 않은 리스트가 존재할 때,

 

1) 첫 번째 데이터인 15와 두 번째 데이터인 11을 비교해 큰 데이터를 뒤로 위치시킨다. 15가 크므로 둘의 위치를 바꾼다.

 

 

2) 두 번째 데이터인 15와 세 번째 데이터인 1을 비교하는데, 앞에 위치한 15가 크므로 둘의 위치를 바꾼다.

3) 마찬가지 방식을 적용해 세 번째 데이터인 15와 네 번째 데이터인 3의 위치를 바꾼다.

4) 마찬가지 방식을 적용해 네 번째 데이터인 15와 마지막 데이터인 8의 위치를 바꾼다. 가장 큰 데이터인 15가 가장 뒤에 위치하게 된다.

5) 처음부터 다시 시작한다. 첫 번째 데이터인 11과 두 번째 데이터인 1의 크기를 비교하는데 앞에 위치한 11이 크므로 둘의 위치를 바꾼다.

6) 마찬가지 방식을 적용해 두 번째 데이터인 11과 세 번째 데이터인 3의 위치를 바꾼다.

7) 마찬가지 방식을 적용해 세 번째 데이터인 11과 네 번째 데이터인 8의 위치를 바꾼다. 두 번째로 큰 데이터인 11이 뒤에서 두 번째에 위치하게 된다.

 8) 처음부터 다시 시작한다. 첫 번째 데이터인 1과 두 번째 데이터인 3의 크기를 비교하는데 앞에 위치한 1이 작으므로 그대로 둔다.

 

9) 두 번째 데이터인 3과 세 번째 데이터인 8의 크기를 비교하는데, 앞에 위치한 3이 작으므로 그대로 둔다. 세 번째로 큰 데이터인 8이 뒤에서 세 번째에 위치하게 된다.

 

10) 처음부터 다시 시작한다. 첫 번째 데이터인 1과 두 번째 데이터인 3의 크기를 비교하는데, 앞에 위치한 1이 작으므로 그대로 둔다. 데이터들에 대한 정렬이 완료된다.

 

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

 

 

 

출처: 네이버지식백과