정렬되어 있는 배열에서 데이터를 찾으려 시도할 때, 순차 탐색처럼 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 것이 아니라 탐색 범위를 절반씩 줄여가며 찾아가는 Search 방법입니다. 시간복잡도 처음부터 끝까지 우너하는 값을 찾을 때까지 탐색을 계속하는 순차 탐색은 Worst Case일 때 O(n)이라는 Time complexity를 보여줍니다. 10만개의 데이터가 있다면 무려 10만번을 탐색해야합니다. 그러나 Binary Search는 탐색 대상을 절반씩 계속해서 줄여나가기 때문에, Worst Case일때도 탐색의 횟수가 logn이 되므로 10만개의 데이터가 있다고해도 약 16번정도로 탐색을 끝낼 수 있습니다. 시간복잡도는 O(log n) 입니다. 구현 재귀적으로도 구현을 할 수 있습니다.

기수정렬은 낮은 자리 수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘입니다. 기수 정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요합니다. 정렬 방식 0~9 까지의 Bucket(Queue 자료구조)를 준비합니다. 모든 데이터에 대하여 가장 낮은 자리 수에 해당하는 Bucket에 차례대로 데이터를 둡니다. 0부터 차례대로 버킷에서 데이터를 다시 가져옵니다. 가장 높은 자리 수를 기준으로 하여 자리수를 높여가며 2번 3번 과정을 반복합니다. 아래의 8개 데이터에 대하여 기수 정렬을 시도해 보겠습니다. 위의 그림과 같이 각 숫자에 해당하는 Queue 공간을 할당하고 진행합니다.

완전 이진 트리를 기본으로 하는 힙(Heap) 자료 구조를 기반으로한 정렬 방식 완전 이진 트리란? > 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리 시간복잡도 과정 최대 힙을 구성 현재 힙 루트는 가장 큰 값이 존재함. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나 줄임 힙의 사이즈가 1보다 크면 위 과정 반복 루트를 마지막 노드로 대체 (11 -> 4), 다시 최대 힙 구성 이와 같은 방식으로 최대 값을 하나씩 뽑아내면서 정렬하는 것이 힙 소트입니다. heapify

합병 정렬이라고도 불리우며 분할 정복 방법을 통해 구현할 수 있습니다. 빠른 정렬로 분류되며 퀵소트와 함께 많이 언급되는 정렬 방식입니다. 요소를 쪼갠 후, 다시 병합시키면서 정렬해나가는 방식으로 쪼개는 방식은 퀵정렬과 유사합니다. 구현 재귀를 이용해서 병합 정렬을 구현할 수 있습니다. 먼저 배열을 더 이상 나눌 수 없을때까지 분할한 이후에 다시 병합하면서 점점 큰 배열을 만들어 나가면 됩니다. 따라서 이 재귀 알고리즘의 기저 조건은 입력 배열의 크기가 2보다 작을 때이며, 이 조건에 해당할 때는 배열을 그대로 반환하면 됩니다. 임시 배열을 만들어서 사용하기 때문에 메모리적인 측면에서 비효율적인 코드여서 개선점을 생각해볼 수 있을 것 같습니다.

Goal Quick Sort에 대해 설명할 수 있습니다. Quick Sort 과정에 대해 설명할 수 있습니다. Quick Sort 를 구현할 수 있습니다. Quick Sort의 시간복잡도와 공간복잡도를 계산할 수 있습니다. Quick Sort의 처악의 경우를 개선시킬 수 있습니다. Abstract Quick Sort는 분할 정복(divide and conquer) 방법 을 통해 주어진 배열을 정렬합니다. Quick Sort는 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속합니다. 또한 Merge Sort와 달리 Quick Sort는 배열을 비균등하게 분할합니다. Process (Ascending) 배열 가운데서 하나의 원소를 고릅니다. 이렇게 고른 원소를 피봇(pivot) 이라고 합니다. 피봇 앞에는 피봇보다 값이 작은 모든 원소들이 오고, 피봇 뒤에는 피봇보

Goal Insertion Sort에 대해 설명할 수 있습니다. Insertion Sort 과정에 대해 설명할 수 있습니다. Insertion Sort를 구현할 수 있습니다. Insertion Sort의 시간복잡도와 공간복잡도를 계산할 수 있습니다. Insertion와 Selection Sort 차이에 대해 설명할 수 있습니다. Abstract 손 안의 카드를 정렬하는 방법과 유사합니다. Insertion Sort는 Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘입니다. Insertion Sort는 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘입니다. 최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 상요될 만큼 좋은 정렬 알고리즘입니다.

Goal Selection Sort에 대해 설명할 수 있습니다. Selection Sort 과정에 대해 설명할 수 있습니다. Selection Sort을 구현할 수 있습니다. Selection Sort의 시간복잡도와 공간복잡도를 계산할 수 있습니다. Abstract Selection Sort는 Bubble Sort와 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 정해져 있고, 어떤 원소를 넣을 지 선택하는 알고리즘입니다. Selection Sort와 Insertion Sort를 헷갈려하는 사람들이 종종 있는데, Selection Sort는 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이라고 생각하면 편합니다. Process (Ascending) 주어진 배열 중에 최소값을 찾습니다. 그 값을 맨 앞에 위치한 값과 교체합니다. 맨 처음 위치를 뺀 나머지 배열을 같은 방

Goal Bubble Sort에 대해 설명할 수 있습니다. Bubble Sort 과정에 대해 설명할 수 있습니다. Bubble Sort을 구현할 수 있다. Bubble Sort의 시간 복잡도와 공간 복잡도를 계산할 수 있습니다. Abstract Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 입니다. 이름의 유래는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 합니다. Process (Ascending) 1회전에 첫 번째 원소와 두 번쨰 원소를, 두 번째 원소와 세 번째 원소를 이런 식으로 (마지막 - 1)법ㄴ째 원소와 마지막 원소를 비교하여 조건에 맞지 않으면 서로 교환을 합니다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하