알고리즘과 자료구조/정렬 알고리즘 (5) 썸네일형 리스트형 [알고리즘] 퀵 정렬 알고리즘 With JS 퀵 정렬 이 알고리즘은 먼저 배열의 한 요소를 피벗(pivot)으로 선택한 후, 피벗보다 작은 요소는 모두 피벗의 왼쪽에 위치하도록, 피벗보다 큰 요소는 모두 피벗의 오른쪽에 위치하도록 배열을 분할합니다. 그 다음, 분할된 두 하위 배열을 각각 재귀적으로 퀵 정렬을 수행하여 정렬을 완료합니다. 이 알고리즘의 핵심 아이디어는 분할(Divide) 단계에서 피벗을 기준으로 배열을 분할하여 정복(Conquer) 단계에서 각 하위 배열을 정렬하는 것입니다. 이 과정을 반복하여 분할된 배열이 더 이상 분할되지 않을 때까지 정렬을 수행합니다. 피벗 요소를 기준으로 해당 요소보다 작은 요소는 좌측으로, 큰 요소를 우측으로 분할하여, 배열을 분할한다. 그 후 분할 된 배열 내에서 재귀적 퀵 정렬(퀵 정렬 함수를 다시 호.. [알고리즘] 합병정렬 알고리즘(분할과 정복 알고리즘 유형 중 하나) With JS 합병정렬 알고리즘 분할 정복(Divide and Conquer) 알고리즘 중 하나로, 배열을 반으로 나누어 각각을 재귀적으로 정렬하고, 그 결과를 합쳐서 정렬된 배열을 생성하는 알고리즘입니다. * 분할과 정복 알고리즘의 원리 접은 글 내에 글자 중복이 있습니다. 중복된 부뷰이 지우고 수정한 부분이었는데, 수정 시에는 안 보이는데 등록 후에는 보이는 이상한 버그가 있네요더보기 분할 정복 알고리즘의 일반적인 구조는 다음과 같습니다. 분할(Divide) : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 정복(Conquer) : 각각의 작은 문제를 동일한 방법으로 순환적으로 해결 합병(Combine) : 작은 문제의 해를 합하여 원래 문제에 대한 해를 구함 합병정렬도 위 구조에 따라, 배열을 분할하고.. [알고리즘] 삽입 정렬 with JS 삽입 정렬 배열의 요소들을 순차적으로 검사하면서 해당 요소가 들어갈 위치를 찾아 삽입하는 정렬 알고리즘입니다. 간단하게 설명하면, 첫 번째 요소는 이미 정렬되었다고 가정하고, 두 번째 요소(i)부터 시작하여 앞의 요소(j-1)들과 비교하면서 자신의 위치를 찾아 삽입하는 방식으로 정렬을 수행합니다. 즉, 배열을 순회할 때 마다 j= j-1 혹은 j-- 를 반복함으로써 정렬 대상인 key 요소와 j-1 요소 간의 크기 비교를 통해 key = 0 && arr[j] > key) { // j+1번째 인덱스에 j번째 인덱스의 값을 할당합니다. arr[j + 1] = arr[j]; // j를 감소시켜 while 문을 반복하여 key가 들어갈 위치를 찾습니다. // 만일 j 가 -1이 되면 즉시 while을 탈출합니다.. [알고리즘] 선택 정렬 with JS 선택정렬(Selection sort) 배열에서 가장 작은 값을 찾아서 배열의 맨 앞에 위치시키고, 그 다음 작은 값을 찾아서 두 번째 위치에 위치시키는 방식으로 정렬하는 알고리즘 입니다. 선택정렬 실행 과정 배열의 첫 번째 원소를 제외한 나머지 원소들 중 가장 작은 값을 찾습니다. 가장 작은 값과 배열의 첫 번째 원소를 교환합니다. 배열의 두 번째 원소를 제외한 나머지 원소들 중 가장 작은 값을 찾습니다. 가장 작은 값과 배열의 두 번째 원소를 교환합니다. 위의 과정을 반복해서 전체 배열이 정렬될 때까지 반복합니다. 선택정렬 코드 function selectionSort(arr) { for (let i = 0; i < arr.length - 1; i++) { let minIndex = i; for (le.. [정렬 알고리즘] 버블정렬 with JS 버블정렬 버블 정렬(Bubble Sort)은 서로 인접한 두 원소를 비교하며 정렬하는 알고리즘입니다. 구현이 간단하나 시간복잡도가 높기 때문에 큰 데이터셋에는 적합하지 않습니다. 코드 // 배열의 비교인덱스의 요소를 배열 길이 만큼 반복하여 서로 비교 후 자리를 바꾸는 알고리즘 function bubbleSort(array) { const length = array.length; // 시작인덱스: i -> 배열 길이 만큼 반복을 실행하는 용도이지 비교를 위해 사용하지 않습니다. for (let i = 0; i 실질적으로 배열의 원소를 비교할 때 쓰입니다. for (let j = 0; j < length - 1; j++) { if (array.. 이전 1 다음