알고리즘 퀵정렬(Quick sort) 그림으로 쉽게 이해하기

알고리즘 퀵정렬(Quick sort) 그림으로 쉽게 이해하기

 

안녕하세요.

로스윗의 코딩캠프입니다.

오늘은 알고리즘 정렬 중에서

퀵정렬(Quick sort)에 대한 포스팅을 진행하겠습니다.

정말 어렵지 않으니 잘 따라와주세요.

 

- 퀵정렬(Quick sort) 시간 복잡도

퀵 정렬(Qucik sort)도 합병정렬(merge sort)과 마찬가지로

배열을 둘 씩 분할하면서 정렬하는 과정을 거치기 때문에 시간복잡도는 O(NlogN)이 됩니다.
하지만 같은 NlogN이더라도 실제 정렬에는 훨씬 더 짧은 시간이 소요 됩니다.

 

왜그럴까요?

 

 

- 퀵정렬(Quick sort)이 합병정렬(Merge sort)보다 훨씬 더 빠른 이유

리스트(list)파트에서 배열 리스트가 메모리 공간 상에서 인접하게 위치해 있기 때문에 연산에 더 유리한 것처럼
퀵정렬도 컴퓨터의 하드웨어 특성때문에 더 빠른 성질을 가질수 있게 됩니다.
이것을 참조지역성의 원리로 설명을 하게 됩니다.

 

 

1. 캐시(CACHE) 사용

퀵 정렬은 알고리즘 특성상 동일한 배열 내에서 자리를 이동시킵니다.
그래서 인접한 데이터들 사이에서 이동이 발생하기 때문에

제일 처음 배열에 접근할 때만 실제 메모리에서 데이터를 가져오고,
이후에는 캐시로 배열에 접근 할 수 있기 때문에 메모리로 접근할 때보다 훨씬 더 빠른 접근이 가능합니다.

 

 

CPU에서 처음에만 RAM에서 데이터를 가져오고 그 다음엔 CACHE에 올려놓고 바로바로 가져온다

 

 

2. 피봇(Pivot) 연산 제외

그리고 한 번 위치가 정해진 피봇(pivot)값은

한번 위치가 정해지면 이후의 연산에서는 해당값은 제외를 시키고 연산을 하기 때문에

정렬이 진행될 수록, 다시 말해 분할을 할수록 계산해야 할 데이터의 수가 점점 줄어드는 특성도 있습니다.
계산해야 할 데이터의 수가 줄어든면 당연히 정렬 속도를 줄이는데도 영향을 주겠죠.

그래서 합병정렬(merge sort)은 인메모리 정렬로 구현을 하더라도

정렬을 보조해주는 추가 메모리 공간이 필요하다는 단점이 있었지만,
퀵 정렬에서는 추가적인 메모리 공간을 더 사용하지 않고

합병정렬(merge sort)과 비슷하게 divide and conquer 방식으로 정렬을 할 수 있게 됩니다.

 

 

- 퀵정렬 알고리즘

이제 본격적으로 퀵정렬(Quick sort)의 알고리즘을 알아보겠습니다.
퀵정렬(Quick sort)의 알고리즘은 피봇(pivot)값을 정하는 것부터 시작합니다.

피봇(pivot)값으로 정할 인덱스는

리스트에서 가장 앞에 위치한 원소여도 되고, 가장 뒤에 위치한 원소여도 됩니다.
혹은 지금 제가 한 것처럼 중간에 위치한 원소로 설정할 수도 있어요.
그렇게 해서 가장 중간에 위치한 5를 pivot값으로 정해보도록 하겠습니다.

 

 

중간인 5를 피봇(pivot)값으로 정하기

 

피봇(pivot)값을 정했으면 이제 피봇(pivot)값을 기준으로 원소들을 재배치 하게 됩니다.
그래서 피봇(pivot)값의 왼쪽에는 피봇(pivot)값보다 작은 값들이 위치하게 되고

피봇(pivot)값의 오른쪽에는 피봇(pivot)값보다 큰 값들이 위치하게 됩니다.

 

 

피봇을 기준으로 왼쪽과 오른쪽에 피봇보다 작은 값, 큰 값들이 위치한다

 

 

이때 양 사이드의 배열들은 아직 정렬을 되지 않았지만

피봇(pivot)보다 작은값과 피봇(pivot)보다 큰 값으로 묶으면서

피봇(pivot)값의 인덱스는 바뀔 수 있습니다.

그렇게 해서 피봇(pivot)값을 기준으로 왼쪽과 오른쪽, 2개의 서브리스트를 볼 수 있습니다.
이제 각각 서브리스트에서도 마찬가지로 앞에서 했던 로직을 반복해줍니다.
그래서 왼쪽의 서브리스트에서는 피봇(pivot)값이 중간값인 1이 되고,

오른쪽에서는 피봇(pivot)값을 6으로 설정할 수 있습니다.

 

 

서브리스트에 각각 피봇값을 설정한 모습

 

마찬가지로 정해진 피봇(pivot)값을 기준으로

피봇(pivot)값의 왼쪽에는 피봇(pivot)값보다 작은 값, 오른쪽에는 피봇(pivot)값보다 큰 값을 넣어주면은
아래 배열처럼 다시 재정렬이 이루어지겠죠.

 

 

재정렬된 모습

이제 오른쪽의 서브리스트는 원소의 개수가 하나만 남았기 때문에 더이상 분할할 수 없는 단위가 되었습니다.
그래서 오른쪽의 서브리스트는 퀵정렬이 종료되게 됩니다.

왼쪽은 아직 서브리스트가 남아 있기 때문에 다시 pivot값을 정해서 정렬을 해줘야합니다.
여기서 pivot값은 서브리스트의 중간에 위치한 값인 3이 될 수 있습니다.

 

 

다시 서브리스트의 피봇을 잡아준다

그래서 3을 기준으로 3보다 작은 값을 왼쪽에, 큰 값을 오른쪽에 위치를 시킵니다.

그러면 각 서브리스트의 크기도 여기서 1이 되기 때문에 더이상 분할할 수 없어서 퀵소트는 종료됩니다.
그리고 결과를 보면 1, 2, 3, 4, 5, 6, 7 순서대로 잘 정렬된 것을 볼 수 있습니다.

 

퀵소트 종료

그래서 퀵정렬(Quick sort)는 합병정렬(merge sort)와 마찬가지로

데이터를 절반씩 분할하면서 줄여나가기 때문에 logN만큼의 분할이 이뤄지게 되고,
각 분할에서 N번의 값 비교를 통해서 자신의 위치를 찾아나가기 때문에 시간복잡도가 NlogN이 나오게 되는겁니다.

 

하지만 최악의 경우엔 정렬하고자 하는 리스트의 경우가 이미 정렬된 상태라면

시간복잡도는 N제곱까지 늘어날 수 있게 됩니다.

 

예를들어서 오름차순 되어 있는 리스트에서

가장 앞에 들어있는 값을 피봇(pivot)값으로 정했다고 가정해 봅시다.

 

 

맨 앞에 있는 값을 피봇값으로 정한 경우

 

근데 분할 결과를 보면은 아마 아래 그림과 같이 이런식으로 될거에요.

 

 

 

 

왜냐하면 pivot값의 왼쪽에 넣을 작은 값이 없기 때문이겠죠.
그럼 여기서도 또 동일한 기준으로 pivot이 결정되기 때문에 이번에도 가장 앞에있는 값인 2가 pivot값이 될거에요.
여기서도 재정렬을 하게 되면 여기서도 2보다 작은 값이 없기 때문에 이렇게 분할이 되게 되겠죠.

 

 

다시 말해서 이 배열의 pivot값이 리스트에서 최소값이나 최대값으로 지정이 되어버려서 
분할이 절반씩 이루어지지 않는 상태가 될 때 퀵소트는 효율을 내지 못한다고 볼 수 있습니다.

그러면 절반씩 분할할 때 logN번의 분할 횟수가 나온다는 것을 도출을 해서 NlogN이라는 시간복잡도가 나왔던 건데
분할 횟수가 데이터의 개수만큼 즉, N번만큼 발생하게 되는거죠.

그래서 logN이 N으로 증가하게 되고 시간복잡도가 N제곱만큼 나오게 되는 겁니다.

그래서 이런 치우친 분할을 극복하기 위해서 pivot값을 고를 때

몇 가지 pivot값의 후보군을 두고 그 중에 가장 중간값을 찾아서 pivot으로 사용하는 알고리즘을 사용하기도 합니다.
이것을 Median of Three라고 하는데 이것은 궁금하시면 찾아보시는 것도 재밌을 것 같습니다.

 

로스윗의 코딩캠프는

미래의 개발자 여러분을 응원합니다.

모두 화이팅!!

프론트엔드? 백엔드? 개발 관련 직군 몽땅 정리해드리겠습니다

프론트엔드? 백엔드? 개발 관련 직군 몽땅 정리해드리겠습니다

원형큐(Circular Queue)를 반드시 사용해야 하는 이유 (ft. 그림으로 쉽게 설명)

원형큐(Circular Queue)를 반드시 사용해야 하는 이유 (ft. 그림으로 쉽게 설명)