https://www.hackerrank.com/challenges/quicksort1/problem
Quicksort 1 - Partition | HackerRank
Perform the first step of Quicksort: partitioning an array.
www.hackerrank.com
Quicksort Partition 문제
Partition 할 때 두가지 방법이 있다.
첫번째는 배열을 새로 만들어서 그 곳에 partition을 하고 원래의 배열에 다시 복사하는 방법이다.
두번째는 inline 방식이다.
두 방식 모두 배열의 가장 첫번째 원소가 pivot이 되고 pivot과 다른 원소들을 비교하면서 pivot을 기준으로 작은 원소들은 오른쪽, 큰 원소들은 왼쪽에 넣어준다.
첫번째 방법으로 문제를 풀경우, 새로운 배열(B)의 처음을 가리키는 변수 i, 끝을 가리키는 원소 j를 설정해준다. for문을 이용해서 pivot과 다른 원소들을 비교하고 pivot보다 원소가 작으면 "B[i++]=원소" 를 해주고 pivot보다 원소가 크면 "B[j--] = 원소" 를 해준다. i가 j와 같아지면 이것은 비교할 원소가 없다는 뜻이고 여기에 pivot을 넣어주면 된다. 이것을 다시 원 배열에 복사하면 partition 문제가 풀린다.
inline 방식으로 문제를 풀어보았다.
inline 방식으로 문제를 풀때도 마찬가지로 i와 j 변수 두 개가 필요하다. i는 맨 처음(index start)을 j는 가장 끝+1(index end+1)을 가리킨다. do while 문을 이용하여 코드를 짜면된다.
do while문은 do 부분이 무조건 처음에 한번 시행되어야 하며 그다음에 while문안에 있는 조건문에 맞으면 시행하면된다.
가장 바깥쪽 do while문은 i<j동안 시행된다.
안쪽에 do while문이 2개가 있다. 첫번째 do while문은 i<=end && arr[i]<pivot일 동안 i++가 시행이 된다.
두번째 do while문은 j>=start && arr[j]>pivot일 동안 j--가 시행이 된다.
이 두가지가 멈출때는 보통 arr[i]>pivot일때와 arr[j]<pivot일 때이다. 따라서 i와 j에 있는 원소두개의 위치를 바꿔준다.
이런식으로 시행되다 보면 i>=j가 되게 되고 이러면 가장 바깥쪽 do while문도 종료를 한다.
pivot을 기준으로 작은건 왼쪽, 큰건 오른쪽에 배치되게 되는데 따라서 pivot과 j를 바꿔줘야 한다. 왜 j와 바꿔야 되냐면 j가 i보다 작아지고 이것은 j에 있는 원소가 pivot보다 작은 원소이기 때문이다.
https://www.hackerrank.com/challenges/quicksort1/problem
Quicksort 1 - Partition | HackerRank
Perform the first step of Quicksort: partitioning an array.
www.hackerrank.com
Quicksort Partition 문제
Partition 할 때 두가지 방법이 있다.
첫번째는 배열을 새로 만들어서 그 곳에 partition을 하고 원래의 배열에 다시 복사하는 방법이다.
두번째는 inline 방식이다.
두 방식 모두 배열의 가장 첫번째 원소가 pivot이 되고 pivot과 다른 원소들을 비교하면서 pivot을 기준으로 작은 원소들은 오른쪽, 큰 원소들은 왼쪽에 넣어준다.
첫번째 방법으로 문제를 풀경우, 새로운 배열(B)의 처음을 가리키는 변수 i, 끝을 가리키는 원소 j를 설정해준다. for문을 이용해서 pivot과 다른 원소들을 비교하고 pivot보다 원소가 작으면 "B[i++]=원소" 를 해주고 pivot보다 원소가 크면 "B[j--] = 원소" 를 해준다. i가 j와 같아지면 이것은 비교할 원소가 없다는 뜻이고 여기에 pivot을 넣어주면 된다. 이것을 다시 원 배열에 복사하면 partition 문제가 풀린다.
inline 방식으로 문제를 풀어보았다.
inline 방식으로 문제를 풀때도 마찬가지로 i와 j 변수 두 개가 필요하다. i는 맨 처음(index start)을 j는 가장 끝+1(index end+1)을 가리킨다. do while 문을 이용하여 코드를 짜면된다.
do while문은 do 부분이 무조건 처음에 한번 시행되어야 하며 그다음에 while문안에 있는 조건문에 맞으면 시행하면된다.
가장 바깥쪽 do while문은 i<j동안 시행된다.
안쪽에 do while문이 2개가 있다. 첫번째 do while문은 i<=end && arr[i]<pivot일 동안 i++가 시행이 된다.
두번째 do while문은 j>=start && arr[j]>pivot일 동안 j--가 시행이 된다.
이 두가지가 멈출때는 보통 arr[i]>pivot일때와 arr[j]<pivot일 때이다. 따라서 i와 j에 있는 원소두개의 위치를 바꿔준다.
이런식으로 시행되다 보면 i>=j가 되게 되고 이러면 가장 바깥쪽 do while문도 종료를 한다.
pivot을 기준으로 작은건 왼쪽, 큰건 오른쪽에 배치되게 되는데 따라서 pivot과 j를 바꿔줘야 한다. 왜 j와 바꿔야 되냐면 j가 i보다 작아지고 이것은 j에 있는 원소가 pivot보다 작은 원소이기 때문이다.
