퀵 정렬 알고리즘

arr = [5, 4, 6, 8, 2, 3, 1, 7, 9, 0]

 

위 배열을 퀵 정렬을 통해 오름차순으로 정렬해보자.

 

퀵 정렬은 pivot과 2개의 비교가 필요하다.

arr[0]=5를 pivot으로 설정하고 arr[1]=4부터 뒷방향으로의 비교, arr[9]=0부터 앞방향으로의 비교.

arr[1]의 비교를 i라고 하고, arr[9]의 비교를 j라고 하겠다.

pivot과 i,j를 비교하면 된다.

 

i는 pivot보다 작을 경우 앞으로 나가고, j는 pivot보다 클 경우 뒤로 간다.

i=arr[1]=4 < arr[0]=5 이므로 i=arr[2]=6이 되고, 

j=arr[9]=0 <arr[0]=5 이므로 뒤로가지 않고 정지.

 

다시 i와 pivot을 비교, i=arr[2]=6 > arr[0]=5 이므로 정지.

i와j가 모두 정지했을 때 두 값을 swap한다.

 

arr = [5, 4, 0, 8, 2, 3, 1, 7, 9, 6]

 

i=arr[2]=0 < arr[0]=5 이므로 i=arr[3]=8이 되고 정지.

j=arr[8]=8 > arr[0]=5 이므로 뒤로 가 j=arr[7]=7 > 5 이므로 j=arr[6]=1 < 5이므로 정지.

8과 1을 swap.

 

arr = [5, 4, 0, 1, 2, 3, 8, 7, 9, 6]

 

i=arr[6]=8까지 나가고,

j=arr[6]=8에서 뒤로가 arr[5]=3에 위치.

이 때 i와j가 교차되었다.

교차되었을 때의 j값과 pivot을 swap한다.

 

arr = [3, 4, 0, 1, 2, 5, 8, 7, 9, 6]

 

pivot을 기준으로 앞의 배열 [3,4,0,1,2]와 뒷 배열 [8,7,9,6]을 다시 퀵정렬로 정렬한다.

 

앞의 배열의 pivot은 3이다.

i=arr1[1]=4에서 멈춤.

j=arr1[4] = 2에서 멈춤.

swap.

 

arr1 = [3, 2, 0, 1, 4]

i=arr1[4]=4에서 멈춤.

j=arr1[3]=1에서 멈춤.

교차했으므로 j와 pivot이랑 swap.

i와j는 처음부터 다시 시작한다.

 

arr1 = [1, 2, 0, 3, 4]

i=arr1[1]=2에서 멈춤.

j=arr1[2]=0에서 멈춤.

둘이 swap.

 

arr1 = [1, 0, 2, 3, 4]

i=arr1[2]=2에서 멈춤.

j=arr1[1]=0에서 멈춤.

교차했으므로 j와 pivot이랑 swap.

 

arr1 = [0, 1, 2, 3, 4]

 

 

이제 뒷 배열을 보자.

arr2 = [8,7,9,6]

 

pivot = 8

i=arr2[2]=9에서 멈추고

j=arr2[3]=6에서 멈춘다.

둘이 swap.

 

arr2 = [8, 7, 6, 9]

i=arr2[3]=9에서 멈추고

j=arr2[2]=6에서 멈춘다.

둘이 교차했으므로 pivot과 j를 swap.

 

arr2 = [6, 7, 8, 9]

 

 

이렇게 앞 배열,5,뒷 배열을 합치면

[0,1,2,3,4,5,6,7,8,9]가 된다.