push_swap 퀵소트 피봇 구하기

퀵소트 공부

• ‘찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)’가 개발한 정렬 알고리즘
• 퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
• 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법
• 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다.
• 분할 정복 방법
  • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
  • 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog

 

퀵소트는 pivot을 하나 잡고 빠르게 정렬을 하는 알고리즘이다.

그런데 우리 과제에서 pivot을 하나만 잡고 정렬을 해버리면 명령어 개수가 너무 많아져서 큰일남..

→ push_swap은 정렬을 하기 위한 명령어 개수로 평가를 하게 됨.

그래서 pivot을 2개 잡고 하는 것임

• pivot을 2개 잡는 방법을 다양하게 있다
  • 내 친구 중에 잘생긴 친구 한 명 있는데 그 친구는 전체 길이 중에 반을 pivot을 잡고 나머지 하나는 그 반의 반을 잡고 접근을 하였음
    • 쉽게 말해서 전체 길이가 10이면 5 지점을 pivot으로 잡음 그리고 5지점에서 반인 2 아니면 3으로 pivot을 잡음.
  • 나는 전체 길이 중에 3분의 1 지점 3분의 2지점으로 잡았다.

나의 알고리즘을 대충 간략히 설명해보쟈

• 일반적인 퀵소트는 재귀를 타면서 정렬을 함 거기에 맞게 우리도 잡야아함
  • 그래서 a_to_b, b_to_a 함수 2개를 만들어서 재귀를 계속 돌 것임
• pivot을 2개 잡는다는 말은 3구역으로 나눌 수 있음
  • pivot1는 큰 놈 즉 3분의 2지점
  • pviot2는 작은 놈 즉 3분의 1지점

3구역으로 나뉨

1. pivot1 크거나 같은 놈들은 전체 중에서 제일 큰놈
2. pivot1과 pivot2에 있는 중간 놈
3. pivot2보다 작은 놈

→ 여기서 사람들은 많은 고민을 할 것이다. 데이터들 중에 pivot값을 정할텐데 pivot1, 2를 포함시켜야 하나? 아니면 포함시키지 말아야 하나 이것에 대한 답변은 자기가 해보고 싶은대로 하면 된다. 하지만 그것을 잘 알아야한다. 퀵소트는 pivot값에 따라 속도가 달라진다는 것을 그래서 아무렇게나 해보고 난중에 최적화 할 때 잘 생각해보면 됨.

최적화? == 정렬을 하기 위한 명령어 개수를 줄이는 것

이제 함수를 통해 설명해보쟈

아까 내가 a_to_b, b_to_a에 대해 설명했는데 좀 자세히 설명해보자

1. a_to_b

위에서 pivot을 2개 잡았기 때문에 3구역으로 나뉜다고 했는데

입력값이 1 4 3 2으로 가정한다면 밑에 그림처럼 나올 것이다.

1
4
3
2
_ _
a b

• 그러면 나의 pivot1은 3 pivot2는 2임

이 기준을 포함해서 b스택에 넣을 것임

이제 a 스택에는 pivot1 보다(크거나 같은 경우도 됨) 크거나 만약 포함한다고 하면 a스택에는 3 4가 남고 b스택에는 2 1를 보낸다

• 그런데 2 1를 보낼 때 while문을 통해 하나씩 보내게 될 텐데 검사를 해야한다 중간놈들은 b스택에 밑에 가게 하고 작은 놈들은 위로 가게 만들면 된다. → 위로 보내거나 하는 연산은 명령어를 읽어보면 알 것이다.

그러면 그 구조가

큰놈들        작은 놈들
							중간 놈들
___________ _____________
a             b

이렇게 됨.

a스택에 값들 개수가 3개 이하 남을 때까지 a_to_b 재귀를 돌리면 됨.

그러면 a_to_b 함수 안에는

1. a_to_b
2. b_to_a
3. b_to_a

가 와야함.

어떤 인자값들을 넘겨줄지는 생각을 해봐야함.

1. b_to_a

그러면 a_to_b 재귀가 끝났다고 봤을 때 큰놈들은 정렬된 상태가 되어있을 것이다.

 

b_to_a는 아까 a_to_b에서 보내준 친구들의 값들 개수가 3 이하면 정렬을 하면서 보내주면 되고 3이하가 아니면 새로운 pivot들을 구해서 a에 밑, 위에 올려놓고 정렬을 하면 된다.

a_to_b의 구조를 비슷하게 따라가면 된다.

 

다음 글에서 좀 더 세세하게 보자

 

-jaeyojun-