1 7 2 8 6 9 3 5 4
명칭이 quick sort라고 다 똑같은 방법은 아닌거 같음
중간값 예) 6을 선택하고 좌, 우에서 그 보다 큰 혹은 작은 수를 잡고 서로 바꿔 가는
방법이 있으나 선호하지 않음
내가 선호하는 방법은 첫 원소를 잡고 그 원소의 최종 자리를 찾을때 까지 비교 하는 것
시작
1번째 원소를 피봇으로 선택
1 7 2 8 6 9 3 5 4
9번째(마지막) 원소를 비교대상으로 선택
1 7 2 8 6 9 3 5 4
1 7 2 8 6 9 3 5 4 -> 1 과 4 비교 바꿀 필요 없음
비교대상 진행 방향 왼쪽
1 7 2 8 6 9 3 5 4 -> 1 과 5 비교 바꿀 필요 없음
1 7 2 8 6 9 3 5 4 -> 1 과 3 비교 바꿀 필요 없음
1 7 2 8 6 9 3 5 4 -> 1 과 9 비교 바꿀 필요 없음
1 7 2 8 6 9 3 5 4 -> 1 과 6 비교 바꿀 필요 없음
1 7 2 8 6 9 3 5 4 -> 1 과 8 비교 바꿀 필요 없음
1 7 2 8 6 9 3 5 4 -> 1 과 2 비교 바꿀 필요 없음
1 7 2 8 6 9 3 5 4 -> 1 과 7 비교 바꿀 필요 없음
1은 자리 확정!
1 7 2 8 6 9 3 5 4 -> 7 과 4 비교 바꿈
1 4 2 8 6 9 3 5 7 -> 비교대상 진행 방향 오른쪽
1 4 2 8 6 9 3 5 7 -> 7 과 2 비교 바꿀 필요 없음
1 4 2 8 6 9 3 5 7 -> 7 과 8 비교 바꿈
1 4 2 7 6 9 3 5 8 -> 비교대상 진행 방향 왼쪽
1 4 2 7 6 9 3 5 8 -> 7 과 5 비교 바꿈
1 4 2 5 6 9 3 7 8 -> 비교대상 진행 방향 오른쪽
1 4 2 5 6 9 3 7 8 -> 7 과 6 비교 바꿀 필요 없음
1 4 2 5 6 9 3 7 8 -> 7 과 9 비교 바꿈
1 4 2 5 6 7 3 9 8 -> 비교대상 진행 방향 왼쪽
1 4 2 5 6 7 3 9 8 -> 7 과 3 비교 바꿈
1 4 2 5 6 3 7 9 8 -> 비교대상 진행 방향 오른쪽
다음 비교대상 자기 자신이 되니까( 비교대상 없음 )
7번 자리 확정!!
1 4 2 5 6 3 7 9 8 -> 4 과 3 비교 바꿈
1 3 2 5 6 4 7 9 8 -> 비교대상 진행 방향 오른쪽
1 3 2 5 6 4 7 9 8 -> 4 과 2 비교 바꿀 필요 없음
1 3 2 5 6 4 7 9 8 -> 4 과 5 비교 바꿈
1 3 2 4 6 5 7 9 8 -> 비교대상 진행 방향 왼쪽
1 3 2 4 6 5 7 9 8 -> 4 과 6 비교 바꿀 필요 없음
다음 비교대상 자기 자신이 되니까( 비교대상 없음 )
4번 자리 확정!!
1 3 2 4 6 5 7 9 8 -> 3 과 2 비교 바꿈
1 2 3 4 6 5 7 9 8 -> 3 과 2 비교 바꿈
다음 비교대상 자기 자신이 되니까( 비교대상 없음 )
3번 자리 확정!!
1 2 3 4 6 5 7 9 8 -> 2 혼자있음 확정
2번 자리 확정!!
1 2 3 4 6 5 7 9 8 -> 6 과 5 비교 바꿈
1 2 3 4 5 6 7 9 8 -> 비교대상 진행 방향 오른쪽
다음 비교대상 자기 자신이 되니까( 비교대상 없음 )
6번 자리 확정!!
이런 식으로 자리가 확정 된 원소들은 칸막이 역할을 하게 돼
이 후 복잡함이 한결 줄어든다.
참고 영상 링크
시간복잡도 설명(링크)
O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.
O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.
O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형)
O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.
댓글 없음:
댓글 쓰기