DeveloperJun

퀵 정렬(Quick Sort)이란? 기준키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법입니다. 이전에 만나봤던 합병정렬과 비슷하게 두 영역으로 분리하여 비교하는 정렬 방법입니다. 이렇게 두 영역으로 분리하여 각각을 해결하고 다시 합치는 전략을 분할 정복 방법이라고 합니다. 퀵 정렬의 원리를 좀더 간단하게 단계별로 나누면 아래와 같습니다. 1. 피벗을 설정한다. 2. 피벗보다 큰 수는 오른쪽 작은 수는 왼쪽에 배치한다. 3. 피벗을 기준으로 두개의 배열로 나눈다. 4. 각각의 배열을 1번부터 재귀적으로 반복한다. // 위치 변경 const swap = (arr, leftIndex, ri..

힙 정렬이란? 주어진 데이터들을 이진 트리로 구성하여 정렬하는 방법 입니다. 조금더 디테일 하게는 내림차순 정렬을 위해서는 최대 힙 트리를 구성하고 오름차순 정렬을 위해서는 최소 힙 트리를 구성하여 정렬을 하는 방법입니다. 그러고 보니 힙(heap)이라는 것이 무엇일까요? 힙(heap)이란? 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조 입니다. 힙에서 두가지 최대힙과 최소힙으로 나눠집니다. 따라서, 최대힙(Max Heap)은 큰 값이 위로 오도록, 최소힙(Min Heap)은 작은 값이 위로 오도록 구성하는 트리구조 입니다. 이처럼, root에 가장 큰 값 또는 가장 작은 값을 올리고 최종적으로 해당 값을 마지막 위치로 교환하여 정렬을 하는 방식입니..

셸 정렬 이란? 1959년 이 방법을 발표한 창안자 도널드 셸의 이름을 따서 붙여진 이름인데, 리스트를 특정 매개변수 값의 길이를 갖는 부파일(subfile)로 쪼개서, 각 부파일에서 삽입 정렬을 수행하는 삽입 정렬의 단점을 보완한 정렬 알고리즘 입니다. 사실, 셸 정렬은 설명만 듣고는 이해가 가질 않았습니다. 쪼개는 것은 알겠는데, 쪼개진 데이터들을 각각 정렬하는 것도 아닌 것이, 쪼개진 간격의 데이터끼리 하나씩 비교를 하는 느낌이었습니다. 이러한 일정한 갭 간격을 설정하고 간격의 데이터끼리 비교 정렬을 합니다. 그 이후, 간격을 줄이고 또 간격의 데이터끼리 비교 정렬을 합니다. 최종적으로 간격이 없는 상태까지 도달했을 때, 삽입 정렬을 통해 마지막으로 정렬을 합니다. 가장 잘 표현된 영상입니다. 이 ..

삽입 정렬(Insertion Sort)이란? 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식을 삽입 정렬이라고 합니다. 실제로 삽입 정렬의 데이터 이동 흐름은 위와 같습니다. 여기서의 핵심은 빨간색 데이터를 위로 잠깐 빼놓고, 값을 비교하여 오른쪽으로 계속 당기는 과정이 핵심입니다. 빨간색 데이터와 바로 왼쪽의 데이터를 자리 바꿈으로 정렬을 하는 예제들이 많은데, 그렇게 하면 버블 정렬보다 훨씬 느리답니다 ㅠㅠ 그럼 코드로 확인해보겠습니다. // 임의 데이터 생성 const makeRandomValueArr = (length) => { const arr = []; for (let i = 0; i < length; i++) { arr.push(i); } for (let i = 0; i < ar..

선택 정렬(Selection Sort)이란? 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식입니다. 좀 더 쉽게 표현하면, 각 자리마다 가장 작은 값을 선택하는 개념 이라고 이해하시면 됩니다!! 출처 - https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC 생각보다 이해하는데 어렵지 않았던 개념이라 바로 javascript로 구현해보겠습니다. // 랜덤 임의 배열 만들기 const makeRandomValueArr = (length) => { const arr = []; for (let i = 0; i < length; i++) { arr.push(i); } for (let i = 0; i <..