[알고리즘] 정렬

선택정렬 O(n^2)

원소를 넣은 위치를 정해두고 해당 위치에 들어가야하는 원소를 찾아서 넣는 것

ex) 제일 작은 원소를 찾아 첫번째 자리에 넣고 두번째 작은 원소를 찾아 두번째 자리에 두고….

• 코드

(정렬) 선택정렬 코드

---

삽입정렬 O(n) ~ O(n^2)

앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아서 삽입하는 것

ex)

31 [25] 12 22 11

(25) 31 [12] 22 11

(12) 25 31 [22] 11

12 (22) 25 31 [11]

(11) 12 22 25 31

• 코드

(정렬) 삽입 정렬

---

버블정렬 O(n^2)

인접한 두 원소를 비교하며 나가는 코드 - 가장 큰 수가 제일 마지막으로 가도록 정렬된다.

속도는 느리나 코드가 단순하다.

ex)

[31][25] 12 22 11

(25) [31][12] 22 11

25 (12) 31 22 11

…

[25][12] 22 11 31

…

11 12 22 25 31

• 코드

(정렬) 버블정렬

---

퀵정렬 O(n log n) ~ O(n^2)

하나의 피봇을 기준으로 피봇보다 작으면 왼쪽 피봇보다 크면 오른쪽으로 이동시키며 정렬시키는 방식이다.

ex)

31 25 12 22 11 - pivot : 22

• 31은 22보다 크므로 오른쪽으로 이동, 11은 22보다 작으므로 왼쪽으로 이동

11 25 12 22 31

…

11 12 22 25 31

• 코드

(정렬) 퀵정렬

---

합병정렬 - O(nlogn)

하나의 리스트를 동일한 크기의 배열 2개로 계속 분할하여 분할한 배열의 크기가 1이되면

분할된 배열을 병합하면서 정렬을 해나가는 방식이다.

• 코드
  (정렬) 합병정렬 코드