5. 퀵소트(Quick Sort)

# 퀵소트(Quick Sort)

시간 복잡도가 O(nlogn)으로 빠른 편에 속한다. 하지만 정렬된 후 사용하면 O(n^2)가 되는 단점이 존재한다.

따로 메모리를 사용하지 않아 공간복잡도도 좋다.(좋은 space complexity를 가진다)

 

**퀵소트와 머지소트는 재귀함수를 사용해서 코드 구성해야한다. 같은 행위가 반복되니까!

 

# 코드 구현

퀵소트1

퀵소트 메인절에는 내가 정렬시켜볼 배열을 넣어본다. 이 부분은 문제에 따라서 입력받은 값 등으로 변경될 수 있다.

퀵소트는 퀵소트를 진행할 배열의 제일 왼쪽 값과 오른쪽 값이 기준이 되므로 이 두 개를 left와 right값으로 지정해준다. 메처음 시작 할 땐 배열의 제일 왼쪽의 인덱스는 0으로 고정되고 오른쪽 인덱스는 배열의 전체길이에서 1을 뺀 값이므로 이를 넣어준다.  이 세 가지 값(정렬시킬 배열, 제일 왼쪽값, 제일 오른쪽값) 우리가 만들어둔 quickSort 메소드에 매개변수로 넣어주고 퀵소트 정렬을 진행한다.

 

  quickSort 메소드에서 일단 left값과 right값이 교차하면 안되므로 두개 확실히 크기가 left<right인지 확인해주고 이가 아닐경우 리턴시켜주는 작업으로 시작한다. 피봇은 배열의 가장왼쪽값으로 지정한다. 얘가 quickSort의 기준이 된다.

이제 기준이 되는 피봇의 다음 값(피봇을 제외한 제일 왼쪽값)부터 크기 비교를 하는데 피봇의 다음 값부터 피봇과 크기비교를 진행한다. 이 때 피봇보다 큰 값을 발견하면 일단 멈춤. 다음은 제일 오른쪽 값부터 순서대로 피봇과 크기비교를 한다. 이 때 피봇보다 작은 값을 발견하면 일단 멈춤.

 

이 두 값의 위치가 서로 교차하지 않는다면 두 값의 자리를 바꿔주고 두 값의 위치가 교차하였다면 작은 값과 피봇의 위치를 바꿔준다. 이렇게 한 바퀴를 다 돌았다면 피봇값을 중심으로 두 개의 배열로 나누고 quickSort 과정을 반복해준다. (재귀함수 사용! 자기자신 다시 반복!) 퀵소트끝~~ 이 작업을 돌리고 나면 순서대로 나열된다. 이 방법은 시간복잡도가 낮아서 자주 사용된다! (시간복잡도 nlogn)