Computer Science/Algorithm6 [Algorithm] 기수 정렬(Radix Sort) 기수 정렬(Radix Sort) 출처 기수 정렬(Radix Sort)은 데이터를 구성하는 기본 요소, 즉 기수를 이용해서 정렬을 진행하는 알고리즘입니다. 기수 정렬은 비교 정렬 알고리즘과는 다르게 비교 없이 수행하는 정렬 알고리즘으로 입력 데이터를 여러 개의 버킷으로 나누고 각 버킷에 속한 데이터들을 개별적으로 정렬하는 버킷 정렬 정렬의 일종으로 취급되기도 합니다. 데이터의 각 자릿수를 기준으로 정렬을 수행하기 때문에 자릿수가 존재하지 않는 데이터를 기수 정렬로 정렬하는 것은 불가능합니다. 또한 기수 정렬은 정렬 방법의 특수성 때문에 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없고 길이가 다른 데이터들을 대상으로는 정렬이 불가능합니다. 예제 먼저 다음과 같이 정렬되지 않은 배열이.. 2023. 11. 11. [Algorithm] 퀵 정렬(Quick Sort) 퀵 정렬(Quick Sort) 출처 퀵 정렬(Quick Sort)는 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬로 분할 정복(divide and conquer) 알고리즘을 기반으로 동작합니다. 분할 정복 알고리즘은 큰 문제를 작은 하위 문제로 나누고 각 하위 문제를 해결한 다음 그 결과를 결합하여 원래 문제를 해결하는 방식으로 진행합니다. 다만 동일하게 분할 정복 알고리즘을 활용하는 병합 정렬과는 다르게 분할되는 배열이 불균등합니다. 때문에 정렬 이후 데이터의 순서가 정렬 이전 원래 순서와 같음을 보장하지 못하는 불안정 정렬에 속합니다. 주어진 배열에서 임의의 한 원소를 고릅니다. 이렇게 고른 원소를 피벗(Pivot)이라 부릅니다. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고 피벗 뒤에는 .. 2023. 11. 8. [Algorithm] 병합 정렬(Merge Sort) 병합 정렬(Merge Sort) 출처 병합 정렬(Merge Sort)은 비교 기반 정렬 알고리즘이자 분할 정복 알고리즘 중 하나입니다. 분할 정복 알고리즘은 큰 문제를 작은 하위 문제로 나누고 각 하위 문제를 해결한 다음 그 결과를 결합하여 원래 문제를 해결하는 방식으로 진행합니다. 또한 하위 배열들을 병합하는 과정에서 투 포인터 기법이 사용됩니다. 분할: 주어진 배열을 반으로 나누는 과정으로 시작하며 정렬되지 않은 배열의 중간 지점을 기준으로 나눕니다. 해당 분할 작업을 더이상 나눌수 없을 때까지 재귀적으로 반복합니다. 정복: 나뉜 하위 배열들들에 대해 재귀적으로 병합 정렬 진행합니다. 각 하위 배열은 독립적으로 정렬됩니다. 병합: 투 포인터 기법을 사용하여 두 정렬된 하위 배열을 하나로 합칩니다. 두.. 2023. 11. 3. [Algorithm] 선택 정렬(Selection Sort) 선택 정렬(Selection Sort) 출처 선택 정렬(Selection Sort)은 배열에서 가장 작은(또는 가장 큰) 원소를 선택하고 이를 배열의 앞쪽으로 이동시키는 방식으로 동작합니다. 비교 연산을 기반으로 동작하며 원소 간의 비교를 통해 작은(또는 큰) 값을 찾고 배열에서 다른 위치로 이동시키는 방식으로 동작합니다. 예제 먼저 다음과 같이 정렬되지 않은 배열이 있다고 가정하겠습니다. 위 배열을 오름차순으로 정렬하기 위한 선택 정렬 알고리즘은 다음과 같이 동작합니다. 먼저 첫 번째 위치의 값과 해당 배열에서의 가장 작은 값이 무엇인지 확인합니다. 영 번째 인덱스의 값인 15보다 세 번째 인덱스의 값 10이 더 작은 값 입니다. 가장 작은 값인 10을 영 번째 인덱스에 넣고 15는 세 번쨰 인덱스로 .. 2023. 10. 28. [Algorithm] 삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort) 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다. 정렬되지 않은 목록(리스트, 배열)을 정렬된 부분과 정렬되지 않은 부분으로 나누며 정렬되지 않은 부분의 원소를 하나씩 선택하여 정렬된 부분의 적절한 위치에 삽입하는 방식으로 동작합니다. 출처 예제 먼저 다음과 같이 정렬되지 않은 배열이 있다고 가정하겠습니다. 위 배열을 오름차순으로 정렬하기 위한 삽입 정렬 알고리즘은 다음과 같이 동작합니다. 0 번째 인덱스 요소인 5는 정렬된 상태로 가정을하고 그 외 나머지 1... n-1 인덱스 요소는 정렬되지 않은 배열이라고 가정합니다. 첫 번쨰 요소를 정렬된 하위 배열의 요.. 2023. 10. 22. [Algorithm] 버블 정렬(Bubble Sort) 버블 정렬(Bubble Sort) 두 개의 인접한 요소를 비교하고 필요한 경우 위치를 교환(Swap)하여 리스트를 정렬합니다. 버블 정렬은 모든 요소를 탐색하며 정렬 조건(오름차순, 내림차순 등)에 해당하는 요소가 가장 뒤로 이동할 때까지 반복됩니다. 정렬 시 거품이 올라오는 것처럼 보여 버블 정렬이라고 이름이 지어졌습니다. 출처 예제 먼저 다음과 같이 정렬되지 않은 배열이 있다고 가정하겠습니다. 위 배열을 오름차순으로 정렬하기 위한 버블 정렬 알고리즘은 다음과 같이 동작합니다. 첫 번째 인덱스부터 시작하여 첫 번째 요소와 두 번째 요소를 비교합니다. 첫 번째 요소가 두 번째 요소보다 크면 교체됩니다. 마지막 요소에 도달할 때까지 이전 절차가 반복됩니다. 첫 번째 인덱스부터 시작하여 첫 번째 요소와 두 .. 2023. 10. 17. 이전 1 다음
