CS : Algorithm : Sort

Selection Sort

 

 

1.

해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

 

2.

• 첫 번째 순서 : 첫 번째 위치에 가장 최솟값을 넣는다.
• 두 번째 순서 : 두 번째 위치에 남은 값 중, 가장 최솟값을 넣는다.
• 반복

 

 

 

---

 

Insertion Sort

 

 

1.

배열에서, 앞에서부터 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾는 알고리즘

 

2.

• 두 번째 값 : 첫 번째 값 비교하여 자신의 자리를 찾는다.
• 세 번째 값 : 첫 번째 값, 두 번째 값과 비교하여 자신의 자리를 찾는다.
• 네 번째 값 : 첫 번째 값, 두 번째 값, 세 번째 값과 비교하여 자신의 자리를 찾는다.
• 반복

 

 

 

 

---

 

 

Bubble Sort

 

 

1.

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

 

2.

• 첫 번째 루프 : 첫 번째 자료와 두 번째 자료 비교, 두 번째 자료와 세 번째 자료 비교 ... -> 가장 큰 수가 맨 마지막에 위치 함
• 두 번째 루프 : 첫 번째 자료와 두 번째 자료 비교, 두 번째 자료와 세 번째 자료 비교 ... -> 그 다음 큰 수가 맨 마지막의 전에 위치함
• 반복

 

 

 

---

 

 

Merge Sort

 

 

1.

divide and conquer 방식이다.

즉, 문제를 작은 2개의 문제로 분리하고, 각각 해결한 다음, 결과를 합쳐 원래의 문제를 해결하는 전략이다.

 

2.

• 분할 (Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
• 정복 (Conquer) : 부분 배열을 정렬한다. 만약, 부분 배열의 크기가 충분히 작지 않다면 순환 호출을 통해 다시 분할 정복 방법을 적용한다.
• 결합 (Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.

 

 

 

 

---

 

 

Quick Sort

 

 

1.

평균적으로 가장 빠른 속도를 자랑한다.

 

2.

이 역시, divide and conquer 방식을 사용한다.

 

3.

• 분할 (Divide) : 입력 배열을 pivot 기준으로 비균등하게, 2개의 부분 배열로 분할한다. (pivot을 중심으로, 왼쪽은 pivot보다 작은 요소, 오른쪽은 큰 요소)
• 정복 (Conquer) : 부분 배열을 정렬한다. 만약, 부분 배열의 크기가 충분히 작지 않다면 순환 호출을 통해 다시 분할 정복 방법을 적용한다.
• 결합 (Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.

 

4.

pivot을 '잘' 선택하여 배열이 '균형'하게 분할될수록 빨라진다.

 

 

 

 

 

---

 

 

정렬 알고리즘 비교