알고리즘 이해
이전 글의 방법 2 알고리즘의 동작 원리를 다시 이해해보자.
누가 볼지 모르겠지만.. hoxy 본다면 꼬옥 먼저 생각해보고 이해하려고 노력도 많이 해본 뒤에 읽기..~
이게 도움이 될지도 모르겠지만.. hoxy나 해서.. (^_^)a
동작원리
(정렬된 부분은 빨간색, 나머지 색은 정렬되지 않은 부분이다. 정렬되지 않은 부분도 구분이 필요한 경우가 있어서 색을 여러 개 사용했다.)
스택 a에 1부터 80까지 숫자 80개가 들어왔다고 가정해보자.
처음에는 다음 그림처럼 들어왔을 것이다.
a_to_b()부터 시작한다.
처음에는 40개의 노드에 대해 검사한다.
이전 글에서 a_to_b와 b_to_a의 3, 4번을 과정 ①, 5번을 과정 ②라고 하겠다.
현재 피봇은 10과 20으로 정한다.
과정 ①까지 하고 나면 다음 그림처럼 된다.
과정 ②를 하면 다음 그림처럼 된다.
이제 재귀적으로 함수를 호출할 차례이다.
이 다음에 함수를 세 번 호출한다. a_to_b(ra 횟수)를 함수 ①, b_to_a(rb 횟수)를 함수 ②, b_to_a(pb 횟수 - rb 횟수)를 함수 ③이라고 하겠다.
먼저 함수 ①로 가면 위의 과정을 반복하게 된다.
여기서 피봇은 25과 30으로 정한다.
과정 ①을 하면 다음 그림처럼 된다.
과정 ②를 하면 다음 그림처럼 된다.
또 다시 재귀적으로 함수를 호출할 차례이다.
여기서 호출할 함수는 함수 ①-①, 함수 ①-②, 함수 ①-③이라고 하겠다.
함수 ①-①로 가면 또 다시 위의 과정을 반복하게 된다.
여기서 피봇은 32와 35으로 정한다.
과정 ①을 하면 다음 그림처럼 된다.
과정 ②를 하면 다음 그림처럼 된다.
또 또 다시 재귀적으로 함수를 호출할 차례이다. 아휴
여기서 호출할 함수는 함수 ①-①-①, 함수 ①-①-②, 함수 ①-①-③이라고 하겠다.
함수 ①-①-①로 가면 또 또 다시 위의 과정을 반복하게 된다.
여기서 피봇은 36과 37로 정한다.
과정 ①을 하면 다음 그림처럼 된다.
과정 ②를 하면 다음 그림처럼 된다.
아놔 4개가 남아버렸네. 또 또 또 다시 재귀적으로 함수를 호출할 차례이다.
어우 헷갈려. 여기서 호출할 함수는 ①-①-①-①, 함수 ①-①-①-②, 함수 ①-①-①-③이라고 하겠다.
함수 ①-①-①-①로 가면 또 또 또 다시 위의 과정을 반복하게 된다.
여기서 피봇은 37, 38로 정한다.
과정 ①을 하면 다음 그림처럼 된다.
과정 ②를 하면 다음 그림처럼 된다.
그리고 다시 재귀 어게인. 여기서 호출할 함수는 함수 ①-①-①-①-①, 함수 ①-①-①-①-②, 함수 ①-①-①-①-③이라고 하겠다.
이제 함수 ①-①-①-①-①에 들어가면 이제 스택 a에 남은 노드가 3개니까 정렬하고 끝난다.
그러면 이제 다음과 같이 된다. (정렬된 부분은 빨간색!)
이제 함수 ①-①-①-①-②로 간다. 먼저 37만 보내면 되니까 스택 a로 보내고 끝난다. 다음과 같이 된다.
이번에는 함수 ①-①-①-①-③으로 간다. 여기서는 할 게 없습니다. 휴
이제 함수 ①-①-①-①은 끝! 함수 ①-①-①-②로 갑니다. 여기서는 36만 보내면 되니까 스택 a로 보내고 끝난다. 다음과 같이 된다.
그럼 이제 함수 ①-①-①-③으로 간다. 여기서도 35만 보내면 되니까 스택 a로 보내고 끝난다. 다음과 같이 된다.
이제 함수 ①-①-①도 끝이다! 이제 함수 ①-①-②로 갑니다. 여기서 32~34가 3개이기 때문에 정렬하고 스택 a로 보내고 끝난다. 다음과 같이 된다.
그럼 이제 함수 ①-①-③으로 간다. 여기서 30~31가 2개니까 정렬하고 스택 a로 보내고 끝난다. 다음과 같이 된다.
이제 함수 ①-①도 끝! 함수 ①-②로 갑니다.
여기서 25~29가 5개이다. 피봇은 26과 27로 정한다.
과정 ①을 하면 다음 그림처럼 된다.
과정 ②를 하기 전에, b_to_a()에서는 a_to_b(pa 횟수 - ra 횟수)를 해준다. 이를 함수 ①-②-①이라고 하겠다.
여기서 27~79가 3개니까 정렬하고 끝난다. 다음과 같이 된다.
이제 과정 ②를 하면 다음 그림처럼 된다.
그리고 또 함수를 호출하게 되는데, a_to_b(rb 횟수)를 ①-②-②, b_to_a(ra 횟수)를 ①-②-③이라고 칭하겠다.
먼저 함수 ①-②-②로 간다. 여기서는 26으로 한 개니까 정렬하고 끝난다. 다음과 같이 된다.
이제 함수 ①-②-③으로 간다. 여기서도 25로 한 개니까 정렬하고 스택 a로 보내고 끝난다. 다음과 같이 된다.
함수 ①-②도 끝이다. 이제 함수 ①-③으로 간다.
여기서는 20~24니까 5개이다. 피봇은 21과 22로 정한다.
과정 ①을 하면 다음 그림처럼 된다. (너무 길어져서 스택 a를 좀 줄였다.)
역시 과정 ②를 하기 전에 함수 ①-③-①로 간다.
여기서는 22~24가 3개니까 정렬만 해주고 끝난다. 다음과 같이 된다.
과정 ②를 하면 다음 그림처럼 된다.
그리고 함수 ①-③-②로 간다. 여기서 21로 한 개니까 정렬하고 끝난다. 다음과 같이 된다.
이제 함수 ①-③-③으로 간다. 여기서도 20으로 한 개니까 정렬하고 스택 a로 보내고 끝난다. 다음과 같이 된다. (또 너무 길어서 스택 a를 좀 줄였다.)
함수 ①-③도 끝이다. 그럼 이제 함수 ①도 끝이다. 함수 ②로 간다.
여기서는 10~19로 10개이다. 피봇은 12와 14로 정한다.
과정 ①을 하면 다음 그림처럼 된다.
