재귀호출 2. 퀵정렬(Quick Sort) 및 코딩 방법

퀵 정렬 :  일렬로 랜덤으로 배치되어있는 배열을 하나의 기준값[S](여기서는 맨 왼쪽)을

 

2가지형태로 열을 지나가는데 

    -1.기준값[S] 다음 왼쪽[L]값 부터 마지막열[R]까지    (배열 인덱스Left Index가 증가하면서)

    -2.마지막열[R](오른쪽 끝값) 부터 왼쪽값[L] 위치까지 (배열 인덱스Rigth Index가 감소하면서)

Quik Sort

   -1에서 [S]보다 큰값(Left Big)을 찾고,

   -2에서 [S]보다 작은값(Right Small) 찾아  

    LB 와 RS 값의 위치를 바꿔 준다.  (RI > LI 인 상황)

    바꾸고  LI 증가시키고 RS를 감소하면서 위 같은 상황이 오면 값을 바꿔준다.

 

만약 -1의 인덱스와 -2의 인덱스가 교차되기전(RI <= LI) 

LI 와  S 값의 위치를 바꾼다. 

---- Quik Sort End

그럼 S값 기준으로 왼쪽값들은 정렬안된 S보다 작은 값들의 그룹이되고

 오른쪽 값들은 정렬안된 S보다 큰값들로 되어있다. 

 

완전히 정렬하려면 

왼쪽 그룹을 Quik Sort로 정렬 (그 그룹안에서 한번으로 정렬이 안되면  Quik Sort 을 넣어 정렬될때까지 한다.)

오른쪽 그룹을 Quik Sort로 정렬하면  (그 그룹안에서 한번으로 정렬이 안되면  Quik Sort 을 넣어 정렬될때까지 한다.)

정렬이 완성된다.

 

여기서 사용하는게 재귀호출이다.

네이버 지식백과 - 퀵정렬

같은 반복문을 여러번 코드 작성을 하지 않고 사용하게 아주편리한 기능이라고 이때 생각했다.

 

엑셀에서도 사용해보고 싶어 산업기사책에 나온 코드를 c java 를 vba로 변환해서 해보았고

네이버와 차이가 있어 3가지 형식으로 코드를 만들어 봤다.

 

1. do while ~ Loop

2. do ~ Loop while

3. i = Letf +1 , j =Right 와

   i = Letf 1 , j =Right +1

 

 

실행해보면서 동작순서가 생각한거랑 달랐다.

24번째줄 코드가 동작하고 25번째로 실행 할줄았았는데

24번째의 정렬이 완성이 안되면 그안의 퀵정렬이 다시 동작해  25번째로 안가는걸 알았다.

 

퀵정렬이 정렬 알고리즘중에 가장 빠르다고해서 퀵정렬이라고 불린다 한다.

좋은거 알아간다고 생각하고, 만약 재귀호출없이 만들 수 있을까란 생각을 해보지만.. 머리가 아파온다. 

짧게 쓰느라 이해가 안될 수 있으니 다른 곳을 참고하는것도 좋을거 같다. 

QSORT.xlsm

0.17MB