정리 노트

삽입 정렬 정렬을 하다 보면 배열 안의 데이터들을 정렬된 부분과 정렬되지 않은 부분으로 나눌 수 있습니다. 삽입 정렬은 정렬되지 않은 데이터들 중 가장 앞의 데이터를 정렬된 부분에서의 자기 위치를 찾아 정렬하는 방법입니다. 정렬 과정 길이가 6인 정수형 배열({3, 1, 4, 4, 6, 5})을 정렬해봅시다. 먼저 3을 정렬하려면 정렬된 부분과의 대소 비교를 통해 자기 위치를 찾아야 합니다. 하지만 지금은 정렬 시작 단계이기 때문에 정렬된 부분이 없습니다. 따라서 실질적인 삽입 정렬의 시작은 두 번째 원소인 '1'에서부터 시작하고 3은 정렬된 부분으로 포함시킵니다. 정렬되지 않은 원소들 중 가장 앞인 '1' 원소의 위치를 찾기 위해 정렬된 부분의 '3'과 비교합니다. 1이 3보다 작으므로 3과 1의 위치..

선택 정렬(Selection Sort) 선택 정렬은 원소들 중 가장 작은(큰) 값을 정렬되지 않은 부분의 가장 왼쪽(오른쪽)과 swap 하는 정렬 알고리즘입니다. 과정 길이가 6인 정렬되지 않은 정수형 배열({1, 2, 4, 6, 3, 5})를 정렬한다고 해봅시다. 1과 2는 이미 작은 순으로 정렬되어있으므로 여기에 대해서는 swap이 일어나지 않습니다. 다음에는 정렬되지 않은 부분에서 가장 작은 값은 3입니다. 3을 제 위치에 놓기 위해 4와 자리를 swap 합니다. 나머지 4, 5 원소도 위와 같은 단계를 거쳐 배열 정렬을 마무리합니다. 선택 정렬 코드(C++) #include using namespace std; void selectionSort(int[], int); int main() { int..

이번 포스트도 버블 정렬에 대해 알고 있다는 가정 하에 작성되었습니다. 버블 정렬을 모르시는 분들은 제가 전에 적었던 글을 참고하시기 바랍니다. 2022.09.05 - [알고리즘] - 버블 정렬(Bubble sort) Comb Sort 2022.09.06 - [알고리즘] - 칵테일 셰이커 정렬(Cocktail Shaker Sort) 에서 적었듯이 기존 버블 정렬에는 아쉬운 점이 있었습니다. 크기가 작은 데이터가 배열의 끝에 위치한 경우 제 위치로 찾아가기까지 오래 걸렸습니다. Comb Sort는 이 문제점을 개선한 정렬 알고리즘입니다. Gap 기존 버블 정렬에서는 등장하지 않았던 'gap'이 등장합니다. gap은 현재 데이터와 swap 할 데이터 간의 거리를 의미합니다. 즉 버블 정렬에서는 gap이 1이..

본 글은 버블 정렬에 대해 알고 있다는 가정 하에 작성되었습니다. 버블 정렬을 모르시는 분들은 제가 전에 썼던 글을 보고 오시면 더 편하게 이해하실 수 있습니다. 2022.09.05 - [알고리즘] - 버블 정렬(Bubble sort) 버블 정렬할 때 생기는 문제점 버블 정렬을 할 때 길이가 5인 정수형 배열({5, 4, 3, 2, 1})을 정렬한다고 생각합시다. 5는 1번의 pass로 제 위치로 갈 수 있지만 1은 마지막 pass까지 진행해야 제 위치로 갑니다. 이렇듯 정수형 배열을 정렬할 때 값들이 임의로 섞여있는 경우 큰 값들은 적은 pass를 통해 정렬되지만 작은 값들은 거의 마지막 pass까지 진행해야 합니다. 여기서 크기가 작은 값들을 빠르게 제 위치로 이동시킬 수 있는 칵테일 셰이커 정렬(C..

버블 정렬 버블 정렬은 인접한 두 원소의 크기 비교로 정렬이 진행되는 방법입니다. 여기서의 설명은 오름차순으로 정렬하는 것을 기준으로 진행됩니다. 사실 내림차순 정렬은 비교만 바꾸면 되기 때문에 큰 상관은 없습니다. 기본 버블 정렬 처음부터 끝까지 서로 비교하는 것을 하나의 pass라 부릅시다. 한 번의 pass를 거치면 가장 큰 원소가 오른쪽으로 이동하게 됩니다. 예를 들어 길이가 4인 정수형 배열을 정렬한다고 가정하고, 배열 안의 원소는 random 하게 섞여있다고 합시다. 위처럼 첫 번째 pass가 끝나면 가장 큰 원소인 '4'가 배열의 끝에 위치하게 됩니다. 이와 같은 과정을 반복하면 아래처럼 정렬된 배열을 얻을 수 있습니다. 이를 C++ 코드로 구현하면 아래와 같습니다. #include usin..