정렬

[알고리즘]퀵 정렬(Quick Sort)

퀵정렬이란? 퀵정렬은 이름그대로 빠른정렬, 즉 다른 정렬알고리즘에 비해 빠르다고 할 수 있습니다. 다른원소와의 비교를 통해 정렬이 이루어지므로 비교정렬에 속하고, 같은 수가 있는 경우 같은 수의 순서가 달라질 수 있어서 불안정 정렬에 속합니다. ex) 5(1), 5(2), 3, 2, 1 -> 1, 2, 3, 5(2), 51(1) 시간복잡도 최악의 경우 O(n^2) 평균 O(n log n) 알고리즘 임의의 수(pivot)를 고른다. 피벗을 기준으로 두 수를 비교하여 왼쪽에는 pivot보다 작은 수, 오른쪽에는 pivot보다 큰 수가 오도록 분할한다. 분할된 리스트 가운데에 피벗을 위치 시키고, 양쪽 리스트에 대해 재귀적으로 수행한다. 예제 가장 오른쪽에 있는 4를 pivot으로 정함. pivot을 제외하고..

[알고리즘]삽입정렬(Insertion Sort)

삽입정렬이란? 두번째 수부터 자신 왼쪽의 수와 비교하여 내가 더 작으면 왼쪽으로 이동하고, 크면 오른쪽 위치를 유지합니다. 위치를 유지했으면 그 수에 대한 비교는 종료 왼쪽으로 이동했으면, 다시 자신의 왼쪽 수와 비교를 반복합니다. 내 왼쪽과 비교 내가 더 크면 현재 위치 유지 내가 더 작으면 왼쪽 수와 교체(swap) 다시 1번단계부터 비교 반복 마지막 수 까지 비교완료하면 종료 시간복잡도 최악의 경우는 역으로 정렬되어 있는 경우 n-1, n-2, ... 1만큼 비교하여 시간복잡도 O(n^2)입니다. 소스코드(C++) #include using namespace std; void insertion_sort(int arr[],int size){ //삽입정렬 for(int i = 1;i0&&arr[j-1]..

[알고리즘]선택정렬(Selection Sort)

선택정렬이란? 선택정렬은 앞에서부터 쭉 탐색하면서 가장 작은 수를 찾습니다.(오름차순의 경우) 그리고 그 수를 (정렬되지 않은 부분의)맨앞의 수와 교체합니다. 이 과정을 정렬되지 않은 수가 1개 남을 때까지 반복하면 됩니다. 이 때 배열을 정렬된 부분과 정렬되지 않은 부분으로 나눌 수 있습니다. 탐색은 정렬되지 않은 부분에 대해서만 이루어 집니다. 주황색 - 정렬된 부분 흰색 - 정렬되지 않은 부분 하늘색 - 정렬되지 않은 수 중 가장 작은 수 정렬되지 않은 부분에서 가장 작은 수를 찾는다. 정렬되지 않은 부분의 맨 앞의 수와 가장 작은 수를 교환(swap)한다. 교환된 가장 작은 수는 정렬된 부분이 된다. 정렬되지 않은 부분에서 위 과정을 반복하고, 모두 정렬되면 종료 시간복잡도 가장 작은 수를 찾는데..

[알고리즘]버블 정렬(Bubble Sort)

정렬 알고리즘에는 대표적으로 병합정렬, 퀵정렬, 삽입정렬, 선택정렬, 버블정렬 등이 있습니다. 이번에는 그 중에서 제일 간단하게 구현할 수 있는 버블 정렬을 알아보겠습니다! 버블 정렬(오름차순) 버블 정렬은 앞에서부터 두수를 비교하며 가장 큰수를 찾고, 남은 수를 다시 두개씩 비교하며 그 다음으로 큰 수를 찾는 과정을 원소가 1개 남을 때까지 반복하는 정렬 알고리즘입니다. 시간 복잡도 위 예시에서 n = 5이므로 제일 큰 숫자인 5를 찾는데까지 4번(=n-1번)이 걸리고 다음으로 큰 숫자인 4를 찾는데까지 3번(=n-2번)이 걸립니다 총 4+3+2+1번이 걸립니다. n개의 수를 정렬하는 시간은 n-1+n-2+n-3+...1이므로 ((n-1)(n-2))/2 = O(n^2)입니다. 최선, 최악의 경우 모두 ..