정렬 알고리즘

2026.02.04 (수)
정렬 알고리즘
선택 정렬
버블 정렬

---

📶 정렬 알고리즘

정렬(Sorting)은 흩어져 있는 데이터를 정해진 기준에 따라 차례대로 나열하는 것이다. 예를 들어, [3, 1, 4, 2]라는 무작위 리스트를 1, 2, 3, 4 또는 4, 3, 2, 1로 만드는 과정이다.

어디에 사용되는가?

일상에서 사용되는 거의 모든 디지털 서비스에는 정렬 알고리즘을 사용하고 있다.
예를 들어서 쇼핑몰, SNS, 금융/은행, 내비게이션 등

낮은 가격순, 리뷰많은 순 최신 등록순 필터링
타임라인에 게시물을 최신순으로 나열하거나 좋아요가 많은 인기순으로 노출
거래 내역을 날짜별로 정리하거나 계좌 잔액 기준 정렬 등

---

🫧 버블 정렬

큰 원소가 뒤로 거품처럼 밀려 올라가는 모습에서 유래되었다. 인접한 두 원소를 비교하여 조건에 맞지 않으면 자리를 바꾸는 방식!

동작방식

1. 첫번째 원소와 두 번째 원소를 비교한다.
2. 앞의 원소가 더 크면 자리를 바꾼다.
3. 위의 행동을 마지막 원소까지 반복하면 가장 큰 원소가 맨 뒤로 고정된다.
4. 과정된 원소를 제외하고 다시 반복한다.

void bubbleSort(List<int> list) {
  int n = list.length;
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (list[j] > list[j + 1]) {
        // 데이터 위치 교환
        int temp = list[j];
        list[j] = list[j + 1];
        list[j + 1] = temp;
      }
    }
  }
}

---

📌 선택 정렬

전체 원소 중 최솟값을 찾아 맨 앞에 있는 원소와 교체하는 방식이다

동작 방식

1. 주어진 리스트에서 최솟값을 찾는다.
2. 그 값을 맨 앞에 있는 값과 교체한다.
3. 맨 앞을 제외한 나머지 리스트에서 다시 최솟값을 찾아 두 번째 위치와 교체한다.
4. 이 과정을 리스트의 끝까지 반복한다

void selectionSort(List<int> list) {
  int n = list.length;
  for (int i = 0; i < n - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < n; j++) {
      if (list[j] < list[minIndex]) {
        minIndex = j;
      }
    }
    // 최솟값을 현재 위치로 교환
    int temp = list[minIndex];
    list[minIndex] = list[i];
    list[i] = temp;
  }
}

---

🔖 삽입 정렬

두번째 원소부터 시작하여 그 앞의 정렬된 부분과 비교해서 자신의 위치를 찾아 삽입하는 방식이다. 손 안의 카드를 정렬하는 방식과 유사하다

작동 방식

1. 두 번째 원소를 'Key'로 잡고 이전 원소들과 비교한다.
   2.Key가 이전 원소보다 작으면 이전 원소를 뒤로 밀어낸다
2. /Key가 들어갈 적절한 위치를 찾으면 그 자리에 삽입
3. 마지막 원소까지 반복

void insertionSort(List<int> list) {
  int n = list.length;
  for (int i = 1; i < n; i++) {
    int key = list[i];
    int j = i - 1;
    
    // key보다 큰 원소들을 오른쪽으로 한 칸씩 이동
    while (j >= 0 && list[j] > key) {
      list[j + 1] = list[j];
      j--;
    }
    list[j + 1] = key;
  }
}

---

알고리즘 비교 및 사용 이유

알고리즘	시간 복잡도	장점	단점
버블 정렬	$O(n^2)$	코드가 매우 단순함	교환 횟수가 많아 가장 느림
선택 정렬	$O(n^2)$	교환 횟수 적음	데이터 상태와 상관없이 항상 일정한 시간 소요
삽입 정렬	$O(n^2)$	이미 정렬된 상태라면 매우 빠름	데이터가 많을수록 성능 급격 저하

---