JavaScript 알고리즘(4) 퀵정렬(Quick Sort)

 

알고리즘 4번째 시간 ! 돌고돌아 오랜만에 돌아왔다.

---

JavaScript 알고리즘(4) 퀵정렬(Quick Sort)

 

퀵 정렬은 앞선 정렬과 확인했을 때 훨씬 빠르다. 이를 분할정복 알고리즘이라고 한다. 

특정 값을 기준으로 큰 숫자와 작은 숫자로 나눠 보면 어떻까?

 

- 기초 아이디어

퀵 정렬에서는 피봇이라는 기준 값이 있다. 보통 첫번째원소를 피봇(pivot) 이라고 놓는다.

 

피봇을 기준으로,

피봇보다 작은 애들은 모두 피벗의 왼쪽으로 옮기고, 

피봇보다 큰 애들은 모두 피벗의 오른쪽으로 옮긴다. 

다 옮겼으면 피봇을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 순서대로 정렬한다.

 

좌우로 나눠진 부분 리스트는 순환 호출을 이용하여 정렬을 반복한다.
부분 리스트 내에서 다시 피봇(기준값)을 정해서 좌우로 2개의 부분 리스트로 나누는 과정을 반복한다.

한마디로 쪼개지고 쪼개지고 쪼개져서 더 이상 분할이 불가능할 때까지 반복한다.

 

- 다음 숫자를 오름차순으로 정렬하시오.

[3, 7, 8, 1, 5, 9, 6, 10, 2, 4]

 

기본 로직

1. 첫번째 숫자 3를 피봇으로 설정 
이때 3을 기준으로 자기보다 큰 숫자는 본인 기준 정방향(앞→뒤)으로 검사하면서 찾고,
3보다 작은 숫자는 본인기준 역방향(뒤→앞)으로 검사하면서 찾는다.

2. 맨앞 → 맨끝 순서로 검사할 때는, 처음 만난 3보다 큰 값을 선택 (7)
[3, 7, 8, 1, 5, 9, 6, 10, 2, 4]

3. 맨앞 ← 맨끝 순서로 검사할 때는, 처음 만나는 3보다 작은 값을 선택 (2)
[3, 7, 8, 1, 5, 9, 6, 10, 2, 4]

4. 둘이 자리를 바꿔줌. (7 ↔ 2)
[3, 2, 8, 1, 5, 9, 6, 10, 7, 4]

 

이런식으로 쭉쭉 가면,

 

1번째 [3, 7, 8, 1, 5, 9, 6, 10, 2, 4]

→ 3보다 큰 첫번째 수인 7(정방향), 3보다 작은 첫번째 수인 2(역방향) 의 순서를 바꾼다.

 

2번째 [3, 2, 8, 1, 5, 9, 6, 10, 7, 4]

→ 2와 7의 순서가 바뀌었다.

 

3번째 [3, 2, 1, 8, 5, 9, 6, 10, 7, 4]

→ 3보다 큰 첫번째 수인 8 (정방향, 3보다 작은 첫번째 수인 1(역방향)인데, 숫자가 겹쳐졌다.

   여기서 1, 8 이 엊갈렸다. 즉, 역방향 index 가 > 정방향 index 보다 크다. (즉, 원래 크기 순서대로 있다.) 

   이런 조건이 오면 역방향 인덱스 값 1과 맨앞 피봇인 3을 바꿔준다. 

 

4번째 [1, 2, (3), 8, 5, 9, 6, 10, 7, 4] 

→ 3을 기준으로 앞뒤로 작은수 큰수가 분할된다. 이제 피봇은 1이 된다.

 

5번째 [1, 2, 3, 8, 5, 9, 6, 10, 7, 4]

→ 그런데 1보다 작은게 없다. 1보다 작은 숫자를 찾지 못해 결국 1까지 돌아온다. 큰 값은 바로 옆 숫자 2를 찾았다.

    이 때 작은 값의 인덱스 1이 < 큰 값의 인덱스보다 작다. 이럴 때는 피봇1과 해당인덱스1를 바꿔줘야 한다.

    즉 1과 1을 교환하므로 1은 그대로이다.

 

6번째 [1, 2, 3, 8, 5, 9, 6, 10, 7, 4]

→ 왼쪽에 아무것도 없는 경우에는 피봇값을 바로 옆의 값으로 변경한다. 따라서 다음 피봇주자는 2가 된다.

 

7번째 [1, 2, 3, 8, 5, 9, 6, 10, 7, 4]

→ 위와 같은 조건이니 다음 피봇주자는 3이 된다.

 

8번째 [1, 2, 3, 8, 5, 9, 6, 10, 7, 4]

→ 정방향으로 8보다 큰 값인 9를 찾았고, 역방향으로 8보다 작은 4를 찾았다. 

 

9번째 [1, 2, 3, 8, 5, 4, 6, 10, 7, 9]

→  둘의 순서를 바꿔주자.

 

10번째 [1, 2, 3, 8, 5, 4, 6, 10, 7, 9]

→ 여기서 엊갈림이 발생한다. 정방향일때 8보다 큰수 10과 역방향으로 일때 8보다 작은수 7의 동선이 겹친다. 

 

11번째 [1, 2, 3, 8, 5, 4, 6, 7, 10, 9]

→ 그럼 작은 수와 피봇을 교체한다. 피봇은 7이 된다.

 

12번째 [1, 2, 3, 7, 5, 4, 6, 8, 10, 9]

→ 그래서 피봇은 7이 되었다.

 

13번째 [1, 2, 3, 7, 5, 4, 6, 8, 10, 9]

→ 여기서 또 10과 6이 엊갈림이 발생한다. 

 

14번째 [1, 2, 3, 7, 5, 4, 6, 8, 10, 9] 

→ 작은 수인 6과 피봇인 7이 교체된다. 

 

15번째 [1, 2, 3,6, 5, 4, 7, 8, 10, 9] 

→ 그래서 피봇은 6이 되었다.

 

16번째 [1, 2, 3, 6, 5, 4, 7, 8, 10, 9]

→ 여기서 또 엊갈림이 발생한다. 작은수인 4과 피봇인 6이 교체된다. 피봇은 4가 된다.

 

17번째 [1, 2, 3, 4, 5, 6, 7, 8, 10, 9]

→ 그래서 피봇은 4가 되었다.

 

18번째 [1, 2, 3, 4, 5, 6, 7, 8, 10, 9]

→ 왼쪽에 아무것도 없는 경우에는 피봇값을 바로 다음 값으로 변경한다. 따라서 다음 피봇주자는 5가 된다.

 

19번째  [1, 2, 3, 4, 5, 6, 7, 8, 10, 9] 

→ 그래서 피봇은 5가 되었다.

 

20번째 [1, 2, 3, 4, 5, 6, 7, 8, 10, 9]

→ 왼쪽에 아무것도 없는 경우에는 피봇값을 바로 다음 값으로 변경한다. 그래서 피봇은 6이 되었다.

 

21번째 [1, 2, 3, 4, 5, 6, 7, 8, 10, 9]

→ 왼쪽에 아무것도 없는 경우에는 피봇값을 바로 다음 값으로 변경한다. 그래서 피봇은 7이 되었다.

 

22번째 [1, 2, 3, 4, 5, 6, 7, 8, 10, 9]

→ 왼쪽에 아무것도 없는 경우에는 피봇값을 바로 다음 값으로 변경한다. 그래서 피봇은 8이 되었다.

 

23번째 [1, 2, 3, 4, 5, 6, 7, 8, 10, 9]

→ 왼쪽에 아무것도 없는 경우에는 피봇값을 바로 옆의 값으로 변경한다. 따라서 다음 피봇주자는 10이 된다.

 

24번째  [1, 2, 3, 4, 5, 6, 7, 8, 10, 9]

→ 역방향 작은수 9와 정방향 큰수는 본인자신을 가르키게 되기 때문에 10과 9를 바꿔준다.

 

25번째  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

→ 이로써 퀵정렬을 통해 오름차순으로 정렬이 되었다.

 

다음시간에는 퀵정렬을 구현하는 코드를 알아보자.

 

 

 

ref: https://www.youtube.com/playlist?list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz