퀵 정렬 (Quick Sort)

퀵 정렬에 대해서 알아보자.. 앞서 설명한 버블 정렬과 선택 정렬보다 우수한 성능을 보여주는 정렬 알고리즘이다.

 

그냥 간단히 알고리즘에 대해서 보자면

 

키 하나를 정하고? 키를 기준으로 키보다 큰것 키보다 작은것을 구별해서 분할하는 과정이다.

 

예시들 들어 이렇게 무작위로 나열된 수가 있다고 해 보자.

 

키를 정한다.

그리고 오른쪽으로 가는 화살표와 왼쪽으로 가는 화살표를 그리자.

 

오른쪽으로 가는 화살표는 Key보다 큰 값을 찾는 화살표다.

 

왼쪽으로 가는 화살표는 Key 보다 작은 값을 찾는 화살표다.

 

그래서 이제 화살표가 찾는만큼 길을 간다. 

 

 

그리고 화살표는 여기에 위치하게 된다. 이때 두 요소의 자리를 교체한다.

 

또 다시 화살표를 그리고, 출발한다.

 

이번에는 화살표가 교차되어 있다. 그렇다면 키보다 작은 수 2와 Key의 위치를 교환한다. 

 

이러한 과정 때문에 교차가 발생할 때, 키의 우측에는 무조건 키보다 큰 수가 있고 키의 좌측에는 키보다 작은 수가 존재한다. 어쨋든 중요한것은 Key 자체는 원래 위치에 도달했다는 소리이다.

 

따라서 키의 좌측과 우측을 분할하는 과정을 거친다.

 

 그리고 분할된 요소들만 다시 처음부터 과정을 반복한다.

 

진행한 결과 

교차가 발생하였고 다시 작은 수와 Key의 위치를 교체한다.

 

또 분해가 되고 

 

이런식으로 정렬이 된다.

 

코드로 구현하는건 시간이 안되서 무리! 내일 하도록 하겠음