push_swap에서 정렬해야할 숫자가 2,3,4,5개 일때의 정렬하는 방법
구현
int start_sort(t_deque *deq_a, t_deque *deq_b) { int node; if (deq_a->first == deq_a->last) return (0); node = is_sorted(deq_a); // 정렬된 상태라면 1 반환, 정렬되지 않았다면 노드의 갯수를 반환해 줌 if (node == 1) return (0); else if (node == 2) do_sa(deq_a); else if (node == 3) sort_3(deq_a); else if (node == 4) sort_4(deq_a, deq_b); else if (node == 5) sort_5(deq_a, deq_b); return (0); }
2개일 때
정렬해야할 수가 2개이고 현재 정렬되지않은 상태일때에는 두개의 숫자의 자리를 바꾸는 sa를 한번만 실행해주면 됨
예시
{2, 1} = sa{1, 2}
3개일 때
int sort_3(t_deque *deq) { t_node *curr; curr = deq->first->next; if (deq->first->num > curr->num) // 첫번째 값이 두번째 값보다 크다면{3, 2, 1} { curr = curr->next; if (deq->first->num > curr->num) // 첫번째 값이 세번째 값보다 크다면 {3, 2, 1} do_ra(deq); // 첫번째 값을 가장 뒤로 보내줌 {2, 1, 3} curr = deq->first->next; if (deq->first->num > curr->num) // 현재의 첫번째 값이 두번째 값보다 크다면 {2, 1, 3} do_sa(deq); // 첫번째값과 두번째값의 위치를 바꿔줌 {1, 2, 3} } else // 첫번째값이 두번째값보다 작다면 {1, 3, 2} { if (curr->num < curr->next->num) // 두번째 값이 세번째 값보다 작다면 (현 상황에선 이미 정렬 완료) do_sa(deq); // 첫번째 값과 두번째 값을 바꿔줌 else if (curr->num > curr->next->num) // 두번째 값이 세번째 값보다 크다면 {1, 3, 2} { do_rra(deq); // 마지막 값을 첫 값으로 올려줌 {2, 1, 3} if (deq->first->num > deq->first->next->num) // 현재 첫 값이 두번째 값보다 크다면 do_sa(deq); // 첫 값과 두번째 값을 바꿔줌 {1, 2, 3} } } return (0); }예시
{2, 3, 1} = rra{1, 2, 3}
{1, 3, 2} = rra{2, 1, 3} -> sa{1, 2, 3}
{3, 2, 1} = ra{2, 1, 3} -> sa{1, 2, 3}
{2, 1, 3} = sa{1, 2, 3}
4개일 때
int sort_4(t_deque *deq_a, t_deque *deq_b) { int min; t_node *curr; min = deq_a->first->num; curr = deq_a->first; while (curr) // 최소값을 찾기위해 처음부터 끝까지 반복 { if (min > curr->num) min = curr->num; // 현재 값보다 작은 값이 나오면 최소값 변경 curr = curr->next; } while (deq_a->first->num != min) // 최소값이 가장 앞으로 올때까지 반복 {3, 2, 1, 4} do_ra(deq_a); // first->num이 최소값이 아니라면 first를 last로 보내줌 {1, 4, 3, 2} if (is_sorted(deq_a) != 1) // 현재 정렬이 되지않은 상태라면 {1, 4, 3, 2} { do_pb(deq_a, deq_b); // 최소값인 first를 deq_b로 보내줌 {4, 3, 2} {1} sort_3(deq_a); // 정렬되지않은 deq_a를 sort_3으로 정렬해줌 {2, 3, 4} {1} do_pa(deq_a, deq_b); // b에있는 최소값을 a의 처음으로 보내줌 {1, 2, 3, 4} } return (0); }예시
- {2, 1, 3, 4}
ra{1, 3, 4, 2} -> pb{3, 4, 2}{1} -> rra{2, 3, 4}{1} -> pa{1, 2, 3, 4}- {2, 3, 4, 1}
ra{3, 4, 1, 2} -> ra{4, 1, 2, 3} -> ra{1, 2, 3, 4}- {1, 4, 2, 3}
pb{4, 2, 3}{1} -> ra{2, 3, 4}{1} -> pa{1, 2, 3, 4}- {4, 3, 2, 1}
ra{3, 2, 1, 4} -> ra{2, 1, 4, 3} -> ra{1, 4, 3, 2} -> pb{4, 3, 2}{1} -> ra{3,2,4}{1} -> sa{2, 3, 4}{1} -> pa{1, 2, 3, 4}
5개일 때
int sort_5(t_deque *deq_a, t_deque *deq_b) { int mid; int countpb; //pb를 실행한 횟수를 세는 카운트 countpb = 0; mid = find_mid(deq_a); // 5개의 노드들중 중간값을 찾아주는 함수 {4, 1, 3, 5, 2} while (countpb != 2) // pb가 2번 실행될 때 까지 반복 { if (deq_a->first->num >= mid) // 첫번째 값이 중간값보다 크거나 같다면 {4, 1, 3, 5, 2} do_ra(deq_a); // 첫번째값을 마지막으로 보내줌 {1, 3, 5, 2, 4} else // 첫번째 값이 중간값보다 작다면 { do_pb(deq_a, deq_b); // 첫번째 값을 deq_b로 보내줌 {3, 5, 2, 4}{1} countpb++; 카운트 증가 } } // 반복문 종료 시 {4, 3, 5} {1, 2} if (is_sorted(deq_a) != 1) // deq_a가 정렬된 상태가 아니라면 {4, 3, 5}{1, 2} sort_3(deq_a); // sort_3 사용해 정렬 {3, 4, 5}{1, 2} if (deq_b->first->num < deq_b->last->num) // deq_b의 첫값이 두번째값보다 작다면 {3, 4, 5}{1, 2} do_sb(deq_b); // deq_b의 첫 값과 두번째 값의 자리를 변경 {3, 4, 5}{2, 1} do_pa(deq_a, deq_b); // deq_b의 첫 값을 a의 첫값으로 보내줌{2, 3, 4, 5}{1} do_pa(deq_a, deq_b); // deq_b의 첫 값을 a의 첫값으로 보내줌{1, 2, 3, 4, 5} return (0); }예시
- {2, 4, 1, 5, 3}
pb{4, 1, 5, 3}{2} -> ra{1, 5, 3, 4}{2} -> pb{5, 3, 4}{1, 2} -> ra {3, 4, 5}{1, 2} -> sb {3, 4, 5}{2, 1} -> pa{2, 3, 4, 5}{1} -> pa{1, 2, 3, 4, 5}- {5, 4, 3, 2, 1}
ra{4, 3, 2, 1, 5} -> ra{3, 2, 1, 5, 4} -> ra{2, 1, 5, 4, 3} -> pb{1, 5, 4, 3}{2} -> pb{5, 4, 3}{1, 2} -> ra{4, 3, 5}{1, 2} -> sa{3, 4, 5}{1, 2} -> sb{3, 4, 5}{2, 1} -> pa{2, 3, 4, 5}{1} -> pa{1, 2, 3, 4, 5}
늅늅