정렬의 정의$n$개의 숫자를 입력받아 입력 받은 숫자들을 점점 커지는 순서나 점점 작아지는 순서로 다시 재배열하여 출력하는 것 선택정렬현재 상황에서 가장 작거나 가장 큰 숫자를 선택하여 재배치하는 아이디어의 알고리즘수행시간: $_{n}\mathrm{C}_{2}$ 또는 $n(n-1) \over 2$ 또는 $\sum_{i=1}^{N-1} i$최악: 선택정렬의 경우에는 항상 일정하기 때문에 최악의 경우는 없다최선: 선택정렬의 경우에는 항상 일정하기 때문에 최선의 경우는 없다즉, 시간복잡도는 $O(n^2)$Not Stable 정렬임 삽입정렬Key 값을 정렬된 배열에 알맞은 위치에 삽입하여 정렬문제를 푸는 알고리즘$T(n) = c_{1}n+c_{2}(n-1)+c_{3}(n-1)+ c_{4}\sum_{j=2}^n ..

이분탐색이란 정렬된 배열의 중앙에 있는 값을 조사하여 찾고자하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄여가며 탐색을 진행하는 알고리즘 숫자야구게임과 유사한 방식이다. 이진탐색은 배열의 내부 데이터가 정렬되어 있어야만 적용할 수 있는 알고리즘이다. 이분탐색 알고리즘 과정 1 3 5 6 7 9 11 20 30 위 배열에서 5를 탐색하는 경우를 보자. 중간값인 7을 mid값으로 지정한 후, 5와 비교 ( 5는 7보다 작으므로 7보다 큰 오른쪽 부분은 제외) 다시 왼쪽부분에서 중간값인 3을 mid값으로 지정한후, 5와 비교 (3은 5보다 작으므로 3보다 작은 왼쪽 부분은 제외) 다시 오른쪽부분에서 중간값인 5를 mid값으로 지정한 후, 5와 비교 (5와 5는 같은 값이므..

기수정렬이란 데이터를 구성하는 기본 요소(Radix)를 이용하여 정렬하는 방식 데이터의 각 자릿수끼리 비교하면서 정렬을 수행한다. 가장 작은 자릿수부터 비교하는 방법인 LSD(Least-Significant-Digit)와 가장 큰 자릿수부터 비교하는 방법인 MSD(Most-Significant-Digit)가 있다. 기수정렬 알고리즘 과정 한자리수 일땐 데이터의 값이 인덱스가 되어 배열에 정렬된다. 만약 2자리 일땐? (28,93,39,81,62,72,38,26) 낮은 자리수로 먼저 분류한 다음, 순서대로 읽어서 다시 높은 자리수로 분류한다. 버켓은 큐로 구현 버켓의 개수는 키의 표현 방법과 밀접한 관계가 있다.(이진법2개, 알파벳26개, 십진법10개) 자리수에 따라 큐에 순차적으로 데이터를 삽입한다. 버..

퀵 정렬이란 평균적으로 가장 빠른 정렬 방법 분할정복법 사용 리스트를 2개의 부분리스트로 합병정렬과는 다르게 퀵정렬은 리스트를 비균등 분할하고, 각각의 부분리스트를 다시 퀵정렬한다(재귀) 불안정 정렬에 속하며 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속한다. 분할정복이란? 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 분할 정복 방법은 대개 재귀호출을 이용하여 구현한다. 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 기준으로 작은 요소들은 왼쪽에, 큰 요소들은 오른쪽에 오게끔)로 분할한다. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 재귀 호출을 이용하여 분할 ..

합병정렬이란 리스트를 2개의 균등한 크기로 분할하고 분할된 부분리스트를 정렬하는 알고리즘. 정렬된 2개의 부분 리스트를 합하여 전체 리스트를 정렬한다. 합병정렬은 안정 정렬(Stable)에 속하며 분할 정복 알고리즘(Divide and conquer)의 한 종류이다. 분할정복이란? 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 분할 정복 방법은 대개 재귀호출을 이용하여 구현한다. 분할(Divide): 입력 배열을 같은 크기의 2개의 배열로 분할 정복(Conquer): 부분 배열을 정렬한다. 크기가 충분히 작지 않으면 재귀 호출을 이용하여 다시 분할방법적용 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다. 합병정렬 구체적인 개념 추가..

쉘 정렬이란? 삽입정렬이 어느정도 정렬된 리스트에서 대단히 빠른 것에 착안된 알고리즘이다. 삽입정렬은 요소들이 삽입될 때, 이웃한 위치로만 이동된다. 즉, 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있다. 삽입 정렬과는 다르게 쉘 정렬은 전체의 리스트를 한 번에 정렬하지 않는다. 요소들이 멀리 떨어진 위치로 이동할 수 있게 하면 보다 적게 이동하여 제자리를 찾아가는 것이 가능. 정렬해야할 리스트의 각 k번째 요소를 추출해서 부분리스트를 만든다. 이때 k를 gap이라고 한다. 간격의 초기값은 (정렬할 값의 수) / 2, 생성된 부분 리스트의 수는 gap과 같다. 각 회전마다 간격 k를 절반으로 줄인다. 회전이 반복될 때마다 부분리스트의 속한 값..

버블정렬이란 인접한 2개의 레코드를 비교하여 순서대로 되어 있지 않으면 서로 교환하는 방식의 정렬 알고리즘 선택정렬과 기본개념이 유사하다 버블정렬 기본 개념 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다. 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. 버블정렬 과정 첫번째 자료 7을 4와 비교하여 교환하고, [교환]칸이 한 칸 이동되어 7과 5를..

삽입정렬이란 정렬되어 있는 부분에 새로운 레코드를 올린 위치에 삽입하는 과정을 반복한다. 손안의 카드를 정렬하는 방법과 유사하다. 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입한다 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다. 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 즉, 두 번째 자료는 (첫 번째 자료), 세 번째 자료는 (두 번째와 첫 번째) 자료, 네 번째 자료는 (세 번째, 두 번째, 첫 번..

선택정렬 정렬된 왼쪽 리스트와 정렬안된 오른쪽 리스트로 나누어 정렬 초기에는 왼쪽 리스트는 비어있고 정렬할 숫자들은 모두 오른쪽 리스트에 존재한다. In-place 정렬 알고리즘의 하나 (입력배열 이외의 다른 추가 메모리를 요구하지 않는 정렬 방법) 원소를 넣을 위치는 이미 정해져있고 어떤 원소를 넣을지 "선택"하는 알고리즘 오른쪽리스트에서 최소값을 선택하여 왼쪽 리스트로 순서대로 옮기는 방식이다. 선택정렬 알고리즘 과정 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다. 1회전을 수행..

위상 정렬 방향 그래프에서 간선 가 있다면 정점 u는 정점 v를 선행함 방향 그래프 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것이다. 위상정렬은 여러 개의 답이 존재할 수 있다. 그래프에 사이클이 존재할 경우 위상 정렬은 불가능하다. 하나의 방향 그래프에는 여러 위상 정렬이 가능하다. 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서(Topological Order)라 한다. 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리즘은 중단되고 이러한 그래프로 표현된 문제는 실행이 불가능한 문제가 된다. 진입차수가 0인 정점을 큐에 삽입한다. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다. 간선 제거 이후 진입하수가 0이 될 정점을..

힙정렬이란 2022.10.13 - [📚 자료구조 및 알고리즘/힙] - [자료구조] 힙(Heap)이란? [자료구조] 힙(Heap)이란? 힙이란? 완전이진트리의 일종이다. 힙은 중복된 값을 허용한다. 여러 값들 중 최대값 혹은 최소값을 빠르게 찾아내기 위한 자료구조이다. Max heap은 가장 큰 값을 빠르게 찾기 위한 것이고 Min Heap linerate.tistory.com 합병 정렬방식은 비록 최악의 경우 연산 시간과 평균 연산 시간 모두 O(nlogn)이지만, 정렬할 레코드 수에 비례하여 저장 공간이 추가로 필요하다. 힙 정렬(heap sort)은 일정한 양의 저장 공간만 추가적으로 필요한 동시에, 최악의 경우 평균 연산 시간이 O(n log n)이다. 하지만, 힙 정렬은 합병 정렬보다 약간 느리다..

Merge Sort(병합 정렬) 병합 정렬은 분할정복(Divide and Conquer)의 대표적인 예이다. n개의 데이터를 가진 배열을 오름차순으로 정렬하기 위해 병합정렬을 사용한다면 아래와 같은 3단계의 과정을 거치게 된다. 1. Divide(분할) : n개의 원소를 갖는 배열을 n/2 개의 원소를 갖는 작은배열 2개로 나눈다. 2. Conquer(정복) : 각각의 작은 배열들을 정렬한다. 3. Combine(병합) : 정렬된 작은 배열들을 병합한다. 예를 들어 다음과 같은 과정을 거치게 된다. 병합정렬의 특징 병합정렬은 분할한 작은 배열을 위한 저장공간이 따로 필요하다. n개의 원소를 n/2 개씩 나누므로 병합정렬의 공간복잡도는 O(n)이다. 따라서 not-in place 정렬이다. 시간 복잡도는 ..

정렬 알고리즘이란? 정렬 알고리즘은 n개의 숫자가 주어졌을 때 이를 사용자가 지정한 기준에 맞게 정렬하는 알고리즘이다. stable vs not stable STABLE 정렬은 중복된 키 값이 있을 때 이를 순서대로 정렬하는 알고리즘을 뜻한다. 예를 들어, int arr[5] = { 7, 3, 6, 2, 3 }과 같이 3값이 두번 들어 있는 배열이 있다고 하자. 이것을 어떠한 정렬 알고리즘으로 정렬 했을 때 중복된 키 값이 처음 순서대로 정렬 되었다면 stable sort라고 한다. 반대로 어떠한 정렬 알고리즘으로 정렬 했을 때 중복된 키 값이 처음 순서와 다르다면 not-stable sort라고 한다. 정렬전에는 주황색으로 표시한 3이 초록색으로 표시한 3보다 앞에 있다. Stable sort: 정렬 ..

퀵 정렬(Quick Sort) 퀵 정렬은 합병정렬과 비슷하게 분할정복(Divide and Conquer) 알고리즘이다. 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법으로 다음과 같은 과정을 거친다. 1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 pivot이라고 한다. 2. pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮기고 pivot보다 큰 요소들은 모두 povot의 오른쪽으로 옮긴다. 3. pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다. 3-1) 분할된 왼쪽 리스트와 오른쪽리스트도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분리스트로 나눈다. 3-2) 재귀를 사용하여 부분 리스트들이 더이상 분할이 불가능 할 때까지 ..

삽입정렬 삽입정렬은 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 위와 같은 배열을 오름차순으로 정렬한다고 하자. 두번 째 원소인 5부터 시작하여 그 앞의 원소들과 비교를 시작한다. 5와 7을 비교해 5가 더 작으므로 7을 한칸 뒤로 옮기고 그 자리에 5를 삽입한다. 세 번째 원소인 1과 그 앞의 원소 7을 비교해 1이 더 작으므로 7을 한 칸 뒤로 민다. 그 앞의 원소 5와 1을 비교해 1이 더 작으므로 5를 한 칸 뒤로 밀고 1을 그 자리에 삽입한다. 네 번째 원소인 4와 그 앞의 원소 7을 비교해 4가 더 작으므로 7을 한 칸 뒤로 민다. 그 앞의 원소 5와 4를비교해 4가 더 작으므로 5를 ..

선택정렬(Selection Sort) 선택정렬은 현재 위치에 들어갈 값을 찾아서 바꾸는 알고리즘이다. 오름차순으로 정렬하는 선택정렬은 다음과 같은 과정을 가진다. 1. 현재 정렬되지 않은 가장 맨 앞의 인덱스를 선택한다. 2. 현재 인덱스의 다음 인덱스부터 끝까지 가장 작은 값을 찾으면 현재 인덱스의 값과 바꿔준다. 3. 다음 인덱스에서 위 과정을 반복한다. 예를 들어 위와 같은 배열을 오름차순으로 선택정렬한다고 하자. 가장 먼저 맨 앞의 7부터 시작한다. 7뒤의 값들 중 가장 작은 값인 1과 자리를 바꾼다. i는 현재 인덱스, minIdx는 가장 작은 값의 인덱스를 나타낸다. 다음은 5와 그 이후 값들 중 가장 작은 값인 3의 위치를 바꿔준다. 다음으로 7과 그 이후 값들 중 가장 작은 값인 4의 위치..

버블 정렬 버블정렬은 현재 원소와 다음 원소를 비교하여 조건에 맞으면 교환하는 식의 정렬이다. 원소가 거품처럼 올라오는 듯하여 버블정렬이라고 부른다. 처음 7과 5를 비교하여 7이 더 크므로 위치를 바꾼다. 이후 배열의 끝까지 비교해서 값이 더 크다면 위치를 바꾼다. 다시 5와 1을 비교해 5가 더 크므로 위치를 바꿔준다. 이번엔 정렬이 끝난 7 전까지만 해당 과정을 반복 해준다. 다시 1과 4를 비교하여 1이 더 작으므로 위치를 바꾸지않는다. 이후 4와 3을 비교했을 때 4가 더 크므로 위치를 바꿔준다. 1과 3을 비교하여 1이 더 작으므로 위치를 바꾸지 않는다. 이렇게하면 버블정렬이 완료된다. 버블정렬의 특징 버블정렬은 하나의 배열에서 값을 바꾸는 식으로 동작하므로 공간복잡도는 O(1)이다. 선택정렬..