코딩꿀팁: 정렬 알고리즘
1. 선택 정렬
선택 정렬은 배열에서 가장 작은 값을 찾아 처음 위치에 넣고, 그 다음으로 작은 값을 찾아 두 번째 위치에 넣는 과정을 반복하는 알고리즘입니다.
선택 정렬의 시간 복잡도는 O(n^2)입니다.
2. 삽입 정렬
삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 가장 왼쪽 값을 정렬된 부분 사이에 삽입하는 과정을 반복하는 알고리즘입니다.
삽입 정렬의 시간 복잡도는 O(n^2)입니다.
3. 버블 정렬
버블 정렬은 인접한 두 개의 값을 비교하여 순서가 잘못되어 있다면 서로 교환하는 과정을 반복하는 알고리즘입니다.
버블 정렬의 시간 복잡도는 O(n^2)입니다.
4. 퀵 정렬
퀵 정렬은 분할 정복 알고리즘의 일종으로, 평균적으로 가장 빠른 정렬 알고리즘 중 하나입니다. 배열을 기준 값(피벗)을 기준으로 작은 값과 큰 값으로 분할하고, 각 부분 배열에 대해 재귀적으로 정렬합니다.
퀵 정렬의 평균 시간 복잡도는 O(n log n)입니다.
5. 합병 정렬
합병 정렬은 분할 정복 알고리즘의 일종으로, 배열을 반으로 나눈 뒤 병합하는 과정을 반복하는 알고리즘입니다. 배열을 작은 단위로 쪼갠 뒤 합병하면서 정렬하게 됩니다.
합병 정렬의 시간 복잡도는 O(n log n)입니다.
6. 힙 정렬
힙 정렬은 힙 자료구조를 이용한 정렬 알고리즘입니다. 배열을 힙으로 만든 뒤 최댓값(또는 최솟값)을 제거하여 정렬된 배열을 만드는 과정을 반복합니다.
힙 정렬의 시간 복잡도는 O(n log n)입니다.
7. 기수 정렬
기수 정렬은 자릿수를 기준으로 정렬하는 알고리즘입니다. 가장 작은 자릿수부터 가장 큰 자릿수까지 반복하며 정렬하여 최종적으로 정렬된 배열을 얻습니다.
기수 정렬의 시간 복잡도는 O(kn)입니다. (k는 자릿수의 개수)