[알고리즘] 7. 정렬 알고리즘 (1)
1. 선택 정렬(Selection Sort)
정렬(Sorting)
• 데이터를 일정한 규칙에 따라 재배열하는 과정
• 데이터 크기에 따라 정렬 방식이 달라짐
정렬 알고리즘
• 기본적인 정렬 방식 중 하나
• 비교 연산과 이동 연산으로 구성됨
• 데이터 크기가 클수록 이동 연산이 적은 방식이 효율적
• 내부 정렬(메모리 내 정렬)과 외부 정렬(보조기억장치 활용)이 있음
내부 정렬(Internal Sort)
• 모든 데이터를 메모리에 올려 빠르게 정렬
• 대용량 데이터 처리에는 부적합
• 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬 등
외부 정렬(External Sort)
• 대용량 데이터 정렬 가능
• 디스크 등 보조기억장치 활용으로 수행 속도가 느림
선택 정렬(Selection Sort)
• 정렬되지 않은 데이터에서 가장 작은 값을 찾아 앞쪽과 교환하는 방식
• 해당 위치에 맞는 데이터를 선택하여 위치 교환
2. 버블 정렬(Bubble Sort)
버블 정렬
• 인접한 두 데이터를 비교하여 큰 값을 뒤로 보내는 방식
• 1회전 수행 후 가장 큰 값이 맨 뒤로 이동
• 이후 정렬에서 제외되는 데이터가 증가하며 반복
최선의 경우
• 데이터가 이미 정렬된 상태
• 비교 횟수는 n(n-1)/2이지만 자리 교환이 없음
최악의 경우
• 데이터가 역순으로 정렬된 상태
• 비교 및 교환 횟수가 최대가 되어 수행 시간이 길어짐
• 평균 시간 복잡도: O(n^2)
3. 삽입 정렬(Insertion Sort)
삽입 정렬
• 정렬되지 않은 데이터를 적절한 위치에 삽입하는 방식
• 앞쪽 데이터들과 비교하여 자신의 위치를 찾아 정렬
• 두 번째 데이터부터 시작하여 진행
효율성
• 알고리즘이 단순하며, 데이터가 적을 때 유용
• 데이터가 많거나 이동이 많을 경우 비효율적
최선의 경우
• 데이터가 거의 정렬된 상태
• 비교 횟수 n-1로, 시간 복잡도 O(n)
최악의 경우
• 데이터가 역순으로 정렬된 상태
• 모든 단계에서 데이터를 이동해야 함
• 시간 복잡도 O(n^2)
이 내용은 휴넷사회복지평생교육원의 알고리즘 강의를 듣고 정리한 것입니다.