정렬알고리즘이 뭔가요?
📚특정원소들을 사전처럼 일정한 순서대로 열거하는 알고리즘입니다.
왜중요하나요?
🔎탐색에 용이합니다.
정렬이 되지 않은 숫자에서 특정 숫자값을 찾으려면 결국 하나씩 탐색을 해야합니다.
하지만 정렬이된 숫자라면 훨씬 빨리 원하는 숫자를 찾을 수 있습니다.
종류에는 무엇이 있나요?
1. 버블정렬
인접한 두개의 요소를 비교해서 조건에 따라 위치를 교환해줍니다.
배열길이보다 1번 적게 비교가 일어나며 한번 정렬이 일어나면
마지막요소는 고정되므로 그 때마다 하나 더 적게 비교가 일어나게 됩니다.
두 요소를 비교하고 교환만 이루어지므로
가장 간단하고 쉬운 정렬방법이지만 최악의 경우 모든 요소를 교환해서
시간복잡도O(n^2)가 좋지 않습니다.
저는 왼쪽에서 오른쪽으로 정렬되는 상황만 있는지 궁금해졌습니다.
물론 반복문을 달리하면 오른쪽에서 왼쪽으로 정렬이 되겠지요
알아보니 일반적으로는 왼쪽에서 오른쪽으로 비교하고 교환하는 방식이 이루어진다고 합니다.
결론적으로 버블정렬은 인접한 두 요소를 비교하고 자리를 교환한다는 사실이 중요합니다.
2. 선택정렬
전체 범위에서 차례대로 가장 작은 숫자를 탐색하여 변수에 저장합니다.
가장 왼쪽부터 변수에 저장된 최소값과 차례대로 교환이 일어나며
버블 정렬보다 교환이 덜 일어나게 됩니다.
3. 삽입정렬
인덱스 1번부터 시작해서 현재요소의 왼쪽에 자신보다 큰 수가 있는지 찾아봅니다.
인덱스 2번, 3번으로 넘어가면서 계속해서 큰 수가 있다면 교환이 일어납니다.
자신의 위치를 찾아 삽입된다고 하여 삽입정렬이라고 합니다.
4. 병합정렬
'분할 정복' 이라는 알고리즘 디자인기법에 근거하여
복잡한 문제를 복잡하지 않게 분할하여 정복하는 방식 입니다.
(그런데 복잡해 보입니다.)
병합정렬에서는 분할 후 병합 과정에서 정렬이 이루어집니다.
배열의 길이가 1이될 때까지 배열을 계속 쪼개서
각 요소를 비교한다음 붙여줍니다.
이때 쪼개는 과정을 반복하므로 재귀함수를 사용합니다.
5. 힙정렬
힙(완전이진트리)트리를 구성해서 정렬을 하는 방법입니다.
부모노드와 자식노드를 비교해서 교환이 진행됩니다.
이부분은 너무 어렵습니다!
그래서 코드를 생략합니다
https://taesung1993.tistory.com/26
[JS] 힙 정렬
힙 정렬(Heap Sort)은 힙 생성 알고리즘를 이용하여 정렬하는 방법이다. 힙 생성 알고리즘은 특정한 노드의 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘이다. 또한 위치를 바꾼 후에
taesung1993.tistory.com
6. 퀵정렬
살아있는 전설!!
특정 요소를 기준점(pivot)으로 잡고,
기준점보다 작은 요소는 왼쪽,
기준점보다 큰 요소는 오른쪽으로 두고,
왼쪽과 오른쪽을 각각 부분배열 정렬(정복)하는 방식입니다.
| 장점 | 단점 | 시간복잡도 | ||
| 기본적인 알고리즘 |
버블정렬 | 구현간단 | 이동하려면 교환 계속 일어남 | 최악: O(n^2) 평균: O(n^2) 최선: O(n) 거의 발생x |
| 선택정렬 | 자료 이동 횟수가 미리 결정됨 | 값이 같은요소가 있다면 상대적 위치 변경될 수 있다. | 최악,최선,평균 : O(n^2) | |
| 삽입정렬 | 최선의 경우 O(n) | 요소 너무많으면 많은이동해서 성능 좋지 않다. | 최악: O(n^2) 평균: O(n^2) 최선: O(n) |
|
| 복잡하지만 효율적인 알고리즘 |
병합정렬 | 기준값을 가운데 둠으로써 데이터 분포의 영향을 덜 받는다. | 요소를 배열로 구성하면 임시배열이 필요하다. 정렬을 위해 메모리를 더 쓴다. | 최악,최선,평균 : O(n^2) |
| 힙정렬 | 데이터의 크기가 큰 경우 효율적 | 대체로 느림 | 최악, 최선, 평균: O(nlog(n)) | |
| 퀵정렬 | 평균 실행시간이 빠르다 | pivot에 따라서 성능차이 심하다 | pivot이 중간에 가까운 값을 찾을 수록 성능이 좋다. 최악: O(n^2) 평균: O(n) 최선: O(n) |
너무 많아요 무엇을 써야 하나요? 무조건 제일 빠른게 좋나요?
알고리즘별로 장단점이 있습니다. 상황에 맞게 쓰시면됩니다.
1. 안정성
버블, 삽입, 병합
2. 공간 복잡도
1 - 버블,삽입,선택,힙
n - 병합
logn - 퀵
3. 지역성
4. 키값들의 분포상태
..... 등등등 사실 전 아직 몰읍니다.
마무리
알고리즘스터디 공부를 위해 정렬알고리즘을 살펴보았는데요 사실 정렬이 이렇게나 많은 종류가 있고 어려울줄 몰랐습니다. 아직 제 수준엔 안맞는것 같습니다. 순서대로 잡아 넣기만 하면 될줄 알았건만 이름부터 생소한 버블정렬부터 재귀호출을 이용한 병합정렬까지... 하지만 조금 아주조금 흥미 진진합니다. 나름 이해해가면서 (배껴)쓴 코드를 예시로 올렸지만 막상 새로운 문제를 만난다면 물론 머드라? 하면서 얼어버리겠죠? 하지만 이 포스팅을 다시보면서 기억을 더듬어 봐야겠습니다. 정렬알고리즘을 이렇게 자세히 알필요는 없다고 합니다. 다행입니다!
🔗모든 내용은 아래 영상들을 참고했습니다.
'Algorithm > 개념정리' 카테고리의 다른 글
| [자료구조] 큐,스택,트리 (0) | 2023.04.28 |
|---|---|
| DFS(Depth First Search) (2) | 2023.04.25 |
| 메모이제이션 (피보나치, 타일링) (2) | 2023.04.20 |
