CS7 [알고리즘] 기수 정렬(Radix Sort) 계수정렬에 이어 기수정렬도 정리하려고 한다.기수정렬(Radix Sort)기수 정렬은 같은 키 값을 가진 데이터의 상대적인 순서를 유지하는 정렬 알고리즘이다."기수"는 숫자의 자릿수를 의미하며, 자리수에 따라 정렬을 수행하는 방식에서 유래되었다고 한다.기수정렬은 비비교 정렬 알고리즘이다. 따라서 정수나 유한한 범위의 데이터를 대상으로 하고,기수정렬은 자리수를 기준으로 정렬되며, 안정적인 정렬방식으로 같은 값을 가진 요소의 상대적 순서는 유지된다.정수범위가 좁고(자리수), 양이 많은 데이터일 경우 유리하다.기수정렬의 시간복잡도최악의 경우 시간 복잡도는 O(d*(n + k))이다.여기서 n은 정렬할 요소의 수, d는 최대 자리수, k는 기수(base)를 의미한다.기수정렬 원리기수정렬은 가장 낮은 자리수(LSB.. 2024. 8. 31. [알고리즘] 계수정렬(Count Sort) 계수정렬(Count Sort)란?- 정수형 데이터의 정렬을 위해 사용되는 비교 기반이 아닌 정렬 알고리즘이다.- 특정한 범위의 정수 값을 가지는 데이터에 대해 매우 효율적으로 작동한다.- 데이터의 범위가 작고, 중복된 값이 많을 때 특히 유용하다.- O(n + k)의 시간 복잡도를 가지며, 여기서 n은 입력 데이터의 개수, k는 입력 데이터의 범위다.계수정렬의 장점- 특정한 데이터 범위에 대해 매우 빠른 정렬이 가능하다.- 안정 정렬(stable sort)로, 동일한 값의 순서를 유지한다.계수정렬의 단점- 데이터의 범위가 너무 넓으면 비효율적이다.- 정수형 데이터에만 적용 가능하고, 비정수형 데이터에는 직접적으로 사용할 수 없다.계수정렬의 기본 원리1. 정렬할 데이터의 최소값과 최대값을 찾아 범위를 결정.. 2024. 8. 19. [알고리즘] 퀵정렬(Quick Sort) 퀵정렬(Quick Sort)은 분할 정복(Divide and Conquer) 기법을 사용하는 효율적인 정렬 알고리즘이다. 퀵정렬은 재귀적으로 배열을 정렬하며, 데이터가 큰 경우에도 매우 빠른 성능을 자랑한다. 퀵정렬은 추가적인 메모리 공간을 많이 사용하지 않는 제자리(in-place) 정렬 알고리즘이다. 퀵정렬의 시간 복잡도평균적으로 O(n log n)의 시간 복잡도를 가지며, 특히 큰 데이터셋에서 효율적이다. 이미 정렬된 배열이나 모든 요소가 동일한 경우, 비효율적인 피벗 선택으로 인해 시간 복잡도가 O(n²)까지 증가할 수 있다. 퀵정렬의 원리1. 배열에서 하나의 요소를 선택한다. 이 요소를 피벗이라고 한다. 피벗은 배열의 중간에 위치한 값이나 임의로 선택된 값일 수 있다. 2. 배열을 피벗을 기준으.. 2024. 8. 12. [알고리즘] 선택정렬(Selection sort) 선택정렬(Selection sort)?선택정렬(Selection sort)은 비교 기반 정렬 알고리즘 중 하나로,주어진 리스트에서 가장 작은(또는 가장 큰) 값을 찾아 이를 정렬된 부분과 교환하는 과정을 반복하여 전체 리스트를 정렬한다. 선택정렬의 장점은 구현이 매우 쉽고, 이해하기 쉬운 알고리즘이라는 점이다.제자리 정렬(추가적인 메모리 공간을 사용하지 않고, 원래 리스트 내에서 정렬을 수행)이므로 추가적인 메모리를 거의 사용하지 않는 특징을 가지고 있다. 선택정렬은 시간 복잡도가 O(n²)으로, 데이터가 많을 경우 비효율적이다.또, 동일한 값을 가진 요소의 상대적인 순서가 바뀔 수 있으므로 안정성이 문제도 가지고 있는 단점이 있다. 선택정렬의 시간 복잡도 선택정렬의 시간복잡도는 위에서 말했듯 O(n²).. 2024. 8. 4. 이전 1 2 다음