sort (select/bubble/quick/merge/radix)

선택정렬 (select)

• 최소값의 인덱스를 저장 후 맨 앞으로 보냄
• 시간복잡도 O(N^2)

3 2 7 8 4 5 1 6 / 최소값 - 1

1 2 7 8 4 5 3 6 / 최소값 - 2 (변동 없음) / 최소값 - 3

1 2 3 8 4 5 7 6 / 최소값 - 4

1 2 3 4 8 5 7 6 / 최소값 - 5

1 2 3 4 5 8 7 6 / 최소값 - 6

1 2 3 4 5 6 8 7 / 최소값 - 7

1 2 3 4 5 6 7 8 

---

버블정렬

• 앞, 뒤의 수를 비교하여 작은 값을 앞으로 보냄
• 최대값은 한 번 돌 경우, 무조건 끝 점에 도달하게 된다.
• 시간복잡도 O(N^2)

3 1 2 8 7 5 6 4

1 3 2 8 7 5 6 4

1 2 3 8 7 5 6 4

1 2 3 8 7 5 6 4

1 2 3 7 8 5 6 4 

1 2 3 7 5 8 6 4 

1 2 3 7 5 6 8 4

1 2 3 7 5 6 4 8

---

퀵정렬

• 포인트 되는 값을 골라서 그 값보다 작은 값을 왼쪽으로 큰 값을 오른쪽으로 보낸다.
• 한번 정렬된 값은 항상 고정된다.
• 포인트(=피벗)은 랜덤값을 잡거나, 중간값을 잡는다. -> O(logN)을 유지하기 위해
• 포인트를 최소 or 최대값으로 잡게 되면 시간복잡도가 O(N^2)가 되어버린다. / 시간복잡도가 가변적이다.
• T(N) = 2T(N/2) + N - 1회 돌았을 경우 ( 포인트 고르는 시간 + 포인트 기준으로 왼쪽 오른쪽 정렬하는 시간 )
        = 2(2T(N/4) + N/2) + N
        = 4T(N/4) + N + N
        = 4T(N/4) + 2N - 2회 돌았을 경우
        = 8T(N/8) + 3N - 3회 돌았을 경우
        = 2^kT(N/2^k) + KN - (N이 1이될 때 까지 반복하므로 2^k를 N으로 가정함)
        = NT(1) + log2N*N - (T(1)은 0)
        = log2N*N
• 시간복잡도 O(logN)

3 1 2 8 5 7 6 4

1 2 3 8 5 7 6 4 / 기준 - 3

1 2 3 5 7 6 4 8 / 기준 - 8

1 2 3 4 5 7 6 8 / 기준 - 5

1 2 3 4 5 6 7 8 / 기준 - 6

---

병합정렬

• 전부 나눴다가, 정렬하면서 다시 합친다.
• 2 Pointer 
  • 2,3의 2를 가리키고 있는 변수 a
  • 1,8의 1을 가리키고 있는 변수 b
  • a(2)와 b(1)를 비교한다. 
  • 1 - b가 더 작기 때문에, 1을 맨 앞으로 정렬해주고 b를 한 칸 움직여 8을 가리키게 한다.
  • a(2)와 b(8)를 비교한다.
  • 2 - a가 더 작기 때문에, 2를 1 뒤로 정렬해주고 a를 한 칸 움직여 3을 가리키게 한다.
  • a(3)과 b(8)을 비교한다.
  • 3 - a가 더 작기 때문에, 3을 2 뒤로 정렬해주고, 마지막 남은 8을 정렬해준다.
• 나누는 시간복잡도 O(N)
• 병합하는 시간복잡도 O(KN)
  1 * 2^k = N
  k = log2N
  O(logN)
  
  
• 시간복잡도가 고정적이다.

3 2 8 1 4 5 7 6

3 2 8 1  / 4 5 7 6

3 2 / 8 1 / 4 5 / 7 6

3 / 2 / 8 / 1 / 4 / 5 / 7 / 6

...

2 3 / 1 8 / 4 5 / 6 7 - 2 Pointer 사용

1 2 3 8 / 4 5 6 7 

1 2 3 4 5 6 7 8

---

radix정렬

• 배열을 만들어 하나씩 카운팅 하는 방법
• 범위가 짧거나 , 메모리가 충분할 때 사용

3 1 9 2 2 4 5 6

1 2 2 3 4 5 6 9