📂 자료구조/정렬

카운팅 정렬 (Counting Sort)

1. 개념 👑 '계수 정렬'이라고도 불리는 '카운팅 정렬(Counting Sort)'은 각 원소들이 몇 개씩 있는지 나타내는 count배열을 활용하는 정렬 알고리즘이다. 각 원소의 값이 count 배열의 인덱스가 되므로 '정수나 정수로 표현할 수 있는 자료'에 대해서만 적용 가능하다. 2. 동작방식 🎓 동작 방식은 다음과 같다. 원소의 최댓값을 포함할 수 있는 배열 설정 각각의 원소가 몇 번 등장하는지 카운팅 count 배열의 인덱스 = 원소 값 count 배열의 값 = 등장 횟수 count 배열을 누적합으로 만들어주기 정렬되지 않은 배열(초기값)의 뒤에서부터 돌면서, 원소의 값과 동일한 인덱스가 가리키는 곳에 원소 배치해 주기 '0 2 1 1 4 4 4 3 5'가 주어졌을 때 동작방식을 아래의 그림을 ..

퀵 정렬 (Quick Sort)

1. 정의 👨‍🚀 퀵 정렬(Quick Sort)은 분할 정복 방법을 이용하는 정렬 알고리즘이다. 퀵 정렬은 피벗(Pivot)을 기준으로 분할과 정복이 이루어지게 된다. 퀵 정렬은 '피벗을 선택하는 방식'과 '재귀 또는 비재귀 방식'의 선택에 따라 다양한 구현 방법이 존재한다. 이번 글에서는 '왼쪽 피벗을 선택하는 방식'과 '재귀 방식'을 통한 퀵 정렬을 알아보도록 하자. 2. 동작 방식 🦸‍♂️ 기본적인 동작 방식은 아래와 같다. 배열에서 임의의 원소인 pivot을 선택한다. (해당 글에서는 배열에서 제일 왼쪽 원소를 pivot으로 선택한다.) pivot을 기준으로 pivot보다 작은 원소는 왼쪽으로, pivot보다 큰 원소는 오른쪽에 오도록 배열을 배치한다. pivot을 기준으로 나누어진 왼쪽 배열과 ..

힙 정렬 (Heap Sort)

1. 정의 🏄‍♂️ 힙정렬이란 자료구조 힙(Heap)을 기반으로 하는 정렬 방식이다. 오름차순 정렬일 경우 최대힙을 이용하고 내림차순 정렬일 경우 최소힙을 이용한다. 간단하게 설명하자면 힙 정렬은 루트노드를 제거하고 제거된 루트 노드를 배열의 뒷부분부터 채워 넣으면서 정렬이 이루어지는 것이다. 2. 동작 방식 🚣‍♂️ 최대힙을 이용하여 오름차순으로 정렬하는 경우를 생각해 보자. 가장 쉽게 생각할 수 있는 동작방식은 아래와 같다. 정렬해야 하는 원소들을 하나씩 힙에 넣어준다. 삭제를 하면서 루트 노드를 가져오고 그것을 배열의 뒷부분부터 채운다. 이렇게 한다면 기존 배열로부터 힙을 구성하는 배열 하나를 추가적으로 만들고(1번 과정), 뒷부분부터 정렬된 원소들을 넣을 배열을 하나 더 만들어야 한다.(2번 과정..

위상 정렬(Topology Sort)

1. 정의 🧊 위상 정렬(Topology Sort)이란 순서가 정해져 있는 작업을 차례대로 수행할 때 그 순서를 결정해 주는 알고리즘이다. 교육과정의 선수과목이 위상 정렬을 설명하는 가장 적절한 예시이다. 컴퓨터 공학을 전공하고 있는 학생은 다음 전공과목(ex. 알고리즘)을 듣기 위해서는 선수 과목(ex. 자료구조)을 필수적으로 들어야 한다. 기초컴퓨터프로그래밍 → 자료구조 → 알고리즘 자료구조 → 논리회로및설계 → 논리회로실험 알고리즘 → 논리회로및설계 → 논리회로실험 또한, 위상정렬은 위와 같이 여러 개의 경로가 존재할 수 있다. 마지막 특징으로는 위상 정렬은 비순환 유향 그래프(DAG - Directed Acyclic Graph)에만 적용이 가능하다. 즉, 사이클이 발생하지 않는 방향 그래프여야 한..

병합 정렬(Merge Sort)

합병정렬이라고도 불리는 병합정렬에 대해서 알아보자. 1. 정의 🎃 병합정렬이란 정렬해야 하는 배열을 가장 작을 때까지 나누고, 그 시점부터 인접한 부분배열끼리 비교하며 정렬하는 알고리즘이다. 해당 알고리즘은 분할 정복(Divide and Conquer) 알고리즘을 기반으로 한다. (분할 정복(Divide and Conquer)이란 문제를 분할하고, 분할한 문제를 정복하여 합치는 것이다.) 2. 동작 방식 🎪 주어진 배열을 절반으로 분할하여 부분배열로 나눈다. - 분할(Divide) 해당 부분배열의 길이가 1이 될 때까지 계속해서 1번 과정을 반복한다. 인접한 부분 배열끼리 합친다. - 정복(Conquer) 위의 그림을 통해 알 수 있듯이 크기가 1이 될 때까지 분할이 진행된다. 그리고 인접한 배열끼리 합..

삽입 정렬(Insertion Sort)

1. 정의 🧵 삽입 정렬은 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 카드 예시를 살펴보면 쉽게 이해할 수 있을 것이다. '4, 2, 3, 1, 5'라는 숫자 적힌 5장의 카드가 순서대로 있다고 하자. 앞에서부터 순서대로 카드를 뽑으면서 손에 쥔다고 생각하자. 뽑힌 카드는 이미 손에 쥐어진 카드들 사이에 위치를 찾아들어간다. 이미 손에 쥐어져 있는 카드들 뽑은 카드 자신의 위치를 찾아들어간 모습 4 4 4 2 2 4 2 4 3 2 3 4 2 3 4 1 1 2 3 4 1 2 3 4 5 1 2 3 4 5 1번 숫자가 적힌 카드가 자신의 위치를 찾아가는 것을 다시 한번 살펴보자. 1번 카드는 4번과 비교하고, 3번과 비교하고, 2번과 ..

선택 정렬(Selection Sort)

선택 정렬은 여러 가지 면에서 앞에서 살펴본 버블 정렬과 상당히 비슷하다. 두 가지 정렬 방법을 구분하는 게 어렵지는 않으니, 선택 정렬을 공부하는 김에 버블 정렬도 같이 공부하는 것을 추천한다. 1. 정의 🎿 선택 정렬은 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 2. 동작 방식 🧦 N개의 원소가 있다고 하자. 우선, 배열에서 최솟값을 찾는다. 그리고 첫 번째 원소와 배열에서 찾은 최솟값의 원소를 바꿔준다. 이것이 1회전 수행한 것이다. 이렇게 되면 배열의 첫 번째에 위치한 원소가 가장 작은 값을 가지게 된다. 2회전을 수행할 때는 첫 번째 원소를 제외한 나머지 배열들 중에서 최솟값을 찾는다. 그리고 해당 원소와 배열의 두 번째 원소를 바꿔준다. 이와 같은 방식으..

버블 정렬(Bubble Sort)

거품 정렬이라고도 불리는 버블 정렬에 대해서 알아보자. 1. 정의 👟 버블 정렬은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 2. 동작 방식 👞 N개의 원소가 있다고 하자. 첫 번째 원소와 두 번째 원소를 비교하여 만약 첫 번째 원소가 더 크다면 둘의 자리를 바꿔준다. 그리고 두 번째 원소와 세 번째 원소를 비교하여 만약 두 번째 원소가 더 크다면 둘의 자리를 바꿔준다. 이러한 동작을 (마지막 - 1) 번째의 원소와 마지막 원소를 비교할 때까지 수행한다. 이것이 1회전 수행한 것이다. 이렇게 되면 마지막에 위치한 원소가 가장 큰 원소가 된다. 2회전을 수행할 때 마지막 원소를 제외한 나머지들을 정렬해 준다. (N - 1) 회전까지 수행하면 정렬이 마무리된다. 위의 방식은 오름차순으로 정렬을 ..