안정 정렬은 데이터의 순서를 유지하면서 정렬하는 알고리즘을 의미합니다. 예를 들어, 중복된 값이 있을 때, 원래의 입력 순서가 유지되는 것이죠. 이러한 특성 덕분에 안정 정렬은 데이터의 일관성을 보장하는 데 유용합니다.
안정 정렬의 정의
안정 정렬(Stable Sort)은 동일한 키 값을 가진 데이터의 순서가 정렬 후에도 유지되는 정렬 방법입니다. 예를 들어, 카드 정렬을 생각해보면, 같은 숫자의 카드가 여러 장 있을 때, 원래의 순서가 유지되는 것이 안정 정렬입니다. 반면, 불안정 정렬은 이러한 순서가 보장되지 않습니다.
안정 정렬과 불안정 정렬의 차이
안정 정렬과 불안정 정렬의 가장 큰 차이는 중복된 값의 순서 유지 여부입니다. 안정 정렬은 중복된 값이 있을 때, 입력 순서와 동일하게 정렬됩니다. 반면, 불안정 정렬은 중복된 값의 순서가 바뀔 수 있습니다. 예를 들어, 서울, 대전, 대구, 부산의 데이터를 시간순으로 정렬할 때, 안정 정렬은 원래의 순서를 유지합니다.
안정 정렬 알고리즘의 종류
안정 정렬 알고리즘에는 여러 가지가 있습니다. 대표적으로는 다음과 같은 알고리즘이 있습니다:
버블 정렬(Bubble Sort): 인접한 두 요소를 비교하여 정렬하는 방식으로, 안정 정렬입니다.
삽입 정렬(Insertion Sort): 데이터를 하나씩 정렬된 부분에 삽입하는 방식으로, 안정 정렬입니다.
병합 정렬(Merge Sort): 데이터를 반으로 나누어 정렬한 후 합치는 방식으로, 안정 정렬입니다.
반면, 퀵 정렬(Quick Sort)은 불안정 정렬로, 중복된 값의 순서가 보장되지 않습니다.
안정 정렬의 예시
안정 정렬의 예시로는 카드 정렬을 들 수 있습니다. 카드의 숫자가 같을 때, 원래의 순서가 유지되는 것을 보여줍니다. 예를 들어, 2, 5, 7의 카드가 있을 때, 이 카드들을 정렬하면 원래의 순서가 유지됩니다.
프로그래밍 언어별 안정 정렬 지원
프로그래밍 언어에 따라 안정 정렬을 지원하는 경우와 지원하지 않는 경우가 있습니다. C++과 Python은 안정 정렬을 지원하지만, Java와 JavaScript, Swift는 기본적으로 안정 정렬을 지원하지 않습니다. 이러한 경우, decorate-sort-undecorate 패턴을 사용하여 안정 정렬을 구현할 수 있습니다.
decorate-sort-undecorate 패턴
이 패턴은 데이터를 정렬하기 전에 추가 정보를 붙이고, 정렬 후에 원래의 데이터로 되돌리는 방식입니다. 예를 들어, 학생들의 성적을 정렬하면서, 성적이 동일한 경우 이름을 기준으로 사전순 정렬하는 상황을 가정해보겠습니다.
import java.util.*;
class Product {
String name;
int price;
Product(String name, int price) {
this.name = name;
this.price = price;
}
@Override
public String toString() {
return name + " (₩" + price + ")";
}
}
public class DecorateSortUndecorateWithMap {
public static void main(String[] args) {
List<Product> products = Arrays.asList(
new Product("Laptop", 1200),
new Product("Smartphone", 800),
new Product("Tablet", 800),
new Product("Smartwatch", 200),
new Product("Headphones", 200)
);
// Decorate: Map을 사용해 product와 index를 매핑
Map<Product, Integer> productMap = new HashMap<>();
for (int i = 0; i < products.size(); i++) {
productMap.put(products.get(i), i);
}
// Sort: 가격을 기준으로 정렬, 가격이 동일하면 인덱스를 기준으로 안정성 유지
List<Product> sortedProducts = new ArrayList<>(productMap.keySet());
sortedProducts.sort(Comparator
.comparing((Product p) -> p.price)
.thenComparing(p -> productMap.get(p)));
// 결과 출력
System.out.println("정렬된 상품들: " + sortedProducts);
}
}
설명
- Decorate: IndexedStudent 클래스를 사용하여 원래의 Student 객체에 index를 추가해 안정성을 보장합니다.
- Sort: 성적을 기준으로 정렬하되, 성적이 동일할 경우 원래의 인덱스를 기준으로 정렬하여 안정성을 유지합니다.
- Undecorate: 정렬이 끝난 후, 원래의 인덱스를 제거하고 정렬된 Student 객체들만 남깁니다.
정렬된 상품들: [Smartwatch (₩200), Headphones (₩200), Smartphone (₩800), Tablet (₩800), Laptop (₩1200)]안정 정렬의 활용 사례
안정 정렬은 데이터베이스에서 중복된 데이터를 정렬할 때 유용합니다. 예를 들어, 고객 정보를 정렬할 때, 이름이 같은 고객의 순서를 유지하는 것이 중요할 수 있습니다. 이러한 경우 안정 정렬을 사용하면 데이터의 일관성을 유지할 수 있습니다.
정리 및 참고 자료
안정 정렬은 데이터의 순서를 유지하면서 정렬하는 데 매우 유용한 알고리즘입니다. 다양한 프로그래밍 언어에서 안정 정렬을 지원하며, 이를 통해 데이터의 일관성을 보장할 수 있습니다.
[1] 홍러닝 - 안정 정렬 vs 불안정 정렬 - 홍러닝 (https://hongl.tistory.com/9)
[2] velog - 안정 정렬 VS 불안정 정렬 - 파이썬 알고리즘 인터뷰
[3] velog - [크래프톤 정글] 10일차 : 안정 정렬(Stable Sort) & In-place ... (https://velog.io/@gusdh2/%ED%81%AC%EB%9E%98%ED%94%84%ED%86%A4-%EC%A0%95%EA%B8%80-10%EC%9D%BC%EC%B0%A8-%EC%95%88%EC%A0%95-%EC%A0%95%EB%A0%ACStable-Sort-In-place-Algorithm)
[4] 티스토리 - [알고리즘] 안정 정렬 (Stable Sort) - riverblue - 티스토리 (https://riverblue.tistory.com/39)
