QuickSort

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 제곱.

ShellSort

1 7 2 8 6 9 3 5 4

insert sort는 바로 앞에꺼와 비교했다면
shell sort 는 바로 앞이 아닌 인터벌을 두고 비교
저 뒤에 잘못 배치된 놈이 한방에 제자리로 갈수도 있는 효율적 상황을 기대해 보자!

고로 비교 간격 설정부터!

참고사이트

Donald Shell은 처음에 간격을 2^k, (k는 0 이상의 자연수) 혹은 2^k-1로 잡았으며,

Marcin Ciura의 연구에 의하면  1, 4, 10, 23, 57, 132, 301, 701, 1750 ... 과 같은 간격을 사용하는 것이 

연산 시간을 많이 줄인다고 한다.

참고사이트2
h(1) = 1;
h(i+1) = 3* h(i) + 1; 을 거쳐 나온 1, 4, 13, 40, 121, 364, 1093, 3280...순
잘 알려진 optimal sequence로 다음 두 가지를 알아두자.
1. Sedgewick : 1 3 7 21 48 112 336 861 1968 4592
2. Papernov-Stasevic : 1 3 7 15 31 63 127 255 511 1023 2047


여기서는 비교간격 k = n/2 = 9/2 = 4

1 7 2 8 6 9 3 5 4

>Step 1 ( k=4 )

1 7 2 8 // 6 9 3 5 // 4      -> 1 과 6 비교 바꿀 필요 없음
1 7 2 8 // 6 9 3 5 // 4      -> 6 과 4 비교 바꿈
1 7 2 8 // 4 9 3 5 // 6

1 7 2 8 // 4 9 3 5 // 6      -> 7 과 9 비교 바꿀 필요 없음

1 7 2 8 // 4 9 3 5 // 6      -> 2 과 3 비교 바꿀 필요 없음

1 7 2 8 // 4 9 3 5 // 6      -> 8 과 5 비교 바꿈
1 7 2 5 // 4 9 3 8 // 6

>Step 2 ( k=2 )

1 7 // 2 5 // 4 9 // 3 8 // 6     -> 1 과 2 비교 바꿀 필요 없음

1 7 // 2 5 // 4 9 // 3 8 // 6     -> 2 과 4 비교 바꿀 필요 없음  

1 7 // 2 5 // 4 9 // 3 8 // 6     -> 4 과 3 비교 바꿈
1 7 // 2 5 // 3 9 // 4 8 // 6
1 7 // 2 5 // 3 9 // 4 8 // 6     -> 4 과 6 비교 바꿀 필요 없음

1 7 // 2 5 // 3 9 // 4 8 // 6     -> 7 과 5 비교 바꿈
1 5 // 2 7 // 3 9 // 4 8 // 6
1 5 // 2 7 // 3 9 // 4 8 // 6     -> 7 과 9 비교 바꿀 필요 없음
1 5 // 2 7 // 3 9 // 4 8 // 6     -> 9 과 8 비교 바꿈
1 5 // 2 7 // 3 8 // 4 9 // 6

>Step 3 ( k=1 ) !! 여기서 부터는 Insert Sort
1 5 2 7 3 8 4 9 6                   -> 1 과 5 비교 바꿀 필요 없음

1 5 2 7 3 8 4 9 6                   -> 5 과 2 비교 바꿈
1 2 5 7 3 8 4 9 6
1 2 5 7 3 8 4 9 6                   -> 1 과 2 비교 바꿀 필요 없음

1 2 5 7 3 8 4 9 6                   -> 5 과 7 비교 바꿀 필요 없음

1 2 5 7 3 8 4 9 6                   -> 7 과 3 비교 바꿈
1 2 5 3 7 8 4 9 6
1 2 5 3 7 8 4 9 6                   -> 5 과 3 비교 바꿈
1 2 3 5 7 8 4 9 6
1 2 3 5 7 8 4 9 6                   -> 2 과 3 비교 바꿀 필요 없음

다음은 8 그 다음은 4 그 다음은 9 순으로 비교
참고 영상 링크 
영상은 스타일이 좀 다릅니다

InsertSort

1 7 2 8 6 9 3 5 4

두번째 원소부터 시작

>step 1
  ↓
1 7 2 8 6 9 3 5 4      -> 1 과 7 비교 바꿀 필요 없음

>step 2
     ↓
1 7 2 8 6 9 3 5 4      -> 2 와 7 비교 바꿈
  ↓
1 2 7 8 6 9 3 5 4      -> 2 와 1 비교 바꿀 필요 없음

>step 3
       ↓
1 2 7 8 6 9 3 5 4      -> 8 과 7 비교 바꿀 필요 없음

>step 4
          ↓
1 2 7 8 6 9 3 5 4      -> 6 과 8 비교 바꿈
       ↓
1 2 7 6 8 9 3 5 4      -> 6 과 7 비교 바꿈
     ↓  
1 2 6 7 8 9 3 5 4      -> 6 과 2 비교 바꿀 필요 없음

>step 5 는 9부터 시작
.... 이런 식으로
참고 영상 링크