AndroidTeacher

기수 정렬이란?​ 기수 정렬 (Radix Sort)은 자리수를 비교하며 정렬을 진행하는 알고리즘 이다. 기수 정렬의 종류 1. LSD (Least Significant Digit) 방식의 정렬​ 가장 작은 자릿수부터 정렬을 진행 (숫자로 치면 일의 자리수부터) 가장 작은 자릿수부터 큰 자릿수까지 비교해야 한다는 단점이 있지만, 코드 구현이 MSD에 비해 간결하다 2. MSD (Most Significant Digit) 방식의 정렬​ 가장 큰 자릿수부터 정렬을 진행 LSD와 비교했을 때 정렬 상태 확인등의 추가 작업이 필요하지만, 중간에 정렬이 완료될 수 있다는 장점이 있다 기수 정렬의 과정​ 기수 정렬의 과정을 배열 [134,224,232,122] 을 이용해 LSD방식과 MSD방식으로 각각 설명하고자 한..

힙 정렬이란?​ 힙 정렬(Heap Sort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성한다. 힙 정렬은 1964년 J.W.J 윌리엄스에 의해 발명되었고, 같은 해 R.W. 플로이드가 제자리 정렬을 할 수 있는 개선판을 출판하였고 이 방법이 바로 트리정렬 알고리즘을 이용한 방식이다. 힙 정렬 시뮬레이션​ 아래의 그림은 힙 정렬을 시뮬레이션한 그림이다. 추가로 힙 정렬을 숫자와 함께 보고 싶다면 아래의 사이트를 가보는 것도 추천한다. 힙 정렬 Visualization 힙 정렬 과정​ 힙 정렬 과정을 알기 위해선 힙 자료구조에 대한 선행 공부가 필수적이다. 만약 힙에 대한 자료구조를 모른다면 [자료구..

퀵정렬이란?​ 퀵정렬(Quick Sort)은 퀵이라는 이름답게 평균 속도 O(N*logN)을 자랑하는 매우 빠른 정렬 알고리즘이다. 퀵정렬은 분할정복(Divide & Conquer) 알고리즘의 하나로, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속하는 알고리즘이다. 퀵정렬의 전체적인 정렬 과정​ 퀵정렬은 임의의 pivot 값을 기준으로 pivot 의 좌측에는 pivot 보다 작은값을 두고 우측에는 pivot 보다 큰 값을 두는 방식으로 정렬을 진행한다. 전체적인 정렬 과정은 다음과 같다. 1. 리스트 안의 임의의 요소 하나를 선택한다. 이를 피봇(pivot) 이라고 하자. 2. pivot을 기준으로 pivot의 왼쪽에는 pivot보다 작은 원소를, pivot의 오른쪽에는 pivot보다 큰 원소..

병합정렬(합병정렬) 이란?​ 비교 기반의 정렬로, 안정 정렬에 속하며 분할 정복(Divide and Conquer) 알고리즘 중 하나이다. ※ 분할 정복(Divde and Conquer) 이란? : 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결한 후, 결과를 모아 원래의 문제를 해결하는 전략. 병합정렬의 전체적인 과정 그래서, 병합정렬의 전체적인 과정은 다음과 같이 요약할 수 있다. 정렬되지 않은 리스트를 각각 1개의 원소만 포함하는 n개의 부분리스트로 분할한다. 분할된 부분리스트들을 병합(Merge)하며 정렬한다. 그럼 다시 결국 1개의 리스트가 될 것이고 이 리스트는 정렬된 상태일 것이다. 병합정렬의 세부 과정 분할(Divide) : 정렬되지 않은 리스트를 절반으로 분할하여 비슷한 크기의 ..

삽입 정렬이란?​ 삽입 정렬(Insertion Sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 비교하면서 자리를 교환(swap)하는 정렬 방법이다. 삽입 정렬의 과정​ 1. 현재 타겟이 되는 숫자와 이전 위치에 있는 원소들을 비교한다. (첫번째 타겟은 두번째 원소부터 시작) 2. 타겟이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환한다. 3. 그 다음 타겟을 찾아 위와 같은 방법으로 반복한다. 위와 같은 삽입 정렬의 과정을 토대로 삽입 정렬의 전체적인 과정에 대해서 설명하자면 다음과 같다. (a) : 첫번째 타겟은 두번째 원소부터 시작하므로 7이다. 7 이전 위치에 있는 원소인 3과 비교했을 때 3이 더 작으므로 위치를 스왑하지 않는다. (b) : 두번째 타겟인 2와 이전 위치..

버블 정렬이란 (거품 정렬, bubble sort)​ 버블 정렬은 서로 인접한 두 원소의 크기를 비교하여 정렬하는 방법이다. 구현은 간단하나 시간복잡도가 O(n^2) 으로 상당히 비효율적이다. 버블 정렬 예시 및 시간복잡도 증명​ 간단한 예시를 통해 버블 정렬 과정을 나타내면 다음과 같다. 위 그림에서 확인할 수 있듯이, 5개의 요소를 거품 정렬을 적용해서 정렬하면 비교연산이 4회 + 3회 + 2회 + 1회 = 10회 소요되는 것을 확인할 수 있고, 요소의 개수를 N개로 일반화하면 (N-1) + (N-2) + (N-3) + ... + 2 + 1 가 된다. 이를 공차가 1인 등차수열 공식에 대입해보면, 결과적으로 N*(N+1) / 2 임을 알 수 있다. 이를 시간복잡도로 표현해보면 O(n^2) 임을 확인할..

선택 정렬 선택 정렬이란 제자리 정렬 알고리즘 중 한가지 방법이다. 보통 오름차순으로 정렬되는 선택 정렬은 다음과 같은 과정으로 이루어져 있다. 가장 작은 원소 값을 찾는다. 그 값을 맨 앞에 있는 값과 교체를 한다. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. 하나의 원소만 남을 때까지 위의 과정을 반복한다. 선택 정렬 예시​ 예시를 통해 좀 더 자세히 살펴보자. 위 그림과 같이, [5, 3, 8, 1, 2, 7] 로 구성된 배열이 있다고 하자. 앞에서부터 탐색하여, 가장 작은 원소 1을 찾은 후 맨 앞의 값 5와 교체한다. 1의 위치를 확정짓고 [3,8,5,2,7] 중 가장 작은 수 2를 맨 앞의 값 3과 교체한다. 같은 방법으로 [8,5,3,7] 중 가장 작은 수 3과 맨 앞의 값 8..