23.09.11 정렬 알고리즘

버블 정렬 (Bubble Sort)

• 작동 원리: 인접한 두 원소를 비교하여 필요하면 스왑(swap)한다. 이 과정을 반복하여 가장 큰 원소가 배열의 마지막으로 이동하게 하는 방식이다.
• 시간 복잡도: O(n^2)
• 특징: 구현이 간단하나, 실제 사용에서는 비효율적이다.

 

삽입 정렬 (Insertion Sort)

• 작동 원리: 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 원소를 정렬된 부분에 올바른 위치에 삽입한다.
• 시간 복잡도: O(n^2), 하지만 이미 정렬된 배열에 대해서는 O(n)
• 특징: 작은 데이터셋에서 효율적이며, 안정적인 정렬 알고리즘이다.

 

선택 정렬 (Selection Sort)

• 작동 원리: 주어진 리스트 중에서 최소값을 찾아서 첫 번째 위치에 있는 값과 교체한다. 그 다음, 두 번째 위치에 올 값도 같은 방식으로 찾는다.
• 시간 복잡도: O(n^2)
• 특징: 버블 정렬과 마찬가지로 구현이 간단하나, 실제 사용에서는 비효율적이다.

 

퀵 정렬 (Quick Sort)

• 작동 원리: 피벗(pivot) 원소를 선택하고 피벗을 기준으로 작은 원소와 큰 원소로 분할한 뒤, 각 부분 배열에 대해 재귀적으로 정렬한다.
• 시간 복잡도: 평균과 최선의 경우 O(n log n), 최악의 경우 O(n^2)
• 특징: 평균적으로 매우 빠르며, 메모리 사용이 적다.

 

병합 정렬 (Merge Sort)

• 작동 원리: 배열을 더 이상 나눌 수 없을 때까지 재귀적으로 나눈 후, 병합하면서 정렬한다.
• 시간 복잡도: O(n log n)
• 특징: 안정적이고, 빅데이터에 대해서도 효율적이다. 하지만 추가적인 메모리를 필요하다.

 

힙 정렬 (Heap Sort)

• 작동 원리: 배열을 힙 자료구조의 형태로 구성한 후, 힙에서 가장 큰 값(루트)를 가장 끝에 있는 값과 교체하고 힙을 재구성하는 과정을 반복한다.
• 시간 복잡도: O(n log n)
• 특징: 메모리를 추가로 사용하지 않지만, 안정적이지 않은 정렬 알고리즘이다.

 

설명을 보고 이해하면 어느정도 이해가 되지만 아에 무슨 정렬만 주고 설명하라 하면은 힘들 것 같으니 외울 필요가 있겠다.