정렬 알고리즘(선택, 삽입, 퀵, 계수)

싸피에서 알고리즘 스터디를 진행하게 되었다.

매주 한가지 알고리즘 주제에 대해서 공부하고 그 주제에 해당하는 문제를 풀어오는 형식이다.

첫주에는 정렬 알고리즘 중 특히, 선택, 삽입 , 퀵 , 계수 정렬에 대해서 공부해오기로 했다.

사실 내장 라이브러리에 있는 함수를 이용해 배열을 정렬하는 경우가 알고리즘 문제에 대부분인 것으로 알지만,

정렬 알고리즘에 대한 이해는 기본인 것 같다. 4가지 정렬에 대해서 정리해보겠다.

-선택 정렬: 모든 인덱스를 순회하며 제일 작은 수를 찾아 앞에 부터 정렬하는 알고리즘

장점: 자료 이동횟수가 미리 결정된다.

단점: 안정성 없음,

*안정정렬은 중복된 값(레코드)을 입력 순서와 동일하게 정렬하는 정렬 알고리즘의 특성(불안정정렬은 순서 보장못함)

-삽입 정렬: 두 번째 자료부터 시작하여 앞의 자료들과 비교하여 삽입할 위치를 찾는 작업을 반복하는 알고리즘

장점 : 안정한 정렬방법, 대부분 이미 정렬되어있는 경우 매우 효율적

단점 : 레코드 수와 크기가 클 경우 적합하지 않음.

-퀵 정렬 : 분할정복 알고리즘 이용하며 평균적으로 매우 빠른 수행속도의 성능이 나오는 정렬방법

*분할 정복(divide and conquer) 방법 :문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
장점: 속도가 빠름 O(nlogn)

단점: 정렬된 리스트에 대해서는 퀵정렬의 불균형 분할에 의해 오히려 수행시간이 많이 걸림

*불균형 분할을 방지하기 위해 피봇(기준 값)을 선택 할때, 리스트를 균등하게 분할 할 수 있도록 중간 값을 피벗으로 선택하는 등의 방법을 추가함

- 계수 정렬(Counting Sort): 모든 데이터를 한번씩 접근하면서 크기를 기준으로 갯수를 세서 정렬하는 알고리즘

장점 : O(n)의 시간복잡도를 갖음(레코드의 최대값이 크지 않을경우)

단점 : 일반적인 상황에서는 느리고 메모리 낭비가 심함. ex) 0,2,0,100,2,0 배열을 정렬하기 위해 누적합 배열의 길이를 100으로 잡는 낭비를 해야함.

Arrays.sort() 는 dual-pivot Quicksort 알고리즘을 사용하기 떄문에 평균 시간복잡도가 O(nlongn) 이기 떄문에 매우 빠른 알고리즘이지만 최악의 경우에는 O(n2) 이다.

하지만 Collections.sort() 는 Timsort알고리즘(합병 및 삽입정렬 섞은 알고리즘) 을 사용하는데 이는 최선의 경우 O(n) , 최악의 경우 O(nlogn)을 보장한다.