이 페이지는 푸쉬스왑 프로젝트 안에 있는 모든 명령어와 목표 그리고 스택이 어떻게 되어있는지 알고 있다는 전제하에 이해할 수 있도록 만들었습니다. 그러니 우선 서브젝트를 읽고 어떤 명령어들이 있는지 그리고 인자를 어디에 넣는지 어떻게 작동하여 뭘 해야하는지 등을 읽어오신 후에 봐주세요.
주제는 퀵소트와 이를 서브젝트와 어떻게 연결시키는냐 입니다. 이 프로젝트를 해결할 수 있는 알고리즘은 많이 있을 겁니다. 하지만, 알고리즘을 이해하고 해결하기 적당한 것이 이 퀵소트를 이용한 알고리즘이라고 판단되어 저는 퀵소트를 이용하였습니다.
퀵소트(Quick sort)
퀵소트란 정렬 알고리즘 중에 하나입니다. 퀵소트에는 피봇(pivot)이라는 것이 있습니다. 퀵소트 정렬은 이 피봇을 기준으로 피봇 왼쪽에는 피봇보다 작은수, 오른쪽에는 피봇보다 큰 수를 정렬하는 것입니다. 피봇의 기준은 정해진 것이 없이 개발자의 마음입니다. 자신이 생각했을때 가장 효율적이다고 생각되는 위치를 피봇으로 정하면 됩니다.
예시를 들겠습니다.
3 7 4 6 1 5 2
이렇게 정렬이 있다고 가정하겠습니다. 여기서 피봇과 비교할 대상을 정할 겁니다. 저는 여기서 피봇을 첫번째 인덱스 값으로 생각해보겠습니다. 그러니까 7을 피봇으로 잡아보겠습니다. 그 후에 피봇이 있는 위치와 그리고 마지막 위치를 생각하며 봅시다.
3 7 4 6 1 5 2
▲ ▲
마지막 수와 피봇(3)를 비교했을 때 2는 피봇보다 작은데 피봇보다 오른쪽에 있습니다. 그러므로 스왑을 해줍니다.
2 7 4 6 1 5 3
▲ ▲
스왑 후에 다음 위치는 비교했던 대상이 피봇보다 왼쪽에 있으면 한칸 오른쪽으로 비교했던 대상이 피봇보다 오른쪽에 있으면 왼쪽으로 한칸 이동합니다. 여기서는 비교했던 대상(2)이 피봇(3)보다 왼쪽에 있으므로 오른쪽으로 한칸 이동한 위치(7)를 보겠습니다. 7은 3보다 큰데 피봇보다 왼쪽에 있습니다. 그러므로 스왑을 해줍니다.
2 3 4 6 1 5 7
▲ ▲
스왑 후에 다음 위치는 비교했던 대상(7)이 피봇보다 오른쪽에 있으므로 왼쪽으로 한칸 이동한 위치(5)를 보겠습니다. 5는 3보다 큰데 피봇보다 오른쪽에 있습니다. 그러므로 아무것도 안하고 위치를 한칸 더 왼쪽으로 이동합니다.
2 3 4 6 1 5 7
▲ ▲
1은 3보다 작은데 피봇보다 오른쪽에 있습니다. 그러므로 스왑해줍니다.
2 1 4 6 3 5 7
▲ ▲
스왑 후에 비교했던 대상(1)이 피봇보다 왼쪽에 있으므로 위치를 오른쪽으로 한칸 이동해(4) 비교합니다. 4는 3보다 큰데 왼쪽에 있으므로 스왑합니다.
2 1 3 6 4 5 7
6은 3보다 큰데 오른쪽에 있기때문에 아무것도 안합니다. 이제 정렬이 끝났습니다.
2 1 | 3 | 6 4 5 7
위 그림처럼 왼쪽은 피봇보다 작은 수, 오른쪽은 피봇보다 큰 수로 나누어 정렬이 되었습니다. 이제 이 다음은 나눈 왼쪽과 오른쪽 영역에 각각 피봇을 정해 또 나눕니다. 첫번째 수를 피봇으로 두었으니 각각 2와 6이 되겠네요. 그 후에 자기들 영역에서 퀵소트를 합니다.
1 2 | 3 | 6 4 5 7
1 2 | 3 | 5 4 | 6 | 7
그림처럼 왼쪽은 정렬이 끝났고 오른쪽은 또 피봇을 기준으로 나누어 졌습니다. 이런식으로 반복하여 마지막에
1 2 3 4 5 6 7
이렇게 정렬시키는 것이 퀵소트입니다.
만약에 위 글을 봤는데 이해가 잘 안된다면 아래 영상을 참고하시면 이해하기 훨씬 편할 것입니다.
그럼 이제 이 알고리즘을 푸쉬스왑에 적용시켜 볼 것입니다.
