cs공부 정렬 (selection)

오늘은 정렬에 대해서 공부해보겠다^^7

 

버블 정렬 (Bubble Sort)

버블 정렬은 서로 인접한 두 원소를 비교하여 정렬하는 알고리즘

시간 복잡도: O(n^2)

 

선택 정렬(Selection Sort)

선택 정렬은 첫 번째 값을 두번째부터 마지막까지 비교하여 최솟값을 찾아 첫 번째에 놓고

두번째도 동일한 과정을 반복하여 정렬하는 알고리즘

시간 복잡도: O(n^2)

 

삽입 정렬(Injection Sort)

삽입 정렬은 두 번째 값부터 시작해서 그 앞에 존재하는 원소들과 비교해 삽입할 위치를 찾아서 삽입하는 정렬

시간복잡도: O(n^2) 

힙 정렬(Heap Sort)

힙 정렬은 주어진 데이터를 힙 자료구조를 만들어 min 또는 max부터 하나씩 꺼내서 정렬하는 알고리즘

시간 복잡도: O(nlogn)

병합 정렬(Merge Sort)

병합 정렬은 주어진 배열을 크기가 1인 배열로 분할하고 합병하면서 정렬하는 알고리즘

시간 복잡도: O(nlogn)

퀵 정렬(Quick Sort)

피봇을 설정하고 피봇보다 큰 값과 작은 값으로 분할하여 정렬하는 알고리즘

시간 복잡도: O(nlogn) 

=> 정렬된 상태일 때 성능이 급격하게 떨어진다.

계수 정렬 (Count sort)

계수 정렬이란 최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬하는 알고리즘

시간 복잡도: O(n + k) (k는 배열의 최댓값)

=> count 배열은 index i 번째는 i까지 누적횟수를 저장 (ex c[3] 은 0~3까지 4번(3, 1, 2, 2) 나왔기 때문에 4임)

arr[i] 가 정렬됐을 때 몇번째 인지 알려면 arr[i] 값을 index로 하여 count 배열의 값이 몇번째인지 나타냄 

result에 값을 넣은 후에는 count 값을 감소

 

기수 정렬(Radix sort)

기수 정렬은 자리수를 기준으로 정렬하는 알고리즘

시간 복잡도: O(w * n) (w는 자릿수)

정렬 알고리즘 시간 복잡도 비교 표

 

 

참고: https://dev-coco.tistory.com/160

https://velog.io/@wjdqls9362/Algorithm-%EC%A0%95%EB%A0%AC-Radix-sort-Counting-sort