[알고리즘] 기본 정렬 알고리즘 (Sorting Algorithms)

✅ 정렬 알고리즘이란?

정렬 알고리즘은 데이터 요소들을 특정 순서대로 정렬하는 알고리즘이다.
일반적으로 리스트나 배열 같은 데이터 구조에 저장된 요소들을 오름차순이나 내림차순 같은 순서로 재배열하는 데 사용된다.

 

 

• 선택 정렬 (Selection Sort)
• 삽입 정렬 (Insertion Sort)
• 버블 정렬 (Bubble Sort)
• 합병 정렬 (Merge Sort)
• 퀵 정렬, 퀵소트 (Quick Sort)

 

✅ 선택 정렬 (Selection Sort)

선택 정렬은 배열에서 가장 작은(또는 가장 큰) 요소를 찾아서 리스트의 가장 앞, 또는 가장 뒤로 옮기고, 정렬되지 않은 나머지 리스트 부분에 같은 과정을 반복하여 전체 배열을 정렬하는 방식이다. 예시는 단순히 최댓값을 찾은 후 리스트의 뒤로 옮기는 과정을 반복하고 있다.

 

 

 

선택 정렬의 시간 복잡도

선택 정렬은 모든 상황에서 O(n2)의 시간 복잡도를 가진다. 각 자리에 와야하는 최솟값, 또는 최댓값을 구하기 위하여 n-1, n-2, n-3, ... , 1번의 비교연산을 수행하기 때문이다.

 

구현이 쉽지만 대규모데이터에서는 비효율적이다

 

---

 

 

✅ 삽입 정렬 (Insertion Sort)

삽입 정렬은 배열의 각 요소를 이미 정렬된 부분과 비교하여 적절한 위치에 삽입함으로써 배열을 정렬하는 방법이다. 아래 예시 리스트는 이미 정렬된 부분(색칠된 부분)에 31을 삽입하는 과정을 보여준다.

 

 

 

삽입 정렬의 시간 복잡도

모든 원소가 이미 정렬되어 있는 경우: O(n)
모든 원소가 이미 정렬되어 있는 경우, 각 원소를 삽입하는 과정에서 비교 연산은 1번씩만 수행된다. 원소를 삽입하는 과정은 n-1번 이루지므로, 시간 복잡도는 O(n)이 된다.

모든 원소가 역순으로 정렬되어 있는 경우: O(n2)
각 원소를 n-1번 삽입하는 동안 비교연산은 1, 2, 3, ... , n-1번 수행된다. 따라서 최악의 경우, 삽입 정렬의 시간 복잡도는 O(n2)이 된다.

 

적은 데이터에 효율적이고 이미 정렬된거는 정렬이 변하지않아서 안정정렬이며 거의 정렬된 데이터에 아주유리

---

 

✅ 버블 정렬 (Bubble Sort)

버블 정렬은 서로 인접한 2개의 원소를 비교하여, 크기가 순서대로 되어 있지 않으면 서로 교환하는 과정을 반복하여 전체 배열을 정렬하는 방식이다. 아래의 예시는 배열을 오름차순으로 정렬할 때, 인접한 2개의 원소를 비교하여 왼쪽의 원소가 오른쪽의 원소보다 클 경우 교환을 진행한다.

예시의 결과, 가장 큰 원소인 93이 배열의 가장 끝에 위치하게 된다. 이와 같이 버블 정렬을 1회전 수행할 때마다 정렬된 원소가 하나씩 늘어나게 되고, n회전을 수행하면 배열이 전부 정렬되게 된다.

 

 

버블 정렬의 시간 복잡도

버블 정렬은 모든 상황에서 O(n2)의 시간 복잡도를 가진다. 배열이 얼마나 정렬되었는지의 여부와 관계 없이, n-1, n-2, n-3, ... , 1번의 비교연산을 수행한다는 점을 알 수 있다.

 

구현은 가장 쉽지만 실무에서 거의 안쓰고 성능은 가장 나쁘다

 

---

 

✅ 합병 정렬 (Merge Sort)

 

합병 정렬은 분할 정복(Divide and Conquer) 전략을 사용하는 정렬 알고리즘이다. 합병 정렬은 하나의 배열을 두 개의 균등한 크기의 배열로 분할하고, 분할된 부분 배열들을 정렬한 다음, 정렬된 하위 배열들을 결합하는 방식으로 전체 배열을 정렬한다. 정렬은 아래의 단계로 이루어진다.

• 분할 (Divide)
  배열을 두 개의 동일한 크기의 하위 배열로 나눈다. 배열의 크기가 1이 될 때까지 이 과정을 재귀적으로 반복한다.
• 정복 (Conquer)
  나누어진 두 개의 배열을 정렬한다. 이 과정에서, 두 배열의 요소들을 각각 비교하여 결과 배열에 차례대로 배치한다.
• 결합 (Combine)
  분할된 배열을 순차적으로 합병하면서 최종적으로 하나의 정렬된 배열로 만든다.

아래의 예시는 위의 과정을 구체적으로 보여준다. 먼저 배열의 크기가 1이 될 때까지 분할 과정을 반복한다. 이후, 나누어진 두 개의 배열을 정렬한다. 예시의 일부를 설명하면, [26, 54] 와 [17, 93] 을 정렬하는 과정은 각 배열의 원소를 모두 비교하여 최소값 17을 먼저 위치시키고, 그 다음 26, 54, 93을 순차적으로 위치시키는 방식으로 진행된다. 결과적으로 분할된 배열을 합병하는 방식으로 정렬이 수행된다.

 

 

 

 

 

합병 정렬의 시간 복잡도

합병 정렬은 모든 상황에서 O(n log n)의 시간 복잡도를 가진다.

크기가 n인 배열을 분할하는 작업 자체에는 상수 시간, 즉 O(1)이 소요된다. 하지만 중요한 것은 분할의 깊이, 즉 재귀의 깊이이다. 배열의 크기를 계속 반으로 나누면, 로그(log) 스케일로 깊이가 결정된다. 따라서 분할의 최대 깊이는 log n이다.

각 분할 단계에서, 합병 작업은 두 하위 배열의 전체 길이에 비례하는 시간이 소요된다. 각 분할 레벨에서 배열의 총 길이는 n이므로 각 레벨의 합병 작업에는 O(n)의 시간이 필요하다.

따라서 합병 정렬의 시간 복잡도는 각 레벨에서 n의 작업을 수행하고, 그 레벨이 log n만큼 있으므로 전체 시간 복잡도는 O(n log n)이 된다.

 

 

성능이 일정하고 안정적이다 그리고 무엇보다 큰데이터에 유리하지만 메모리가 추가적으로 필요하다

 

---

 

✅ 퀵 정렬 (Quick Sort)

 

퀵 정렬 또한 분할 정복(Divide and Conquer) 전략을 사용하는 정렬 알고리즘이다. 퀵 정렬은 이름에서 볼 수 있듯이 평균적으로 매우 빠르며, 대규모 데이터셋에 적합한 성능을 보여준다. 퀵 정렬은 특정 요소 피벗(Pivot)를 기준으로 배열을 두 부분으로 나누고. 각 부분을 재귀적으로 정렬하는 방식으로 작동한다.

아래의 예시에서는 54를 피벗으로 설정하였다. 54를 기준으로 더 작은 원소는 왼쪽으로, 더 큰 원소는 오른쪽으로 분할한다. 구체적으로 설명을 하면 아래와 같다.

• left 포인터를 배열의 두 번째 요소(인덱스 1)에 위치시킨다.
• right 포인터를 배열의 마지막 요소에 위치시킨다.
• left 포인터를 오른쪽으로 이동시키면서 피벗보다 큰 같은 값을 찾는다.
• right 포인터를 왼쪽으로 이동시키면서 피벗보다 작은 값을 찾는다.
• left와 right 포인터가 가리키는 값이 서로 교차하기 전까지, 즉 left 포인터가 right 포인터보다 작거나 같은 동안, 두 포인터가 가리키는 값을 교환한다.
• left와 right 포인터가 교차하는 지점을 찾았다면, right 포인터가 가리키는 값과 피벗(첫 번째 요소)을 교환한다. 이렇게 하면 피벗은 배열의 중간 어딘가로 이동하며, 피벗 왼쪽의 모든 값은 피벗보다 작거나 같고, 피벗 오른쪽의 모든 값은 피벗보다 크게 된다.

 

 

퀵 정렬의 시간 복잡도

최선의 경우, 평균적인 경우: O(n log n)
퀵 정렬에서 최선의 경우는 피벗이 매번 정확히 배열을 두 동등한 부분으로 나누는 경우이다. 이 경우, 각 재귀 호출마다 처리해야 할 데이터의 양이 절반으로 줄어들게 된다. 이로 인해 시간 복잡도는 O(n log n)이 된다. 평균적인 경우, 피벗이 배열을 완벽하게 반반으로 나누지는 않지만, 대체로 균형 잡힌 분할을 유지한다.

최악의 경우: O(n2)
퀵 정렬의 최악의 경우는 피벗이 매번 최소 또는 최대 요소로 선택될 경우이다. 예를 들어, 이미 정렬된 배열에서 첫 번째 또는 마지막 요소를 피벗으로 선택하면, 한 쪽 분할은 0개의 요소를 가지고 다른 쪽 분할은 n−1개의 요소를 가지게 된다. 이 경우, 퀵 정렬은 단순히 각 요소를 제자리로 이동시키는 작업만 하게 되며, 각 단계에서 n−1,n−2,...,1의 비교를 수행해야 하므로, 시간 복잡도는 O(n2)가 된다.

 

분할정렬알고리즘으로써 피벗(Pivot)을 기준으로 좌우로 나누고, 재귀적으로 정렬

 

 

 

✅  실무에서 알고리즘 쓰는 실제 사례

실무 상황적용 알고리즘/개념

 

 

가장 인기 있는 제품 10개 추출	힙 정렬 (PriorityQueue)
최근 날짜 기준으로 데이터 정렬	Merge Sort / DB 정렬
중복 제거된 리스트 생성	HashSet
고객 방문 로그에서 이상 탐지	슬라이딩 윈도우 / 투 포인터
대용량 데이터 빠른 집계	해시맵 / 정렬 + 이진탐색
추천시스템에서 유사도 높은 순 정렬	정렬 + 필터링 알고리즘

 

 

✏️ 공부한점

• 실무에서는 대부분 라이브러리를 사용해 정렬이나 검색을 처리합니다.
• 하지만 데이터 양, 상황, 목적에 따라 어떤 알고리즘이 적합한지 판단해야 할 순간이 옵니다.

📌 예시:

Arrays.sort(arr); // 내부에서 Dual-Pivot QuickSort 사용

 

• QuickSort가 언제 느려지는지(최악 O(n²))를 모르면 데이터가 쏠린 구조에서 성능 문제가 생겨도 원인을 모름

 

 

✅ 퀵 정렬 (Quick Sort)

• **기준 요소(Pivot)**를 정해서, 기준보다 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 나눈 뒤 각각 재귀적으로 정렬합니다.
• 분할이 먼저, 정렬은 나중

✅ 합병 정렬 (Merge Sort)

• 배열을 반으로 나누고, 각 반쪽을 정렬한 후, **두 정렬된 배열을 병합(merge)**합니다.
• 병합이 핵심