퀵 정렬(QuickSort)

재귀적

기준 키를 하나 두고 배열의 왼쪽에서부터(i)기준 키 보다 큰 값을 찾고 오른쪽에서부터는(j)작은 값을 찾아서 찾은 큰 값과 작은 값을 바꿔나간다.이 때 찾은 큰 값의index(i)가 작은 값의index(j)보다 크게 되는 경우(i>j)두 값을 바꾸지 않고 작은 값과 기준 키 값을 바꾼다.그렇게 하면 기준 키를 기준으로 왼쪽은 기준 키보다 작은 값이 오른쪽에는 기준 키보다 큰 값이 위치한다.즉,기준키는 정렬 된 후의 자리에 위치하게 된다.(기준키는 정렬 됨)

1. 기준키(pivot, 4)를 정한다.
   i는 인덱스 0부터 올라가면서 기준 키 값보다 큰 수를 구하고
   j는 배열의 마지막 인덱스부터 아래로 내려가면서 기준 키 값보다 작은 수를 구한다.
2. 기준키보다 큰 수(i)와 오른쪽에서부터 기준키보다 작은 수(j)를 구해서
   두 수의 위치를 바꾼다. (그림에서는 이미 위치를 바꾼 뒤의 상태)
3. 이를 반복하다 [작은 수(j)의 위치 <큰 수(i)의 위치]가 되는 경우
4. j위치와 기준키(pivot)의 위치를 바꾼다.

그 뒤 기준 키를 기준으로 왼쪽 배열과 오른쪽 배열도 이를 반복한다.모든 정렬이 끝났을 때 배열은 오름차순으로 정렬하게 되고 만약 내림차순으로 정렬하고 싶으면 기준 키의 왼쪽에서 기준 키보다 작은 값을 찾고 오른쪽에서부터는 큰 값을 찾아서 위에서 했던 것을 반복하면 된다.

Ex) 학생 정보를 입력받아 성적 순, 학번 순 정렬

전체코드 :https://gist.github.com/fpdjsns/91c71ae97c341679b179a6cd35056917

참고 페이지 : http://terms.naver.com/entry.nhn?docId=2270444&cid=51173&categoryId=51173

---

이를반복적으로 구현할 때는 두 개의 스택을 사용한다.

한 개의 스택에는 배열의 하한 값(정렬하고자 하는 배열의 시작index)을 저장하고 다른 한 개에는 배열의 상한 값(정렬하고자 하는 배열의 마지막index)을 넣는다.정렬하는 방법은 위와 같고 재귀 호출을 하는 대신 반복문을 사용하는데 반복문이 시작할 때 스택에서 하한 값과 상한 값을pop해서 사용한다.

이 때,스택은FILO(First In Last Out)이므로 만약 왼쪽 배열을 먼저 정렬하고 싶다면 왼쪽 배열의 하한 값과 상한 값을 나중에 넣는다.나중에 정렬되면 왼쪽 배열을 먼저 정렬하든지 오른쪽 배열을 먼저 정렬하든지 결과는 같으니 별로 신경은 안 써도 되는 부분이다.

EX) 배열 안의 숫자를 오름차순 정렬

전체코드 :https://gist.github.com/fpdjsns/a244aa4445e42dfc422beca087e453f5