퀵정렬 (quick sort)

퀵정렬도 합병정렬과 마찬가지로 시간복잡도가 으로 빠르게 정렬할 수 있는 효율적인 정렬이다.

 

 

 

 

이미지 출처 : https://m.blog.naver.com/PostView.nhn?blogId=hero1014&logNo=20191727330&proxyReferer=http%3A%2F%2Fwww.google.co.kr%2Furl%3Fsa%3Di%26rct%3Dj%26q%3D%26esrc%3Ds%26source%3Dimages%26cd%3

D%26ved%3D2ahUKEwjX0NO0upzgAhUx7GEKHbbxC8AQjRx6BAgBEAU%26url%3Dhttp%253A%252F%252Fm.blog.naver.com%252Fhero1014%252F20191727330%26psig%3DAOv

Vaw2SoIOMtqZXX839AdvAgYEo%26ust%3D1549176455485435

 

 

퀵정렬은 pivot을 설정하는 여러 가지 방법이 있지만, 나는 첫번째 숫자를 pivot 으로 설정한다. 

 

퀵정렬을 위의 그림에서 간단한 순서로 설명해 보면

 

1. 배열의 첫번째 숫자인 5를 pivot으로 설정하고

2. pivot+1부터 끝까지의 숫자들 중 pivot보다 작은 숫자들은 왼쪽에 배치한다.

3. pivot을 배치한다.

4. pivot보다 큰숫자들은 오른쪽에 배치한다.

 

이순서대로 진행하게 되면 pivot의 자리가 확정되고, pivot보다 작은 숫자들은 왼쪽에, pivot보다 큰 숫자들은 오른쪽에 놓이게 된다.

 

그런 다음에 다시 pivot을 제외한 왼쪽 숫자들 중에 첫번째 숫자를 pivot으로 정하고 위의 방법대로 진행하고,

 

pivot을 제외한 오른쪽 숫자들 중에 첫번째 숫자를 pivot으로 정하고 똑같이 위의 방법을 수행한다.

 

그러면 결론적으로 pivot들이 자기의 자리를 찾아가면서 정렬이 된다.

 

코드를 보면서 더 자세히 설명해보자.

 

 

퀵 정렬 또한 pivot의 자리를 정하고 pivot의 왼쪽 오른쪽에서 같은 방법을 수행하기 때문에 재귀적으로 구현할 수 있다.

 

재귀호출이기 때문에 기저조건이 합병정렬과 마찬가지로 start와 end가 같을때 return을 해주지만, 확실하게 하기 위해

 

나는 start가 end 이상일때로 설정 했다.

 

그 다음에 배열의 시작을 pivot으로 두고 start+1부터 end까지 pivot보다 작은 숫자를 left[] 배열에 저장하는 getLeft를 실행하고,

 

start+1부터 end까지 pivot보다 큰 숫자들을 right[] 배열에 저장하는  getRight를 실행한다.

 

코드에서 내가 getLeft 와 getRight를 void로 하지 않고,  int로 하여 각각 left_cnt와 right_cnt에 저장한 이유는

 

pivot보다 작은 숫자가 몇개인지, 큰 숫자가 몇개인지 모르기 때문에 getLeft와 getRight를 구하면서 몇갠지 알아 놓아야

 

얻은 왼쪽 배열과 pivot과 오른쪽 배열을 합쳐서 pivot자리를 확정할 수 있기 때문이다.

 

구하는 방법은 밑에서 두 함수 코드를 볼때 설명하겠다.

 

그리고 pivot보다 작은 숫자들을 얻었으면 그 숫자들을 다시 arr에 처음부터 배치한 다음에 pivot을 넣고 pivot보다 큰 숫자들을 차례로

 

넣는다. 그 후에 pivot의 자리가 확정 되었으면 pivot 왼쪽에서 다시 재귀호출을 이용하여 퀵정렬을 하고, 오른쪽에서 퀵정렬을 한다.

 

 

arr 배열의 start부터 end 까지 pivot과 비교한다. 그래서 작으면 result[] 매개변수에 left[] 배열을 넣었기 때문에 left[]배열에 저장된다.

 

그리고 idx를 이용하여 0번째부터 차례대로 넣으면 idx가 배열에 들어간 숫자의 개수가 되기 때문에 그 개수를 return 한다.

 

 

getRight 함수 또한 getLeft함수와 똑같기 때문에 설명은 생략.

 

이렇게 하면 퀵정렬이 완성된다. 예시 문제를 한번 풀어보자.

 

 

 

 

문제

---

N개의 자연수가 주어질 때, 퀵정렬을 이용하여 이를 정렬하는 프로그램을 작성하시오.

 

입력

---

첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) 두 번째 줄에 N개의 자연수가 주어진다.  

출력

---

퀵정렬을 이용하여 숫자를 오름차순으로 정렬한 결과를 출력한다.

 

예제 입력

10
5 9 2 8 3 7 4 6 1 10

예제 출력

1 2 3 4 5 6 7 8 9 10

예제 입력

5
2 3 1 2 1

예제 출력

1 1 2 2 3