[정렬 개념] 버블정렬/선택정렬/삽입정렬/합병정렬

https://www.youtube.com/playlist?list=PLDV-cCQnUlIZXLSUeF2Fav3_7X7ku-F63 

코딩테스트 Sorting

코드없는 프로그래밍님의 Sorting 재생목록을 보며 공부한 내용을 기록했습니다.

 

간단하지만 느린	복잡하지만 빠른
버블정렬, 삽입정렬, 선택정렬	퀵정렬, 합병정렬, 힙정렬

 

시간복잡도가 O(N)인 알고리즘 = radix정렬(기수정렬)

 

 

버블정렬

---

 

 

숫자 두개를 버블로 만들어서 두 숫자 중 큰 것을 뒤로 보내서 정렬한다.

 

버블정렬의 특징

---

- 시간복잡도가 O(n**2)이고, 굉장히 느리다 

- Stable한 sorting 방법이다. 

 

 

 

+) Stable하다는 것의 의미

 

[7a,5a,5b,7b,3c] 가 있을 때 이것을 숫자를 기준으로 버블정렬하면

[5a,5b,7a,3c,7b]

[5a,5b,3c,7a,7b]

[5a,3c,5b,7a,7b]

[3c,5a,5b,7a,7b] 로 정렬이 마무리 된다.

 

처음과 마지막을 살펴보면

[7a,5a,5b,7b,3c]

[3c,5a,5b,7a,7b]

 

 a,b 순서대로 정렬이 이루어진 것을 볼수 있다. 이를 stable한다고 한다. 

만약 stable하지 않다면 숫자는 오름차순으로 정렬이 되어도 a,b순서대로 정렬이 되지 않는다. 이는 선택정렬에서 설명하겠다.

 

삽입 정렬

---

[9,3,5,7,1] 의 숫자배열이 있다.

우선 첫번째 수인 9는 이미 정렬이 되어있다고 생각하기 때문에 두번째 수인 3부터 비교한다.

3은 9보다 작기에 9보다 앞에 3을 삽입해준다.

[3 9 5 7 1]

5는 3보다 크고 9보다 작기에 그 사이에 삽입해준다.

[3 5 9 7 1]

 

이것을 반복하면

[3 5 7 9 1]

[1 3 5 7 9] --> 정렬이 끝난다!

 

 

 

삽입정렬의 특징

---

- 시간복잡도가 O(n**2)이다.

- 얘도 버블정렬처럼 느리다. 

 

선택정렬

---

[3 5 9 1 7] 이 있다. 이 수들을 선택정렬하면

우선 , 첫번째 수인 3을 기준으로 3뒤에 있는 수들 중 3보다 작은 수를 찾아 3과 자리를 바꿔준다.

즉,element를 하나 찾아서 swap해준다.

 

5,91,7 중 3보다 작은 수는 1이므로

[1,5,9,3,7]이 된다. 이렇게 정렬을 계속반복하면

[1,3,9,5,7]

[1,3,5,9,7]

[1,3,5,7,9] 로 정렬을 마무리하게 된다. 

 

선택정렬의 특징

---

- stable하지 않다

- 시간복잡도가 O(n**2)이다.

 

+) Stable하지 않다는 것의 의미

 

[7a,7b,5a,5b,3c]가 있다 이를 숫자를 기준으로 선택정렬로 풀어보면

[3c,7b,5a,5b,7a]

[3c,5a,7b,5b,7a]

[3c,5a,5b,7b,7a] --> 어차피 숫자를 기준으로 정렬한 것이기에 7b와 7a는 swap하지 않음

 

첫번째와 마지막을 보면

 

[7a,7b,5a,5b,3c]

 

[3c,5a,5b,7b,7a] 

 

a,b순서가 보장되지 않은 것을 볼 수 있다. 이것을 stable하지 않다고 표현한다. 

 

 

병합정렬

---

숫자 배열이 7 3 1 5 6 4 2가 있다.

이것을 (7 3 1) (6 5 4 2)로 나눌 수 있고

 

( 7 3 1) 에서는 7 / 3 1

(5 6 4 2 ) 에서는 5 6/ 4 2 로 나뉠 수 있다.

 

그럼 이렇게 나눠진 상황에서 정렬을 해보면

 

7 1 3 5 6 2 4가 나오는 것을 알 수 있다.

그러면 다시 (7 1 3) (5 6 2 4) 로 나눠서 정렬을 하면

 

(1 3 7) (2 4 5 6) 이 된다. 

 

이 두 집단을 합쳐서 정렬을 해볼 것이다. 

 

A 그룹을 1 3 7

B 그룹을 2 4 5 6 이라 하면

 

1과 2에 포인터가 있다고 생각해서 A그룹의 1 과 B 그룹의 2를 비교해준다 -> 1 2 3 7 4 5 6으로 정렬된다

A그룹의 3과 B그룹의 4를 비교한다 -> 1 2 3 4 5 6 7 로 정렬된다

 

마지막으로 A그룹의 7과 B그룹의 5,6을 비교해주면  1,2,3,4,5,6,7로 정렬된다.

 

 

병합정렬의 특징

---

 

- O(nlog n)의 시간복잡도를 가진다.

- Stable한 특징을 가지고 있다.