[카운팅 정렬과 퀵정렬]

1. 카운팅 정렬

 

1.  숫자가 등장한 횟수 를 다른 한가지의 배열에 넣는다

2. 다른 한가지의 배열의 누적합으로 값을 update해준다.

3. 기존 숫자들이 있던 배열 마지막부터, 새로 생성한 배열을 보면서, 정렬 index를 찾는다

ex. 4가 5번 등장하면, arr[5] =4 이런식으로 (만약 중복되는 값이 있어, index에 값이 이미있다면, -1 을 해준다.)

 

이해가 잘되는 애니메이션 링크

https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html

Counting Sort

 

 

2.퀵 정렬

일반적으로 더 빠르다.

 

퀵정렬은 우선 배열의 0번째를 pivot으로 둔다.

그리고, 2개의 포인터를 둔다 (흔히 high, low로 사용한다.)

해당 high는 오른쪽 끝 low는 왼쪽 끝에서 부터 서로 엇갈릴때까지 Pivot보다 작은수, 큰 수를 찾 고 (high에서는 작은수, low에서는 큰수)찾게되면 이 두개의 값을 바꿔준다.

 

최종적으로 엇갈리면 high 즉, 마지막으로 세팅된 작은값과 pivot을 바꿔준다. (내림 차순의 경우)

 

이렇게 되면 pivot 기준으로 배열이 두개로 쪼개지게 되는데 이 쪼개 진 배열에서도 같은 과정을 반복한다.

반복하면서 계속 정렬이 된다면, 다시 이걸 합쳐주면서 마무리를 한다.