quick sort (+ til에 대한 주저리...)

 

주저리 먼저😋

일단 지금 진행중인 킹갓엠페러마제스티골져스 💗스터디💗 정말 당신들 없었으면 어쩔뻔했어.. 다같이 으쌰으쌰 해서 뭐든 척척해내는 이 스터디 진짜 최고야........... 

아무튼 5월부터(!!!) 다같이 노션에 정리한 til이 꽤 쌓여서 복습이 필요하다는 결론이 나왔고, 그냥 슥 읽으면 뇌가 지식을 거부할 것이므로 결국 티스토리에 한번 다시 정리하기로 결심😎 #가보자고

 

Quick sort 📊

• 분할정복 알고리즘 중 하나
• 평균적으로 매우 빠른 수행 속도를 가짐 O(N*logN)
• 하지만 최악의 경우 O(n^2)가 될 수도 있으므로 피벗(pivot) 선택에 신중해야 함
  → List를 정렬 한 다음에 딱 가운데 값을 선택하면 좋겠지만.. 그러면 굳이 퀵정렬을 쓸 필요가....😰
  → List의 길이가 3 이상인 경우, 임의로 값을 3개 고른 다음에 그 중앙값을 피벗으로 설정하면 좋음

 

✅ 퀵 정렬의 큰 흐름

이미지 출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

1. 리스트에서 피벗을 설정
2. 피벗을 기준으로 리스트를 2개로 분리
    2-1. 리스트에서 피벗을 설정
    2-2. 피벗을 기준으로 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 이동
3. 재귀를 사용하여 2번 과정을 반복 (리스트의 크기가 0이나 1이 될 때 까지)

 

 

✅ 요소의 정렬 흐름

참고 : https://youtu.be/O-O-90zX-U4

피벗을 기준으로 작은건 왼쪽, 큰건 오른쪽으로 보내는 방법은 위와 같다.

 

💡 1, 2, 3은 아래와 같은 과정을 통해서 이미 정렬이 된 것이다. 

💡 피벗을 정하는 방법은 "리스트의 0번 인덱스"라 한다.

 

1. 피벗을 (8)로 설정한다.
2. 인덱스 오름차순으로 피벗보다 큰 값을 탐색하고, 내림차순으로는 피벗보다 작은 값을 탐색한다.   
    → (9)와 (4)
3. 두 값의 위치를 교환하고, 다시 검색한다.
    → (10)와 (7)
4. 두 값의 위치를 교환하고, 다시 검색한다.
    → 피벗보다 큰 값 : (10), 피벗보다 작은 값 : (7)
    → 작은값의 인덱스 < 큰 값의 인덱스 일 경우, 교차가 일어났다고 하며 탐색을 종료한다.
5. 작은 값(7)과 피벗의 위치를 교환한다.
6. 피벗을 기준으로 리스트를 2개로 나눈다.

7. 피벗을 (7)로 설정한다.
8. 인덱스 오름차순으로 피벗보다 큰 값을 탐색하고, 내림차순으로는 피벗보다 작은 값을 탐색한다.   
    → 피벗보다 큰 값 : 없음, 피벗보다 작은 값 : (6)
    → 큰 값, 작은 값 중 하나라도 없을 경우(끝까지 탐색한 경우) 교차가 일어난 것과 같음, 탐색 종료
9. 작은 값(6)과 피벗의 위치를 교환한다.
10. 피벗을 기준으로 리스트를 2개로 나눈다.

 

위의 과정을 반복한다.

 

이미지 출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

말로 설명한 과정을 그림으로 보면 위와 같다!

 

 

 

참고

https://youtu.be/O-O-90zX-U4

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog