sort
-
알고리즘, Sort, Radix SortData Structure & Algorithm 2024. 6. 18. 17:54
Radix Sort(기수 정렬)은 정수나 문자열의 자릿수를 기준으로 정렬하는 효율적인 정수 정렬 알고리즘입니다. 이 알고리즘은 주로 양의 정수나 고정 길이의 문자열을 정렬하는 데 사용되며, 시간 복잡도가 O(d * (n + k))로, 비교 기반 정렬 알고리즘보다 더 효율적일 수 있습니다. 여기서 d는 데이터의 최대 자릿수, n은 요소의 수, k는 기수(예: 10진법에서는 10)입니다.기본 개념기수 정렬은 LSD(Least Significant Digit)와 MSD(Most Significant Digit) 두 가지 방법으로 나뉩니다:LSD 방식: 가장 작은 자릿수부터 시작하여 큰 자릿수 방향으로 정렬합니다.MSD 방식: 가장 큰 자릿수부터 시작하여 작은 자릿수 방향으로 정렬합니다.LSD 방식은 일반적으로..
-
알고리즘, Sort, Quick SortData Structure & Algorithm 2024. 6. 18. 17:47
퀵 정렬(Quick Sort)은 Divide and Conquer 기법을 사용하는 매우 효율적인 정렬 알고리즘입니다. 평균적으로 매우 빠른 시간 복잡도인 O(n log n)을 가지며, 제자리 정렬(In-place Sort) 알고리즘입니다. 퀵 정렬은 리스트에서 피벗(pivot) 요소를 선택하고, 이를 기준으로 리스트를 두 개의 하위 리스트로 나누는 과정을 반복하여 정렬합니다.기본 개념퀵 정렬의 기본 개념은 다음과 같습니다:피벗 선택: 리스트에서 피벗 요소를 선택합니다.분할: 피벗을 기준으로 리스트를 두 개의 하위 리스트로 분할합니다. 피벗보다 작은 요소들은 피벗의 왼쪽으로, 피벗보다 큰 요소들은 피벗의 오른쪽으로 이동합니다.재귀 호출: 분할된 하위 리스트에 대해 퀵 정렬을 재귀적으로 호출합니다.결합: 하..
-
알고리즘, Sort, Merge SortData Structure & Algorithm 2024. 6. 18. 17:38
병합 정렬(Merge Sort)은 Divide and Conquer 기법을 사용하는 효율적인 정렬 알고리즘입니다. 병합 정렬은 리스트를 반으로 나누어 각각을 재귀적으로 정렬하고, 정렬된 부분 리스트를 합쳐서 전체 리스트를 정렬합니다. 이 알고리즘은 안정적이고, 시간 복잡도가 O(n log n)으로 매우 효율적입니다.기본 개념병합 정렬의 기본 개념은 다음과 같습니다:분할(Divide): 리스트를 두 개의 하위 리스트로 나눕니다.정복(Conquer): 하위 리스트를 재귀적으로 병합 정렬합니다.결합(Combine): 두 개의 정렬된 하위 리스트를 하나의 정렬된 리스트로 병합합니다.예제다음은 자바스크립트로 구현한 병합 정렬의 예제입니다.function merge(arr1, arr2) { let idx1 = 0..
-
알고리즘, Sort, Insertion SortData Structure & Algorithm 2024. 6. 18. 17:32
삽입 정렬(Insertion Sort)은 간단하고 직관적인 정렬 알고리즘 중 하나로, 배열을 부분적으로 정렬된 상태로 유지하면서 새로운 요소를 올바른 위치에 삽입하는 방식입니다. 삽입 정렬은 작은 데이터 세트에 대해서는 효율적이고, 거의 정렬된 배열에 대해서도 효율적입니다.기본 개념삽입 정렬의 기본 개념은 다음과 같습니다:부분 정렬 유지: 배열의 첫 번째 요소는 이미 정렬된 상태로 간주하고, 두 번째 요소부터 시작하여 배열을 부분적으로 정렬된 상태로 유지합니다.삽입 위치 찾기: 현재 요소를 이미 정렬된 부분 배열과 비교하여 적절한 위치를 찾습니다.삽입: 현재 요소를 올바른 위치에 삽입합니다.반복: 배열의 모든 요소에 대해 이 과정을 반복합니다.예제다음은 자바스크립트로 구현한 삽입 정렬의 예제입니다.fun..
-
알고리즘, Sort, Selection SortData Structure & Algorithm 2024. 6. 18. 17:28
선택 정렬(Selection Sort)은 단순한 정렬 알고리즘 중 하나로, 리스트에서 가장 작은 요소를 찾아 맨 앞의 요소와 교환하는 과정을 반복하여 정렬하는 방식입니다. 선택 정렬은 이해하기 쉽고 구현이 간단하지만, 시간 복잡도가 O(n^2)으로 비효율적입니다.기본 개념선택 정렬의 기본 개념은 다음과 같습니다:최소값 찾기: 리스트에서 현재 위치부터 끝까지 탐색하여 가장 작은 요소를 찾습니다.교환: 가장 작은 요소를 현재 위치의 요소와 교환합니다.반복: 리스트의 모든 위치에 대해 이 과정을 반복합니다.예제다음은 자바스크립트로 구현한 선택 정렬의 예제입니다.function swap(arr, idx1, idx2) { let temp = arr[idx1]; arr[idx1] = arr[idx2]; arr..
-
알고리즘, Sort, Bubble SortData Structure & Algorithm 2024. 6. 18. 17:24
버블 정렬(Bubble Sort)은 간단한 정렬 알고리즘 중 하나로, 인접한 두 요소를 비교하여 필요에 따라 위치를 바꾸면서 리스트를 정렬하는 방식입니다. 버블 정렬의 이름은 가장 큰 요소가 반복적으로 리스트의 끝으로 "부풀어 오르는" 과정에서 유래되었습니다.기본 개념버블 정렬의 기본 개념은 다음과 같습니다:비교 및 교환: 리스트의 처음부터 시작하여 인접한 두 요소를 비교합니다. 만약 첫 번째 요소가 두 번째 요소보다 크면 두 요소의 위치를 바꿉니다.반복: 리스트 끝까지 이 과정을 반복합니다. 이 과정을 반복하면 가장 큰 요소가 리스트의 끝으로 이동합니다.반복 감소: 리스트 끝에 가장 큰 요소가 고정되면 다음 반복에서는 마지막 요소를 제외한 나머지 요소를 비교합니다.정렬 완료: 더 이상 교환이 필요하지 ..