정렬 알고리즘 개념

베하!

안녕하세요 여러분, 일단고입니다.

8월 중반이네요. 다가올 가을이 기대됩니다.

오늘은 정렬 알고리즘의 종류엔 무엇이 있고 어떤 장단점이 있는지 알아봅시다!

 

정렬 알고리즘

정렬 알고리즘은 컴퓨터 공학에서 중요시되는 문제 중 하나로, 어떤 데이터셋이 주어졌을 때 이를 정해진 순서대로 나열하여 재배치하는 방법을 말합니다.

선택 정렬, 삽입 정렬, 버블 정렬, 병합 정렬, 힙 정렬, 퀵 정렬, 기수 정렬이 있습니다.

어떤 알고리즘이 가장 좋다고는 말할 수 없습니다.

상황에 따라서 적절한 알고리즘을 사용하는 것이 가장 중요합니다.

 

알고리즘 선택 시 고려해야 할 사항은 다음과 같습니다.

1. 정렬할 데이터의 양
2. 데이터와 메모리
3. 기존의 정렬된 정도
4. 필요한 추가 메모리 양
5. 안정성

그럼 정렬 알고리즘을 하나하나 알아봅시다!

 

1. 선택 정렬 (Selection Sort)

선택된 값과 나머지 데이터중에 비교하여 알맞은 자리를 찾는 알고리즘입니다.

사진 출처 : https://wonjayk.tistory.com/217

• 주어진 배열 중에서 최솟값을 찾는다.
• 찾은 최솟값을 배열의 제일 앞에 위치한 값과 교체한다.
• 교체한 최솟값을 제외하고 위 과정을 반복한다.

선택 정렬의 장점은 자료 이동 횟수가 미리 결정된다는 점이고, 단점은 동일한 값이 여러 개 존재할 경우에 상대적인 위치가 변경될 수 있어서 안정성이 떨어진다는 점입니다.

 

2. 삽입 정렬 (Insertion Sort)

데이터 집합을 순회하면서 정렬이 필요한 요소롤 뽑아내어 이를 다시 적당한곳으로 삽입하는 알고리즘입니다.

사진 출처 : https://wonjayk.tistory.com/217

• 처음 key 값은 두번째 자료부터 시작
• key값 앞에 위치한 값과 비교하며 정렬된 부분의 어느 위치에 삽입되어야 하는가를 판단
• 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬
• 마지막 값까지 위 과정을 반복

삽입 정렬의 성능은 버블 정렬보다 좋습니다. 레코드의 수가 적은 경우에 복잡한 정렬 방법보다 효율적으로 동작하며, 안정적인 정렬 방법이라고 할 수 있습니다. 반대로 레코드들의 이동이 비교적 많기 때문에 레코드의 수가 많고 레코드 크기가 큰 경우엔 적합하지 않은 알고리즘입니다.

 

3. 버블 정렬 (Bubble Sort)

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘입니다.

사진 출처 : https://wonjayk.tistory.com/217

• 인접한 2개의 레코드 비교하여, 작은 숫자를 앞으로 위치하도록 정렬
• 가장 큰 수가 오른쪽 끝으로 위치하게 됨 → 해당 위치를 제외하고 스캔을 반복함
• (배열 크기 -1) 회전까지 위 과정을 반복하여 정렬을 끝냄

구현이 간단하다는 장점이 있지만 비효율적인 정렬이기 때문에 속도가 느리다는 단점이 있습니다.

 

4. 병합 정렬 (Merge Sort)

하나의 배열을 두 개의 균등한 크기로 분할하고 분할된 부분 배열을 정렬한 다음 두개의 정렬된 부분 배열을 합하여 전체를 정렬하는 알고리즘입니다.

사진 출처 : https://wonjayk.tistory.com/217

• 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할
• 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여(재귀적으로) 다시 분할 정복 방법을 적용
• 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병

최적, 최악, 평균 속도를 가리지 않고 항상 일정한 속도로 동작합니다. 다만 제자리 정렬이 아니기 때문에 합병 정렬을 위한 임시 배열이 필요하다는 단점이 있습니다.

 

5. 힙 정렬 (Heap Sort)

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조로 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아낼 수 있습니다.

사진 출처 : https://wonjayk.tistory.com/217

• 정렬해야 할 n개의 요소들로 최대 힙또는 최소 힙(완전 이진 트리 형태)을 만듬
• 한 번에 하나씩 요소를(최대 힙이면 최댓값을, 최소 힙이면 최솟값을) 힙에서 꺼내서 배열의 뒤부터 저장

힙 정렬에 사용되는 시간이 짧습니다. 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때 유용합니다.

 

6. 퀵 정렬 (Quick Sort)

기준이 되는 원소를 기준으로 하여 기준 원소보다 작거나 같음을 비교하여 정렬하는 알고리즘입니다.

사진 출처 : https://www.podo-dev.com/blogs/75

• 데이터 집합내에 임의의 기준(pivot)값을 정하고 해당 피벗으로 집합을 기준으로 두개의 부분 집합으로 나눔
• 왼쪽에는 피벗값보다 작은값들만, 오른쪽에는 큰값들만 넣음
• 더 이상 쪼갤 부분 집합이 없을 때까지 각각의 부분 집합에 대해 피벗/쪼개기 재귀적으로 적용
• 그 결과 정렬된 결과를 가질 수 있음

퀵 정렬은 다른 정렬 알고리즘에 비해 빠르게 동작 가능하고 제자리 정렬이기 때문에 추가적인 메모리가 필요없는 장점이 있습니다. 하지만 불안정한 정렬 알고리즘이며 최악의 경우 스택 오버플로우(재귀 호출 스택의 한계를 초과)가 발생할 수 있습니다.

 

7. 기수 정렬 (Radix Sort)

낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘입니다.

사진 출처 : https://lktprogrammer.tistory.com/48

• 0~9 까지의 Bucket을 준비
• 모든 데이터에 대하여 가장 낮은 자리수(1의 자리)에 해당하는 Bucket에 차례대로 데이터를 둠
• 0부터 차례대로 버킷에서 데이터를 다시 가져옴
• 다음으로 높은 자리수(10의 자리)에 해당하는 Bucket에 차례대로 데이터를 둠
• 0부터 차례대로 버킷에서 데이터를 다시 가져옴
• 가장 높은 자리수까지 반복하여 정렬된 결과를 가짐

기수 정렬은 비교연산을 하지 않아 빠르지만, 또 다른 메모리 공간을 필요하다는게 단점입니다.

 

---

이렇게 7가지 정렬 알고리즘에 대해 알아봤습니다.

재밌죠?

다음 시간에 다시 만나요!