정렬

정렬 (Sorting)

정의 : 데이터를 일정한 순서나 규칙에 따라 재배열하는 것을 의미하며, 특정 기준에 따라 데이터를 오름차순(ascending) 또는 내림차순(descending)으로 정리하는 알고리즘

선택 정렬 (Selection Sort)

선택 정렬은 배열에서 최소값을 찾아 맨 앞의 원소와 교환하는 과정을 반복하여 정렬하는 알고리즘입니다.

핵심 요소

배열을 순회하며 최소값을 찾아 맨 앞부터 채워나가는 방식

•

두 개의 서브 리스트로 나누어 정렬 진행

•

제자리 정렬(in-place sorting) 알고리즘

시간 복잡도

주요 특징

•

장점

•

단점

예시 코드

직접 구현

선택정렬

버블 정렬 (Bubble Sort)

배열의 인접한 두 원소를 비교하여 순서가 맞지 않으면 서로 교환하면서 정렬하는 알고리즘입니다. 가장 큰 원소가 버블처럼 떠올라 맨 뒤로 이동하는 모습과 유사하여 버블 정렬이라고 합니다.

핵심 요소

•

인접한 두 원소를 비교하여 교환

•

한 번의 순회마다 가장 큰 원소가 맨 뒤로 이동

•

n-1번의 순회로 전체 정렬 완료

시간 복잡도

주요 특징

•

구현이 매우 간단함

•

안정 정렬(Stable Sort)

•

제자리 정렬(In-place Sort)

•

비효율적인 시간 복잡도로 인해 실무에서는 잘 사용되지 않음

예시 코드

버블정렬

삽입 정렬 (Insertion Sort)

이미 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬 알고리즘입니다. 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입합니다.

네이버 블로그 | ALOHA정보처리기사 실기 for 직장인 - 순서도_삽입정렬

정보처리기사 실기 for 직장인 - 순서도_삽입정렬

1. 순서도 - 삽입정렬 [문제] 아래의 <순서도> 는 10개의 자연수가 배열 A(6)에 정렬되지 않은 상태...

https://blog.naver.com/h850415/221492097636?trackingCode=blog_bloghome_searchlist

핵심 요소

•

정렬된 부분과 정렬되지 않은 부분으로 나누어 진행

•

각 원소를 적절한 위치에 삽입

•

in-place 알고리즘으로 추가 메모리가 거의 필요하지 않음

시간 복잡도

주요 특징

•

안정 정렬(Stable Sort)

삽입정렬

병합 정렬 (Merge Sort)

분할 정복(Divide and Conquer) 알고리즘을 기반으로 하는 정렬 방식으로, 리스트를 절반씩 나누어 정렬한 후 다시 합치면서 전체를 정렬하는 방법

핵심 요소

•

분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할

•

정복(Conquer): 부분 배열을 정렬

•

결합(Combine): 정렬된 부분 배열들을 하나의 배열로 병합

시간 복잡도

주요 특징

•

안정 정렬(Stable Sort): 동일한 값에 대해 원래의 순서가 유지됨

•

비제자리 정렬(Not-in-place Sort): 추가적인 메모리 공간이 필요

•

분할 정복 방식: 문제를 작은 2개의 문제로 분리하고 해결한 후, 결과를 모아서 원래의 문제를 해결

병합 정렬

퀵 정렬 (Quick Sort)

분할 정복(divide and conquer) 방식을 사용하는 정렬 알고리즘으로, 피벗(pivot)을 기준으로 배열을 분할하고 재귀적으로 정렬하는 방식입니다.

핵심 요소

시간 복잡도

주요 특징

•

불안정 정렬: 동일한 값의 원소들의 상대적 위치가 변경될 수 있음

•

제자리 정렬: 추가적인 메모리 공간이 거의 필요하지 않음

•

다른 정렬 알고리즘에 비해 일반적으로 빠른 성능을 보임

예시 코드 (Java)

퀵 정렬

힙 정렬 (Heap Sort)

힙 정렬은 완전 이진 트리를 기반으로 하는 힙(Heap) 자료구조를 이용하여 데이터를 정렬하는 알고리즘입니다. 최대 힙 또는 최소 힙을 구성하여 순차적으로 요소를 꺼내어 정렬을 수행합니다.

핵심 요소

•

힙(Heap) 자료구조 활용

•

완전 이진 트리 기반

•

불안정 정렬

•

제자리 정렬(in-place sorting)

시간 복잡도

주요 특징

•

항상 O(nlog n)의 시간 복잡도를 보장

•

추가 메모리 공간이 거의 필요하지 않음

•

대규모 데이터 정렬에 효율적

•

불안정 정렬이므로 동일한 값의 순서가 보장되지 않음

힙 정렬

핵심 요소

요소	설명
시간 복잡도	정렬 알고리즘의 수행 시간을 나타내는 척도
공간 복잡도	정렬 수행 시 추가로 필요한 메모리 공간
안정성	동일한 값에 대해 원래의 순서가 유지되는지 여부
데이터 크기	정렬할 데이터의 양에 따른 알고리즘 선택

정렬 알고리즘 비교 표

정렬 알고리즘	개념	시간 복잡도 (최악)	시간 복잡도 (평균)	시간 복잡도 (최선)	특징
버블 정렬 (Bubble Sort)	인접한 원소를 비교하여 교환	O(𝑛²)	O(𝑛²)	O(𝑛)	단순하지만 비효율적
선택 정렬 (Selection Sort)	가장 작은(또는 큰) 원소 선택 후 정렬	O(𝑛²)	O(𝑛²)	O(𝑛²)	데이터 이동 횟수 적음
삽입 정렬 (Insertion Sort)	정렬된 부분에 원소 삽입	O(𝑛²)	O(𝑛²)	O(𝑛)	작은 데이터셋에서 우수
병합 정렬 (Merge Sort)	리스트를 분할 후 병합 (분할 정복)	O(𝑛 log 𝑛)	O(𝑛 log 𝑛)	O(𝑛 log 𝑛)	안정 정렬, 추가 메모리 필요
퀵 정렬 (Quick Sort)	피벗을 기준으로 분할 후 정렬 (분할 정복)	O(𝑛²)	O(𝑛 log 𝑛)	O(𝑛 log 𝑛)	평균적으로 가장 빠름
힙 정렬 (Heap Sort)	힙(완전이진트리) 자료구조 활용	O(𝑛 log 𝑛)	O(𝑛 log 𝑛)	O(𝑛 log 𝑛)	추가 메모리 사용 없음