소개글
면접 대비겸 여러 블로그들을 참고하면서 정리해본 CS 지식들을 포스팅하고 있습니다.
만약 틀린 내용이 있다면 피드백은 언제나 환영합니다.
제 나름대로 요약한 내용이기 때문에 자세한 내용은 제일 아래쪽 참고 사이트에서 확인하면 좋을 것 같습니다!
말투는 편한 말투로 작성하니 양해 부탁드립니다.
정렬
O(nlogn) 알고리즘이 O(n^2) 알고리즘보다 무조건 좋다고는 할 수 없음
- n이 작으면 시간 차이는 거의 없음
- 공간 복잡도가 더 클 수도 있음
- 분할하는 알고리즘의 경우 재귀적으로 분할 함수를 호출하는게 더 비용 클수도 있음
in-place → 원소의 개수(n)에 비해 무시할 만큼의 저장 공간만 더 사용하는 것
not-in-place → n에 비례하여 저장 공간을 사용하는 것
stable → 중복된 값이 있을 때 정렬 전과 후에 이 값들의 순서가 동일함
unstable → 순서가 바뀔 수 있음
Bubble Sort (거품 정렬)
- 서로 인접한 두 원소를 비교하고 자리를 교환하며 정렬
- 비교 횟수도 많고 실제로 교환하는 횟수도 많음
특징
in-place, stable, comparison
시간복잡도
최선, 평균, 최악 - O(n^2)
공간복잡도
O(1)
Selection Sort (선택 정렬)
- 원소를 넣을 위치는 정해져있고, 어떤 원소를 넣을지 쭉 살펴보고 선택 및 교환하여 정렬
- 어떤 원소를 넣을지 볼 때, 무조건 전부 살펴봐야함 (최솟값 / 최댓값 선택)
- 비교 횟수는 많지만 실제로 교환하는 횟수는 적음
특징
in-place, unstable, comparison
시간복잡도
최선, 평균, 최악 - O(n^2)
공간복잡도
O(1)
Insertion Sort (삽입 정렬)
- 원소를 차례대로 살펴보면서 넣을 위치를 정하고 삽입하여 정렬
- 위치를 정할 때, 1개만 살펴봐도 되는 경우가 있을 수 있음 (정렬되어있다면)
- 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적임
특징
in-place, stable, comparison
시간복잡도
평균, 최악 - O(n^2)
최선 - O(n)
공간복잡도
O(1)
Quick Sort (퀵 정렬)
- pivot을 선택하여 왼쪽에는 pivot보다 작은 수, 오른쪽은 큰 수만 있게 하여 정렬 (오름차순일때)
- pivot 값을 잘 선택해야함 (첫번째, 중간, 마지막, 랜덤 등)
- 양끝에서 각각 이동하면서 왼쪽에서 pivot보다 큰 수나 pivot, 오른쪽에서 pivot보다 작은 수나 pivot을 만났다면 멈추고 서로 교환
- left가 right보다 커지면 이동 멈춤
- pivot 값을 제외하고 분할하고 반복 (pivot 값은 자기 위치 찾은 거임)
특징
in-place, unstable, comparison
시간복잡도
최선, 평균 - O(nlogn)
최악 - O(n^2)
공간복잡도
O(nlogn) - 재귀 호출로 인한 스택 메모리 공간
Merge Sort (병합 정렬)
- 요소를 전부 쪼갠 뒤, 순서를 맞춰서 병합해나가며 정렬
- DB에서 많이 쓰임 (빅데이터를 정렬하고 싶은데 한정된 메모리로는 힘들기 때문에 쪼개서 정렬)
특징
not-in-place, stable, comparison
시간복잡도
최선, 평균, 최악 - O(nlogn)
공간복잡도
O(n) - 병합할 장소로 사용할 새로운 배열을 생성해줘야함
Heap Sort (힙 정렬)
- 힙 자료구조를 기반으로 루트 값을 하나씩 빼내면서 정렬
- 빼낸 후 루트를 마지막 노드로 대체하고 heapify
- 최솟값이나 최댓값을 구할 때 유용
특징
in-place, unstable, comparison
시간복잡도
최선, 평균, 최악 - O(nlogn)
공간복잡도
O(1) - 힙은 Array에 저장 가능
Radix Sort (기수 정렬)
- 각 자릿수를 비교하며 정렬
- 문자열, 정수와 같이 자릿수가 있는 데이터만 정렬 가능
- 숫자일 경우 10개의 버킷을 놓고 특정 자릿수의 값을 인덱스로 하여 버킷에 집어넣음
ex) [일의 자릿수] 92, 142 → 2번 버킷 - 버킷 순서대로 정렬하고 다음 자릿수로 이동해서 반복
LSD(Least Significant Digit)
- 일의 자리부터 정렬
- 모든 자릿수의 정렬이 끝나야 확인 가능
- 주로 쓰는 방식
MSD(Most Significant Digit)
- 끝자리부터 정렬
- 점진적으로 정렬을 해나가므로 중간에 정렬을 마칠 수도 있음
- 괜히 끝까지 정렬하다가 오히려 정렬이 이상하게 됨
- 그래서 매번 정렬이 됐는지 확인 과정이 필요함
특징
not-in-place, stable, non-comparison
시간복잡도
최선, 평균, 최악 - O(dn)
d는 자릿수
공간복잡도
O(n)
Count Sort (계수 정렬)
- 원소의 개수를 세어서 정렬
- 원소의 최댓값을 사이즈로 하는 배열(A)이 필요함 → 배열 값의 범위가 작을 경우 주로 사용
- 원소 값 = A의 인덱스로 하여, 각 원소의 개수를 A의 값으로 집어넣음
- A를 누적합 배열(B)로 바꿈
- 원래 원소 배열을 돌면서 원소 값 = B의 인덱스로 하여, B에 들어있는 값을 정렬 위치로 함
(B값을 조회했으면 1을 빼줌)
특징
not-in-place, stable, non-comparison
시간복잡도
최선, 평균, 최악 - O(n)
공간복잡도
O(K)
K는 원소 최대값
참고 사이트
https://velog.io/@kerri/알고리즘-Sorting-알고리즘-선택-버블-삽입-합병-퀵-소트-힙-소트-비교
https://code-lab1.tistory.com/24
https://hyo-ue4study.tistory.com/68
https://nomad-programmer.tistory.com/390
https://soobarkbar.tistory.com/101
