퀵정렬

특정한 값을 기준으로 큰 숫자와 작은 숫자를 나누면 어떨까?

<작동방식>

1. 리스트에서 임의의 원소를 피벗으로 선택합니다.
2. 피벗보다 작은 원소들은 피벗 왼쪽에, 피벗보다 큰 원소들은 피벗 오른쪽에 위치시킵니다.
3. 피벗 왼쪽과 오른쪽 부분을 각각 재귀적으로 퀵 정렬을 사용하여 정렬합니다.

<예시>

p
3 7 8 1 5 9 6 10 2 4   //3을 피벗으로 선택함

p v              v
3 7 8 1 5 9 6 10 2 4  //전체적으로 보았을 때 왼쪽부터 시작하여 '3'보다 큰 값인 7을 선택.
					  //오른쪽으로 시작하였을 떄 '3'보다 작은 2를 선택.
p   v v                         
3 2 8 1 5 9 6 10 7 4  //큰 값과 작은 값을 변경합니다.
					  //왼쪽에서 '3'보다 큰 값 8과 오른쪽에서 '3'보다 작은 값인 1을 선택.

p										 
v   v               										 
3 2 1 8 5 9 6 10 7 4  //큰 값과 작은 값을 변경합니다.
					  //왼쪽에서 '3'보다 큰 값 8과 오른쪽에서 '3'보다 작은 값인 1을 선택.
					  //위와 동일하지만 문제점은 엇갈렸다. 엇갈렸을 때 피벗값과 작은값의 인덱스를 변경
					  //엇갈림 : 작은 값의 인덱스가 큰값의 인덱스보다 더 작은것

1 2 3 8 5 9 6 10 7 4  //이를 통해 3은 정렬이 되었다.
					  //3보다 왼쪽은 3보다 작음. 3보다 오른쪽은 3보다 큼.
					  //이제 왼쪽 집합과 오른쪽 집합에서 그동안 한 일을 반복하면됨.

p v 
1 2  //왼쪽부터 '1'보다 큰 2를 선택. 오른쪽부터 작은 값을 찾음.
     //없기 때문에 자신을 선택하고 엇갈림이 생김. 피벗인 1과 작은 값 1을 바꿈. 결국 그대로임.

p   v        v    
8 5 9 6 10 7 4  //왼쪽에서 8보다 큰 9와 오른쪽에서 8보다 작은 4를 선택

p       v  v
8 5 4 6 10 7 9  //9,4를 변경함.
				//왼쪽에서 8보다 큰 10과 오른쪽에서 8보다 작은 7를 선택

p       
8 5 4 6 7 10 9  //10,7를 변경함.
				//왼쪽에서 8보다 큰 10과 오른쪽에서 8보다 작은 7를 선택. 엇갈림.
				//엇갈림으로 인해 8과 작은값인 7과 자리를 변경함.

        p
7 5 4 6 8 10 9  //8를 기준으로 왼쪽은 작은 값들이 있고 오른쪽에는 큰 값이 있음.
				//다시 반복함.