설명 빗질 정렬은 버블 정렬의 답답함을 해결하기 위해 고안된 비교적 간단한 정렬이다. 정렬을 거북이와 토끼에 비유를 했는데, 버블 정렬을 거북이라 비유하고, 해결하기 위한 방법으로 거북이를 토끼처럼 만드는 것으로 생각하였다 기본 설명 1. 기본 과정은 버블 정렬 (Bubble Sort) 와 동일하다 2. 특정한 감소량 (shrink factor) 를 통해 차이 (Gap)을 줄여가며 버블 정렬을 실행한다 3. shrink factor는 1.3이 가장 이상적이라는 소문이 있으나, 가장 빠른 수치로 결정하면 됨 4. Gap 이 결정되면 해당 대상과의 Gap 만큼 차이가 나는 노드의 크기를 비교하여 버블 정렬을 수행함 시간 복잡도 시간복잡도는 O(n^2)으로 버블 정렬을 개선했다고는 하나, shrink fact..
설명 버블 정렬은 연속된 두 개의 Index를 비교하여 정렬한 다음, 후 순위 숫자와 다음 Index를 다시 연속적으로 비교하여 정렬하는 방법이다 기본 로직 두 번째 Index부터 시작한다 현재 Index와 바로 이전의 Index 값을 비교한다 이전 Index가 크면, 현재 Index와 값을 바꿔준다 현재 Index가 크면, 다음 두 연속된 배열 값을 비교한다 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 1 ~ 4 항목을 반복한다 시간복잡도 1부터 비교를 시작하여, n-1, n-2, ..., 1개를 반복하며, 전체를 대상으로 비교를 진행하므로 O(n^2)이다 코드 void BubbleSort(vector v) { for(int i = 0; i < v.size()-1; i++) { for(int ..
설명 삽입 정렬은 현재 위치에서, 그 다음 배열들을 비교하며 자신이 들어갈 위치를 찾아 삽입하는 알고리즘이다 기본 로직 두 번째 Index부터 시작 현재 Index는 별도의 변수에 저장하고, 비교 Index는 현재 Index - 1로 설정 별도로 저장해 둔 변수의 값과 비교 Index의 값을 비교 저장된 변수의 값이 더 작으면 현재 비교 Index로 저장, 비교 Index - 1하여 비교를 반복 저장된 변수의 값이 더 크면, 비교 Index + 1에 저장 시간 복잡도 최악의 경우 n-1, n-2, ... , 1개를 반복하여 O(n^2) 이미 정렬되어 있는 경우 1번씩만 하기 때문에 O(n) 코드 void InsertionSort(vector v) { for(int i = 0; i < v.size(); i..
설명 선택정렬은 현재 위치에 들어갈 값을 찾아 배열을 정렬한다. 현재 위치에 저장되는 값에 따라 최소 선택 정렬(Min-Selection)와 최대 선택정렬(Max-Selection)로 나뉜다 기본 로직 정렬되지 않은 Array의 Index의 맨 앞을 대상으로 이후 가장 작은 값을 찾는다 (최솟값 찾기) 가장 작은 값을 찾으면, 현재 Index의 위치의 값과 바꾼다 다음 Index에서 위 1, 2번 과정을 반복한다 시간 복잡도 n-1개, n-2개, ..., 1개의 비교를 반복한다. 전체 비교를 진행하므로 시간복잡도는 O(n^2)이다 코드 (C++) void SelectionSort(vector v) { for(int i = 0; i < v.size()-1; i++) { int temp = i; for(in..
