삽입 정렬, 퀵 정렬

1. 삽입 정렬

• 정의)
• 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입하여 정렬시키는 방식

• 과정)
• k번째 원소를 앞의 원소들과 역순으로 비교하며,
• 처음으로 등장하는 본인보다 크지 않은(작거나 같은) 원소 뒤에 위치시킴
• 위 알고리즘을 배열에 아무 변화가 없을 때까지 반복함

• 예시) 6 5 3 8
• i=1, j=0 → key=5 → 5 6 3 8
• i=2, j=1 → key=3 → 3 5 6 8
• i=3, j=2 → key=8 → 3 5 6 8

• 특징)
• 매번 반복할 때마다 앞의 배열이 정렬됨
• 시간 복잡도 : 최선 O(N) , 평균 O(N^2) , 최악 O(N^2)
• 적절한 삽입 위치를 정렬된 부분에서 탐색하는 부분에서 이진 탐색 등과 같은 탐색 알고리즘을 사용해 시간 복잡도 줄일 수 있음
• 그럼에도 시간 복잡도가 좋을 수 없는 이유는, 찾는 건 빨리 해서 O(N)을 O(logN)으로 줄였다고 하더라도 삽입할 뒷 부분의 데이터들에 대해 shift 연산을 수행해야 하는데 이 shift 연산이 시간이 많이 걸리기 때문임

• 코드)

2. 퀵 정렬

• 정의) 기준값(pivot)을 선정해 해당값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 방식
• 매 단계마다 피벗이라고 이름 붙은 원소 하나를 제자리로 보내는 작업을 반복하는, 재귀적으로 구현되는 정렬
• 여기서 제자리로 보낸다는 의미는 피벗의 왼쪽은 피벗보다 작은 원소가, 오른쪽은 큰 원소가 오게 하는 것

• 과정 간략하게)
• 임의의 index를 피벗(pivot)으로 잡음
• 피벗 좌측에는 피벗보다 작은 수, 우측에는 큰 수가 오게끔 배치함
• 피벗을 제외한 피벗의 좌측과 우측 두 개의 리스트에 대해서 위 과정을 재귀적으로 반복함 (분할정복)

• 예시)

• 과정 상세히)
1. 데이터를 분할하는 피벗을 설정 (예시의 경우 가장 오른쪽 끝을 피벗으로 설정)
2. 피벗을 기준으로 아래 과정을 거쳐 2개의 집합으로 분리함 (포인터로 잘못된 위치에 있는 값 찾아나감)
1. start가 가리키는 데이터가 피벗이 가리키는 데이터보다 작으면 start를 오른쪽으로 한 칸 이동
(피벗보다 큰 애가 나오면 멈춤. 그 자리가 아니라서 나중에 swap 해주기 위해)
2. end가 가리키는 데이터가 피벗이 가리키는 데이터보다 크면 end를 왼쪽으로 한 칸 이동
(피벗보다 작은 애가 나오면 멈춤. 그 자리가 아니라서 나중에 swap 해주기 위해)
3. start, end가 가리키는 데이터를 swap 하고 start는 오른쪽, end는 왼쪽으로 한 칸씩 이동
4. end가 start보다 작아질 때까지 a~c를 반복
5. pivot과 end를 swap
3. 분리 집합에서 각각 다시 pivot을 선정
4. 분리 집합이 1개 이하가 될 때까지 과정 1~3을 반복

• 특징)
• 시간 복잡도 : 최선 O(NlogN) , 평균 O(NlogN) , 최악 O(N^2)
• 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미침
• 피벗으로 계속 최대값이거나 최소값을 선택한다면, 좌우측으로 넘길 때 전부다 판단해야 하기 때문에 최악이 O(N^2)임
• 예시) 1 2 3 4 5 100 에서 100이 피벗이라면,
• end는 5로 그대로고 start가 1부터 5까지 다훑고 올라와서 start와 end가 5에서 만남
• 결국 100은 다시 5 뒷자리에 들어가 원래 상태 그대로 유지임
• 피벗으로 중간 정도 크기의 숫자 택하는 게 중요함. 좌우측으로 반반 분할정복이 가능해짐(up down 게임처럼). 물론 중간 정도 크기의 숫자가 어디에 있는지 알 방법은 없기에 운에 따름.
• pivot이 매번 완벽하게 중앙에 위치해서 리스트를 균등하게 둘로 쪼갠다면 단계의 개수가 logN이 될 테고, 각 단계마다 pivot을 제자리로 보내는 데에 O(N)이 필요해서 총 O(NlogN)이 나옴
• pivot이 매번 어느 정도로만 잘 자리잡는다면 시간복잡도는 여전히 O(NlogN)임. 심지어 매번 리스트를 1:99의 배율로 쪼개더라도 마찬가지임
• STL을 못 쓰고 직접 정렬을 구현해야 하는 상황에서 다른 정렬을 선택할 수 있다면 퀵 소트는 절대 쓰지 말고, 머지 소트나 힙 소트 같은 다른 O(NlogN)인 정렬을 쓸 것
• 머지 소트가 퀵 소트보다 느린 건 맞지만 어차피 O(NlogN)에 돌아가니 충분히 빠름. 이에 반해, 퀵 소트는 최악의 경우 O(N^2)이라 쓸 필요가 없기 때문임
• 그럼에도, 대부분의 라이브러리에선 퀵 소트를 씀. 라이브러리에선 피벗을 랜덤하게 택하기도 하고, 피벗 후보를 3개 정해서 그 3개 중 중앙값을 피벗으로 두기도 한는 등 다양한 처리를 함.
• 또, 최악의 경우에도 O(NlogN)을 보장하기 위해서 일정 깊이 이상 들어가면 퀵 소트 대신 힙 소트로 정렬함. 이러한 정렬을 Introspective sort라 부름.

• 장점)
• 추가적인 공간이 필요하지 않음 (추가적인 공간을 사용하지 않는 정렬 == In-Place Sort)
• 배열 안에서의 자리 바꿈만으로 처리 되기 때문에 cache hit rate 가 높아서 속도가 빠름

• 단점)
• 리스트가 오름차순이거나 내림차순일 때는 시간복잡도로 O(N^2)이 나옴

• 코드)

💡

전체 코드와 추천 문제는 아래에서 확인하실 수 있습니다.

GitHub - ChooSeoyeon/algorithm: 알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다.

알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다. - GitHub - ChooSeoyeon/algorithm: 알고리즘 학습 시 사용한 코드를 모아뒀습니다. 전체 학습 과정에 대한 내용은 아래 링크에서 확인할 수 있습니다.

https://github.com/ChooSeoyeon/algorithm/tree/main