기본 알고리즘 (정렬)

1. 도입 (왜 배워야 하는가)

정렬 알고리즘은 데이터를 특정 기준에 따라 순서대로 배치하는 방법을 제공합니다. 예를 들어, 쇼핑몰에서 상품을 가격순으로 정렬하거나, 학생 성적을 높은 순으로 나열할 때 사용됩니다. 이러한 정렬 작업은 데이터 분석, 검색 효율성 향상, 사용자 경험 개선 등 다양한 실무 상황에서 필수적입니다.

정렬을 제대로 이해하지 못하면, 비효율적인 코드 작성으로 인해 프로그램의 성능이 저하될 수 있습니다. 간단한 데이터라도 정렬이 필요할 때 비효율적인 방법을 사용하면 사용자에게 불편을 줄 수 있습니다. 따라서 정렬 알고리즘을 배우는 것은 개발자로서 중요한 기본기 중 하나입니다.

2. 핵심 개념 설명

정렬 알고리즘은 여러가지가 있으며, 각각의 알고리즘은 특정 상황에서 더 효율적일 수 있습니다. 여기서는 대표적인 정렬 알고리즘인 버블 정렬(Bubble Sort)과 선택 정렬(Selection Sort)을 소개하겠습니다.

버블 정렬 (Bubble Sort)

• 정의: 인접한 두 요소를 비교하여 정렬하는 방법으로, 가장 큰 값을 맨 뒤로 보내는 방식입니다.
• 비유: 물속에서 가장 가벼운 물체가 위로 떠오르듯, 가장 큰 값이 차례로 맨 뒤로 이동합니다.

선택 정렬 (Selection Sort)

• 정의: 주어진 데이터에서 가장 작은 값을 찾아 맨 앞에 위치시키고, 나머지 데이터에 대해 반복하는 방법입니다.
• 비유: 마치 수업 시간에 선생님이 학생들을 키 순서대로 세우는 것을 생각해보세요. 가장 작은 학생을 찾아서 맨 앞에 세우고, 그 다음으로 작은 학생을 찾아서 그 뒤에 세우는 방식입니다.

정렬 알고리즘	시간 복잡도 (최악)	공간 복잡도	안정성
버블 정렬	O(n^2)	O(1)	안정적
선택 정렬	O(n^2)	O(1)	비안정적

3. 기본 코드 예제

버블 정렬 코드

void bubbleSort(List<int> arr) {
  int n = arr.length;
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // 두 값 교환
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

void main() {
  List<int> numbers = [64, 34, 25, 12, 22, 11, 90];
  bubbleSort(numbers);
  print(numbers); // [11, 12, 22, 25, 34, 64, 90] 
}

실행 결과

[11, 12, 22, 25, 34, 64, 90]

코드 동작 설명

1. bubbleSort 함수 정의: 주어진 리스트를 정렬하는 함수입니다.
2. n 변수에 배열의 길이를 저장합니다.
3. 첫 번째 반복문은 전체 배열을 순회합니다.
4. 두 번째 반복문은 인접한 두 요소를 비교합니다.
5. if 조건문으로 두 요소의 크기를 비교하여 필요시 교환합니다.
6. 반복이 끝나면 정렬된 배열을 출력합니다.

4. 실전 활용 예제

쇼핑몰의 장바구니 구현

쇼핑몰에서 장바구니에 담긴 상품을 가격순으로 정렬하는 경우를 생각해보겠습니다.

class Product {
  String name;
  double price;
  
  Product(this.name, this.price);
}

void sortProductsByPrice(List<Product> products) {
  products.sort((a, b) => a.price.compareTo(b.price));
}

void main() {
  List<Product> cart = [
    Product('상품 A', 30.0),
    Product('상품 B', 20.0),
    Product('상품 C', 50.0),
  ];
  
  sortProductsByPrice(cart);
  
  for (var product in cart) {
    print('${product.name}: ${product.price}');
  }
}

실행 결과

상품 B: 20.0
상품 A: 30.0
상품 C: 50.0

상황 설명

쇼핑몰에서 사용자가 장바구니에 상품을 담고, 가격순으로 정렬하여 보여주면 사용자가 더 쉽게 상품을 비교하고 결정할 수 있습니다.

5. 흔한 실수와 주의사항

실수 1: 인덱스 범위 초과

잘못된 코드:

for (int j = 0; j <= n - i - 1; j++) { // <=를 사용

올바른 코드:

for (int j = 0; j < n - i - 1; j++) { // <로 수정

설명: <=를 사용하면 배열의 범위를 초과하여 오류가 발생할 수 있습니다.

실수 2: 교환 로직 오류

잘못된 코드:

if (arr[j] < arr[j + 1]) { // 부등호 방향이 잘못됨

올바른 코드:

if (arr[j] > arr[j + 1]) { // 올바른 비교

설명: 정렬 방향이 잘못되면 오히려 역정렬이 될 수 있습니다.

6. 정리

7. 정렬 알고리즘은 데이터 처리의 기본 중 하나로, 실무에서 매우 중요하다.
8. 버블 정렬과 선택 정렬은 기초적인 정렬 알고리즘으로, 각기 다른 특징을 가지고 있다.
9. 실전에서는 상품 가격 정렬, 성적 정렬 등 다양한 분야에서 활용된다.
10. 다음에 학습하면 좋은 주제: 고급 정렬 알고리즘 (퀵 정렬, 병합 정렬), 정렬과 검색 알고리즘의 관계.