99클럽 코테 스터디 39일차 TIL + 정렬 알고리즘(Sort Algorithm)(2)

학습 키워드

- 정렬 알고리즘(Sort Algorithm)

 

공부한 내용

정렬 알고리즘 - 3 : 선택 정렬 (Selection Sort)

• 선택 정렬은 주어진 배열에서 최소값을 찾아서 맨 앞의 원소와 자리를 바꾸고 그 다음으로 작은 값을 찾아서 두 번째 원소와 자리를 바꾸는 식으로 정렬하는 알고리즘 중 하나이다.

→ 맨 앞 인덱스부터 차례대로 들어갈 원소를 선택하여 정렬하는 알고리즘이다.

• 정렬할 원소의 개수가 적을 때나 이미 거의 정렬된 상태일 때 사용될 수 있다.
• 그러나 대부분의 경우 다른 정렬 알고리즘보다 느리고 비효율적이기 때문에, 실제로 사용되는 경우는 드물다. (버블 정렬보다 성능이 좋다.)

선택 정렬의 동작 방식

1. 배열에서 가장 작은 요소(최소값)를 찾는다.
2. 가장 작은 요소와 배열의 첫 번째 요소를 교환한다.
3. 두 번째로 작은 요소를 찾아 두 번째 요소와 교환한다.
4. 이러한 과정을 배열의 끝까지 반복한다.

정렬 알고리즘 - 4 : 삽입 정렬 (Insertion Sort)

• 삽입 정렬은 정렬되지 않은 부분에서 값을 선택하고 그 값을 이미 정렬된 뿐의 올바른 위치에 삽입하는 과정을 수행하는 알고리즘이다.
• 인덱스 1부터 앞 방향으로 들어갈 위치를 찾아 교환하는 정렬 알고리즘이다.
• 이를 통해 정렬되지 않은 부분은 점차적으로 감소하고 전체 배열이 정렬되게 된다.
• 정렬이 되어 있는 배열의 경우 O(n)의 속도로 정렬되어 있을 수록 성능이 좋다.

삽입 정렬의 동작 방법

1. 배열의 두 번째 요소부터 시작한다.
2. 현재 위치의 요소를 기준으로, 이전 위치의 요소들과 비교한다.
3. 이전 위치의 요소가 현재 위치의 요소보다 크다면, 이전 위치의 요소를 현재 위치로 이동시킨다.
4. 이전 위치의 요소가 현재 위치의 요소보다 작거나 같다면, 정렬이 완료된 것으로 간주하고 다음 요소로 이동한다.
5. 배열의 시작에 도달할 때까지 반복한다.

정렬 알고리즘 - 5 : 병합 정렬 (Merge Sort)

• 병합 정렬은 배열을 반으로 나누어 각각을 정렬한 후, 병합하는 과정을 통해 전체 배열을 정렬한다.
• 분할 정복 알고리즘 중 하나이다.
• 배열의 길이가 1이 될 때까지 2개의 부분 배열로 분할한다. 분할이 완료되면 다시 2개의 부분 배열을 합병하고 정렬한다. 모든 배열이 합병될 때 까지 반복한다.
• 배열은 반으로 나누어 각각을 재귀적으로 정렬한다. 그리고 정렬된 두 개의 배열을 병합하는 단계에서 작은 값을 선택하여 새로운 배열에 차례대로 배치한다. 이 과정을 반복하면서 전체 배열이 정렬되게 된다.
• 시간 복잡도가 O(nlog n)으로 빠르지만, 아래 코드를 보면 tmpArr을 사용해야 돼서 제자리 정렬보다 O(n)만큼 추가적인 메모리가 사용되는 단점이 있다. 보통은 재귀함수로 구현하므로 이 것또한 메모리를 많이 사용하게 된다.

병합 정렬의 동작 방식

1. 배열을 반으로 나눈다.
2. 각 반쪽을 재귀적으로 정렬한다.
3. 정렬된 두 개의 반쪽을 병합하여 하나의 정렬된 배열로 합친다.

정렬 알고리즘 - 6 : 힙 정렬 (Heap Sort)

• 힙 정렬은 주어진 배열을 힙으로 만들고, 가장 큰 값을 배열의 가장 마지막으로 보내는 방식으로 정렬을 진행한다.
• 안정적인 정렬 알고리즘이며, 평균적으로 다른 정렬 알고리즘에 비해 빠른 실행 시간을 가지는 특징이 있다. 그러나 추가적인 메모리 공간이 필요하다는 단점이 있다.

힙 정렬의 동작 과정

1. 주어진 배열을 최대 힙(Max Heap)으로 구성한다.
2. 최대 힙에서 가장 큰 요소(루트)를 가져와 배열의 맨 끝으로 이동시킨다.
3. 배열의 크기를 줄이고, 남은 요소들을 다시 최대 힙으로 구성한다.
4. 위의 과정을 반복하여 정렬이 완료될 때까지 진행한다.

 

 

참고 자료

- https://adjh54.tistory.com/334

- https://sjh9708.tistory.com/209