선택정렬, 삽입정렬, 버블정렬, 쉘정렬 이해하기

ㅑ#선택정렬 #삽입정렬 #버블정렬 #쉘정렬 #개발자의도구들

​

AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다.

시간 복잡도에 따른 분류

이전글에서는 정렬문제에 대한 간단한소개, 안정정렬, 제자리 정렬에 대해 공부하였습니다.

​

이제 현 시대에 어떤 정렬 알고리즘이 존재하는지 함께 공부해봅시다. 정렬 알고리즘은 시간복잡도에 따라 나눌 수 있습니다. 이번 단락의 핵심은 각 알고리즘의 이름과 시간복잡도 및 구현방법을 이해하는 것입니다.(코드가 아닌 머리로 이해하세요!)

​

O(N²)

선택정렬

​

가장 작은 데이터를 0번자리와 자리바꿈하여 데이터를 정렬하는 방식입니다. 선택정렬이라는 이름에 걸맞게 가장 작은 데이터를 "선택"하여 교환한다는 의미로 기억하시면 좋습니다.

​

선택정렬의 가장 큰 특징은 index를 사용해야한다는 것입니다. 배열처럼 무작위로 접근가능한 자료구조와 어울리는 정렬이 되겠습니다. 중간의 가장 작은 데이터와, 현재 위치의 데이터를 변경해줘야 하기때문에 순차적인 접근이 아닌 무작위 접근이 가능한 index를 사용해야합니다.

0번 이후에 1번, 2번, 3번 ... 자리와 이후 가장 작은 데이터를 선택하여 교환하는 방식으로 정렬합니다. 항상 최소값을 찾아 줘야 하기 떄문에 총 N²시간이 소모될 수 밖에 없습니다.

​

또한 알고리즘의 자리바꿈 특성상, 크기가 같은 요소의 순서가 충분히 뒤바뀔 수 있는 불안정 정렬입니다. 그렇지만, 추가적인 데이터 소모는 없어 제자리정렬이 되겠습니다.

삽입정렬

삽입정렬을 들었을때 가장 먼저 떠올릴 것은 빈공간입니다. 이름에서 알 수 있듯이 삽입정렬은 빈공간에 삽입하는 형태로 구현된 알고리즘입니다.

​

그럼 여기서 빈공간은 어디인지 이해하는것이 중요한 문제가 되겠습니다. 삽입정렬은 모든 요소를 순회하는데 여기서 각 요소가 자신의 차례에 빈공간을 만듭니다. 그런 후 각 요소는 자신보다 앞에있는 위치의 요소와 계속해서 비교해나가며 자신의 자리를 찾아갑니다.

​

삽입정렬의 경우에는 이미 데이터가 정렬되어 있는 상태라면 O(N)의 시간복잡도를 가집니다. 알고리즘 비교 특성상 안정정렬이며 추가적인 메모리를 필요로 하지 않는 제자리 정렬이기도 합니다.

​

하지만, 평균/최악의 시간복잡도가 O(N²)이라 좋은 성능의 알고리즘으로 보기에는 어렵습니다.

버블정렬

버블정렬은 무조건 자신의 앞뒤로 비교합니다. 그래서 가장 큰 값인 경우 가장 오른쪽으로 갈 수 밖에 없게 구현됩니다.

​

버블정렬은 각 요소(n)개를 n번 앞뒤로 비교하는 알고리즘이기 때문에 O(N²)의 시간 복잡도(최소,평균,최악 모두)를 나타냅니다.

​

삽입정렬과 달리 버블정렬은 중간에 공간을 비울 수 없는 데이터의 경우에 사용하기 용이합니다.

쉘정렬

쉘정렬은 삽입정렬의 보완된 버전으로 초기 gap = k를 선정하고 k를 1로 줄여가며 새로운 리스트를 만듭니다.

​

새로운 리스트를 생성하는 이유는 초기 데이터가 비효율적으로 퍼져있는 것을 한번 걸러내기 위함입니다. 삽입정렬은 이미 정렬되어있는 경우 O(n)의 시간 복잡도를 가지기 때문에 좀 더 효율적인 정렬이 가능합니다.

​

평균 시간복잡도는 O(N^⅔)로 일반적인 삽입정렬보다 조금 빠른 속도를 보입니다.

​