내부정렬 vs 외부정렬
내부정렬
internal sort
정렬할 자료의 양이 적어서 자료 전체가 주기억장치에 저장될 수 있는 경우에 내부정렬을 사용한다
외부정렬
external sort
자료의 양이 많을 때는 속도가 느리고 접근 방식이 제한적인 보조기억장치에 전체 자료를 두고 자료의 일부분을 한번에 조금씩 주기억장치에 옮겨와서 정렬한다.
비교기반정렬 vs 분포기반 정렬
비교기반 정렬
comparison-based
선택 정렬, 버블 정렬, 삽입 정렬, 쉘 정렬, 퀵 정렬, 합병 정렬, 힙 정렬
분포기반 정렬
distribution-based
특징이 있는 데이터에 사용
계수 정렬, 기수 정렬, 버킷 정렬
제자리성
in place algorithm
제자리성을 갖는 알고리즘은 입력 원소 외에 별도에 메모리에 저장되는 원소의 개수가 상수개를 넘지 않는 알고리즘을 말한다.
안정성
안정성을 갖는 알고리즘은 동일한 값을 갖는 데이터에 대하여 정렬 전과 후의 데이터 순서가 그대로 유지되는 알고리즘이다.
보통 인접한 원소들끼리만 비교하는 정렬은 안정성을 갖는다.
선택 정렬
selection sort - 책 293p
배열에서 가장 작은 원소를 찾아서 맨 앞에 놓고, 그 다음 작은 원소를 찾아서 맨 앞에 놓고... 반복해서 정렬한다.
SelectionSort.h
typedef int Data;
void selectionSort(Data * arr,int length);
int compare(Data d1, Data d2);
void swap(Data* arr, int index1, int index2);
void showArr(Data* arr, int length);typedef 부분만 바꾸면 다른 자료형에 대해서도 사용할 수 있다.
SelectionSort.cpp
#include "SelectionSort.h"
#include <iostream>
using namespace std;
void showArr(Data* arr, int length) {
for (int i = 0; i < length; i++) {
cout << arr[i] << " ";
}
cout << endl << endl;
}
//arr배열의 index1 원소와 index2 원소 자리 교체
void swap(Data* arr, int index1, int index2) {
Data temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
//d1>d2이면 1 , d1==d2이면 0, d1<d2이면 -1 반환
int compare(Data d1, Data d2) {
if (d1 > d2) {
return 1;
}
else if (d1 == d2) {
return 0;
}
else {
return -1;
}
}
//arr 선택정렬
void selectionSort(Data* arr, int length) {
int minIndex = 0;
//i=0부터 length-2 인덱스 까지 반복
//j로 i 다음부터 끝까지 반복, minIndex에 최솟값의 인덱스값을 저장
for (int i = 0; i < length - 1; i++) {
minIndex = i;
for (int j = i + 1; j < length; j++) {
if (compare(arr[minIndex], arr[j])>0) {
minIndex = j;
}
}
swap(arr, i, minIndex);
showArr(arr, length);
}
}
주석에 자세한 설명이 있다.
배열의 앞부분부터 작은 원소가 하나씩 정렬된다.
하나씩 정렬될 때 마다 showArr로 과정을 출력하고자 했다.
main.cpp
#include "SelectionSort.h"
#include <random>
int main() {
srand(time(NULL));
int arr[10];
for (int i = 0; i < 10; i++) {
arr[i] = rand() % 100 + 1;
}
showArr(arr, 10);
selectionSort(arr, 10);
//showArr(arr, 10);
return 0;
}
실행 결과는 다음과 같다.
가장 작은 원소부터 맨 앞쪽에 배치된다.
성능
n개의 아이템이 있다면 외부 루프는 n-1번 실행된다.
i번째 외부 루프에는 i+1부터 n번째 원소까지 교환 연산하게 된다.
따라서 i=1~n-1일 때 총 비교 연산 횟수는
n-1 + n-2 + n-3 + .... + 1 = ((n-1)n)/2
이다.
선택 정렬의 복잡도는 θ(n2)이다.
교환연산을 고려하면
교환연산 : θ(n)
비교연산 : θ(n2)
일반적으로 교환은 데이터가 이동하기 때문에 교환이 비교보다 느리다.
이 차이는 데이터의 크기가 클수록 커진다.
시간복잡도
평균시간복잡도 : O(n2)
최악시간복잡도 : O(n2)
제자리성
상수 크기 메모리밖에 사용하지 않으므로 제자리성 정렬이다
안정성
불안정한 정렬이다.
이웃한 원소끼리만 비교하지 않는다.
수정
교환 연산 (코드에서 swap 부분)이 불필요하게 발생하는 경우가 있다.
예를 들어 외부 루프의 첫번째 원소가 최소 원소일 경우 swap을 자기 자신과 자신을 교환하도록 호출하게 된다.
#include "SelectionSort.h"
#include <iostream>
using namespace std;
void showArr(Data* arr, int length) {
for (int i = 0; i < length; i++) {
cout << arr[i] << " ";
}
cout << endl << endl;
}
//arr배열의 index1 원소와 index2 원소 자리 교체
void swap(Data* arr, int index1, int index2) {
Data temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
//d1>d2이면 1 , d1==d2이면 0, d1<d2이면 -1 반환
int compare(Data d1, Data d2) {
if (d1 > d2) {
return 1;
}
else if (d1 == d2) {
return 0;
}
else {
return -1;
}
}
//arr 선택정렬
void selectionSort(Data* arr, int length) {
int minIndex = 0;
//i=0부터 length-2 인덱스 까지 반복
//j로 i 다음부터 끝까지 반복, minIndex에 최솟값의 인덱스값을 저장
for (int i = 0; i < length - 1; i++) {
minIndex = i;
for (int j = i + 1; j < length; j++) {
if (compare(arr[minIndex], arr[j])>0) {
minIndex = j;
}
}
if (minIndex != i) {
swap(arr, i, minIndex);
}
showArr(arr, length);
}
}
selectionSort 함수에 minIndex!=i 일때만 swap을 호출하도록 수정했다.
이렇게 하면 교환 횟수의 복잡도가 O(n)이 된다.
만약 배열이 이미 정렬되어 있다면 수정 전 알고리즘과 수정 후 알고리즘의 차이가 클 것이다.
하지만 n-1회의 minIndex!=i의 비교 연산이 추가된 것이므로 무조건 이득인지는 알 수 없다. 교환 횟수가 그만큼 준다는 보장이 없기 때문이다.
활용
선택 정렬은 방법이 간단하며 구현하기 쉽다.
선택 정렬에서는 교환을 적게 하는것이 중요하다.
따라서 충분히 성능을 발휘하는 작은 배열에는 적합하지만, 더 나은 정렬 알고리즘으로 더 좋은 결과를 얻을 수 있는 큰 배열에는 사용하지 않는다.
버블 정렬
bubble sort - 책에 없음
입력 : 길이가 n인 배열 A
각 단계에서 왼쪽 -> 오른쪽으로 이동하며 인접한 두개의 원소를 비교해서 왼쪽 원소가 더 클 경우 두 원소의 위치를 바꾼다.
i번째 단계를 완료하면 배열에서 i번째로 큰 원소가 A[n-i] 에 위치하게 된다.
BubbleSort.cpp
#include "BubbleSort.h"
#include "SortBasics.h"
#include <iostream>
using namespace std;
void bubbleSort(Data* arr, int length) {
//총 length개의 원소
//i번째 외부 루프를 시행하면 뒤쪽부터 i개의 원소가 정렬됨
//i=legnth-2면 뒤쪽부터 length-2개가 정렬되고 남은 원소는 2개
//i=length-1이면 남은 원소 1개, 1개를 정렬하는건 의미가 없으므로 i는 length-1까지가 맞다
for (int i = 1; i < length - 1; i++) {
//j는 0부터 length-i-1까지 j와 j+1번째 원소를 비교한다.
//i=1일때 j는 0~length-2이다. j=length-2일때 length-2와 length-1번째 (마지막) 까지 비교한다.
for (int j = 0; j < length - i; j++) {
if (compare(arr[j], arr[j + 1]) > 0) {
swap(arr, j, j + 1);
}
}
showArr(arr, length);
}
}
주석에 자세하게 설명이 써있다.
SortBasics.h에 swap, compare, showArr 같은 함수들을 넣었다.
실행결과를 보면 i번째 외부 루프마다 i번째로 큰 원소가 배열의 A[length-i]로 정렬되는 것을 확인할 수 있다.
시간 단축 방법
한 사이클을 시작하기 전에 전 사이클에서 자리 바꿈이 발생했는지 확인한다. (swap을 호출했는지 확인한다)
만약 swap을 호출하지 않았다면 이미 정렬이 완료된 것이므로 사이클을 시작하지 않고 정렬을 종료하면 된다.
#include "BubbleSort.h"
#include "SortBasics.h"
#include <iostream>
using namespace std;
void bubbleSort(Data* arr, int length) {
//swapCalled를 이용해서 전 단계에서 swap을 호출했는지 확인한다
bool swapCalled = true;
//총 length개의 원소
//i번째 외부 루프를 시행하면 뒤쪽부터 i개의 원소가 정렬됨
//i=legnth-2면 뒤쪽부터 length-2개가 정렬되고 남은 원소는 2개
//i=length-1이면 남은 원소 1개, 1개를 정렬하는건 의미가 없으므로 i는 length-1까지가 맞다
for (int i = 1; i < length - 1; i++) {
if (swapCalled == false) {
break;
}
swapCalled = false;
//j는 0부터 length-i-1까지 j와 j+1번째 원소를 비교한다.
//i=1일때 j는 0~length-2이다. j=length-2일때 length-2와 length-1번째 (마지막) 까지 비교한다.
for (int j = 0; j < length - i; j++) {
if (compare(arr[j], arr[j + 1]) > 0) {
swap(arr, j, j + 1);
swapCalled = true;
}
}
showArr(arr, length);
}
}
swapCalled 라는 bool 형 변수로 swap의 호출 여부를 판단했다.
일부로 거의 정렬된 배열을 대상으로 테스트해봤다.
시간복잡도
O(n2)이다.
길이가 n인 배열에서 외부 루프를 n-2번
i번째 외부 루프에서 비교 연산을 n-i번 한다.
i=1~n-2므로 계산하면 최고차항이 n2이된다.
제자리성
상수 크기 메모리를 활용하므로 제자리성을 갖는다.
안정성
인접한 원소랑만 비교하기 때문에 안정성이 있다.
삽입 정렬
insertion sort - 책 297p
이미 정렬된 아이템 사이에 새로운 아이템을 맞는 위치에 삽입하기 때문에 삽입정렬이다. 카드를 한장씩 받아서 정렬한다고 생각해보자. 두번째 카드를 받으면 첫번째 카드랑 비교해서 정렬하고, 세번째 카드를 받으면 또 이미 받은 두장의 카드랑 비교해서 알맞은 위치에 놓는다.
insertionSort.cpp
#include "InsertionSort.h"
#include "SortBasics.h"
void insertionSort(Data* arr, int length) {
int j = 0;
//i=1~length-1까지
for (int i = 1; i < length; i++) {
j = i;
//j=i부터 j와 j-1 원소값을 비교해서 j-1원소값이 더 크다면 두 원소의 자리를 바꾸고 j-=1을 해준다
//while을 사용한 이유는 i번째 사이클마다 배열 앞의 i개의 원소가 정렬된다
//만약 j와 j-1을 비교했는데 j가 더 크다면 어차피 더 앞의 원소들이랑 비교할 필요가 없다
//그래서 while의 조건을 이렇게 작성함
while (compare(arr[j-1],arr[j])>0&&j>0) {
swap(arr, j - 1, j);
j -= 1;
}
showArr(arr, length);
}
}
정렬되는 과정을 확인할 수 있다.
시간 복잡도
교재에서는 시간복잡도를 교환/비교를 분리해서 분석한다
교안에서는 비교연산만 셌다. 교안의 방식으로 일단 작성했다.
-
최선시간복잡도
최선의 경우라면 배열이 이미 정렬되어 있을때다.
배열이 이미 정렬되어 있다면 각 외부 사이클마다 while문의 조건에서 compare을 한번씩만 호출하고 탈출할 것이다. 따라서 n-1번의 비교가 발생한다. 즉 O(n)이다. -
최악시간복잡도
i번째 사이클에서 j=1~i까지 i-1번의 비교연산이 발생한다.
계산해보면 최고차항이 n2니까 O(n2)이다. -
평균시간복잡도
i번째 사이클에서 최악일 경우 i-1번 비교하고 최선일 경우 1번 비교한다.
따라서 평균 i/2번 비교한다.
i=1~n-1에서 계산해보면 최고차항은 n2니까 O(n2)이다.
쉘 정렬
삽입 정렬의 단점 : 현재 삽입하고자 하는 키가 들어가야 할 위치에서 멀어도 인접한 원소랑 비교하면서 한번에 한자리씩만 이동한다. 이것을 보안하기 위한 방법이 쉘 정렬이다.
배열을 부분배열로 나눠서 각 부분배열에 삽입정렬을 적용한다.
원소가 12개인 배열에서 4칸씩 떨어진 원소들을 모아 부분배열을 만들고 각각 삽입정렬을 적용한다음. 전체 배열에 다시 삽입정렬을 적용할 수 있다.
이렇게 하면 각 한번의 비교 후 원소가 4자리씩 이동하기 때문에 일반적으로 원소가 더 빨리 제자리에 접근하게 된다.
이것을 일반화 한 것이 쉘 정렬이다.
부분배열의 개수를 바꾸어 가면서 이 과정을 여러번 거치는 것이다.
부분배열의 개수는
퀵 정렬
quick sort - 교재 320p
배열에서 피벗값을 정하고 피벗을 기준으로 앞에는 피벗보다 작은 값, 오른쪽에는 피벗보다 큰 값이 오도록 정렬한다.
피벗의 위치를 기준으로 배열을 2개로 나눠서 배열의 크기가 1 이하일 때까지 반복한다.
#include <iostream>
#include <random>
using namespace std;
//배열을 출력하기 위한 함수
void showArr(int* arr, int length) {
for (int i = 0; i < length; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
//arr 배열의 low인덱스와 high 인덱스 원소의 자리를 바꿔주는 함수
void swap(int* arr, int low, int high) {
int temp = arr[low];
arr[low] = arr[high];
arr[high] = temp;
}
//arr 배열의 왼쪽 끝 인덱스 left와 오른쪽 끝 인덱스 right를 매개변수로 받아서
//left를 피벗값으로 지정하고 피벗값 기준으로 작은 원소를 왼쪽 큰 원소를 오른쪽으로 가게 하고
//피벗값의 위치를 반환하는 함수 partition
int partition(int* arr, int left, int right) {
//low를 left로 high를 right+1로
//left는 피벗값, right+1은 인덱스를 벗어나는 값이지만 밑의 do while 문에서 low ++ high -- 로 시작해서 괜찮다
int low = left, high = right + 1;
//left 인덱스 값을 피벗으로 (기준값)
int pivot = arr[left];
do {
do {
low++;
} while (arr[low] < pivot && low <= right);
//low는 배열의 왼쪽 -> 오른쪽으로 이동하다가 pivot보다 큰 값을 찾으면 멈춘다
//이동하다가 오른쪽 끝 인덱스인 right를 넘지 않도록 한다
do {
high--;
} while (arr[high] > pivot && high >= left);
//high는 배열의 오른쪽 -> 왼쪽으로 이동하다가 pivot보다 작은 값을 찾으면 멈춘다
//이동하다가 왼쪽 맨 끝 인덱스인 left를 넘지 않도록 한다
//pivot보다 크고 작은 값을 찾아서 멈췄거나 못 찾아서 끝까지 가서 멈췄을 수도 있다.
//low<high라면 low와 high의 위치가 교차되지 않은 것이고 pivot보다 큰값, 작은값을 찾아서 멈춘것이다
if (low < high) {
//따라서 low와 high의 위치를 바꿔준다
swap(arr, low, high);
}
} while (low < high);
//위의 while문을 탈출했다는 것은 low와 high의 교차가 발생한 것이다
swap(arr, left, high);
//맨 왼쪽 인덱스인 left와 오른쪽->왼쪽으로 이동하던 high의 자리를 바꿔준다.
//left는 피벗 값이고 high는 오른쪽 끝에서 왼쪽으로 이동하며 자리의 값이 pivot보다 작다면 왼쪽으로 옮겼다.
//따라서 high의 자리에 피벗값을 놓으면 피벗값 기준으로 왼쪽 오른쪽이 작고 큰 값이 된다
//피벗값의 인덱스를 반환한다
return high;
}
//퀵 정렬 함수에서는 arr와 왼쪽 끝 인덱스 left 오른쪽 끝 인덱스 right를 매개변수로 받는다
void quickSort(int* arr, int left, int right) {
int k = 0;
//left<right라면 원소의 개수가 2개 이상이므로 반복
if (left < right) {
//partition을 이용해 정렬하고 피벗의 위치를 k에 받는다
k = partition(arr, left, right);
//left ~ k-1부분과 k+1~right 부분을 다시 quicksort한다.
quickSort(arr, left, k - 1);
quickSort(arr, k + 1, right);
}
//원소의 개수가 1개 이하일 때까지 반복해서 정렬하게 된다.
}
int main() {
srand(time(NULL));
//난수 배열 생성
int arr[10];
for (int i = 0; i < 10; i++) {
arr[i] = rand() % 100000 + 1;
}
showArr(arr, 10);
quickSort(arr, 0, 9);
showArr(arr, 10);
return 0;
}partition 함수를 보면 피벗값은 배열의 맨 왼쪽 끝인 left로 정한다.
그리고 low와 high 변수를 이용해 배열의 왼쪽, 오른쪽에서 각각 탐색한다.
low는 배열의 왼쪽 끝에서 오른쪽으로 이동하며 피벗보다 큰 값을 찾으면 멈춘다.
right는 배열의 오른쪽 끝에서 왼쪽으로 이동하며 피벗보다 작은 값을 찾으면 멈춘다.
멈추고 나서 low<high인지 먼저 확인한다. low>=high라면 두 위치가 교차되버린 것이므로 이 사이클을 그만해도 된다.
low<high라면 아직 교차된게 아니다. 따라서 low와 high의 위치를 바꾼다.
low<high가 되서 외부 while문을 탈출했다면 left와 high위 위치를 바꿔준다.
left는 피벗값이고 high는 오른쪽 -> 왼쪽으로 이동하며 피벗보다 큰 값을 다 high의 오른쪽으로 보내놨다. 따라서 high 자리에 피벗값이 오면 피벗이 알맞은 자리를 찾은 것이다.
반환값은 high , 즉 피벗값의 위치다. 이 반환값을 이용해서 배열의 처음~피벗값 전 / 피벗값 후 ~ 배열의 끝 으로 다시 재귀적으로 퀵 정렬을 호출할 수 있다.
시간 복잡도
-- 태블릿 배터리 충전다되면 작성
최악시간복잡도
최선
비순환적 퀵 정렬
#include <iostream>
#include <random>
#define MAX_LEVEL 100
using namespace std;
void showArr(int* arr, int length) {
for (int i = 0; i < length; i++) {
cout << arr[i] << " ";
}
cout<<endl<< endl;
}
void swap(int* arr, int index1, int index2) {
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
//element = 원소의 개수
void nonRecursiveQuickSort(int* arr, int elements) {
int piv, beg[MAX_LEVEL], end[MAX_LEVEL], i=0, l, r;
beg[0] = 0, end[0] = elements;
while (i >= 0) {
l = beg[i], r = end[i] - 1;
cout << "beg : ";
showArr(beg, i+1);
cout << "end : ";
showArr(end, i+1);
cout << "l , r : " << l << "," << r << endl << endl;
//l>=r이면 반복할 필요 없음
if (l < r) {
//cout << "l , r = " << l << ", " << r << endl;
//피벗값 = arr[0]
piv = arr[l];
while (l < r) {
while (arr[r] >= piv && l < r) {
r--;
}
if (l < r) {
//l자리에 r원소 넣고 l 우로1칸이동
arr[l++] = arr[r];
}
while (arr[l] < piv && l < r) {
l++;
}
if (l < r) {
//r자리에 l넣고 r좌로 1칸이동
arr[r--] = arr[l];
}
}
//피벗값 알맞은 위치에 넣어주기
arr[l] = piv;
//현재 피벗 위치가 l이다
// 다음 정렬할 구간은 피벗 +1 ~ 끝까지 부분이다
//beg[i+1]에 피벗 다음칸
//edn[i+1]=end[i]로 이번 사이클의 오른쪽 끝을 표시하는 값을 end의 i+1인덱스로 옮긴다
// 그리고 i자리에 l을넣고 i를 1 증가시킨다.
// i자리에 l을 넣는 이유는 피벗기준 오른쪽에 계속 정렬하다가 끝나면 왼쪽부분을 해야하는데
// 그때 쓰기 위해서 저장해놓는다
//36행을보면 처음 시작할때 l = beg[i] , r = end[i]-1이다
//따라서 다음 시작할때 이번 피벗위치의 다음칸 ~ 오른쪽 끝까지 진행함
beg[i + 1] = l + 1;
end[i + 1] = end[i];
end[i++] = l;
}
else {
//이번 사이클의 피벗 오른쪽 기준 정렬을 하려는데 l<r을 만족하지 않으면 정렬할게 없다.
//그러면 왼쪽을 해야 되니까 l<r을 만족할 때까지 i가 감소하게 된다
//그러다가 전에 저장해놓은 왼쪽 부분의 인덱스까지 오면 왼쪽도 마저 정렬하게 된다.
i--;
}
showArr(arr, 10);
}
}
int main() {
srand(time(NULL));
int arr[10];
for (int i = 0; i < 10; i++) {
arr[i] = rand() % 100 + 1;
}
showArr(arr, 10);
nonRecursiveQuickSort(arr, 10);
return 0;
}이해하기 너무 어려웠다.
코드만 봐도 어떻게 정렬하는지는 알겠는데 beg과 end 배열에 의해 다음 정렬 범위가 설정되는게 너무 헷갈렸다.
beg과 end를 무시하고, 먼저 한번의 사이클에서 정렬하는 방법은 이렇다. (위 그림 참고)
l = 왼쪽 끝 인덱스, r = 오른쪽 끝 인덱스 , pivot = arr[l]
먼저 왼쪽에서 l이 오른쪽으로 이동하면서 피벗보다 큰 값을 찾는다.
찾으면 r 자리에 arr[l]을 대입한다. (swap 아님 대입하는거임)
그리고 r은 1 감소하여 왼쪽으로 이동한다.
그다음 r이 왼쪽으로 이동하면서 pivot보다 작은 값을 찾는다.
찾으면 마찬가지로 l자리에 arr[r]을 대입하고 l은 1 증가해서 오른쪽으로 이동한다.
이 과정을 반복한다. 반복하다가 l과 r이 겹치게되면 pivot값을 l자리에 넣으면 된다.
l 자리는 지금 l 왼쪽에는 다 피벗보다 작은값이고 오른쪽은 다 피벗보다 큰 값이다.
한 사이클은 이렇게 이해하면 된다.
위 과정을 재귀 없이 반복하기 위해서 beg과 end 배열을 사용한다.
beg와 end 배열은 각 사이클에서 왼쪽 끝과 오른쪽 끝을 설정하기 위해 만든 배열이다.
i=0 에서 시작한다. i는 beg와 end에서 값을 참조하기 위해 쓰인다.
처음에 beg[0]을 0으로, end[0]을 elements (배열의 길이) 로 초기화한다.
l = beg[i] , r = end[i]-1이다.
즉 배열의 왼쪽 끝, 오른쪽 끝 인덱스로 l, r값이 설정된다.
if (l < r) {
//cout << "l , r = " << l << ", " << r << endl;
//피벗값 = arr[0]
piv = arr[l];
while (l < r) {
while (arr[r] >= piv && l < r) {
r--;
}
if (l < r) {
//l자리에 r원소 넣고 l 우로1칸이동
arr[l++] = arr[r];
}
while (arr[l] < piv && l < r) {
l++;
}
if (l < r) {
//r자리에 l넣고 r좌로 1칸이동
arr[r--] = arr[l];
}
}
//피벗값 알맞은 위치에 넣어주기
arr[l] = piv;
//현재 피벗 위치가 l이다
// 다음 정렬할 구간은 피벗 +1 ~ 끝까지 부분이다
//beg[i+1]에 피벗 다음칸
//edn[i+1]=end[i]로 이번 사이클의 오른쪽 끝을 표시하는 값을 end의 i+1인덱스로 옮긴다
// 그리고 i자리에 l을넣고 i를 1 증가시킨다.
// i자리에 l을 넣는 이유는 피벗기준 오른쪽에 계속 정렬하다가 끝나면 왼쪽부분을 해야하는데
// 그때 쓰기 위해서 저장해놓는다
//36행을보면 처음 시작할때 l = beg[i] , r = end[i]-1이다
//따라서 다음 시작할때 이번 피벗위치의 다음칸 ~ 오른쪽 끝까지 진행함
beg[i + 1] = l + 1;
end[i + 1] = end[i];
end[i++] = l;
}
else {
//이번 사이클의 피벗 오른쪽 기준 정렬을 하려는데 l<r을 만족하지 않으면 정렬할게 없다.
//그러면 왼쪽을 해야 되니까 l<r을 만족할 때까지 i가 감소하게 된다
//그러다가 전에 저장해놓은 왼쪽 부분의 인덱스까지 오면 왼쪽도 마저 정렬하게 된다.
i--;
}코드의 일부분인데 여기서 핵심은 l<r 일 경우 피벗값을 arr[l]로 정하고 정렬한다. 그리고 나서 if의 마지막 부분에 보면 beg와 end 배열을 건드린다.
beg[i+1] = l+1
정렬을 한 사이클 돌린 상황에서 피벗값의 위치가 l이다. 즉 l 인덱스에 피벗값이 있고 기준으로 왼쪽에는 다 피벗보다 작고 오른쪽은 다 피벗보다 크다. 피벗위치+1, 즉 피벗의 오른쪽 인덱스를 beg[i+1]에 넣어준다.
end[i + 1] = end[i];
end[i++] = l;
end[i+1]에 end[i]값을 넣는다. end[i+1]은 이번 사이클에서 사용한 오른쪽 끝 인덱스+1인 값이다. (다시 윗부분을 보면 처음에 r을 설정할 때 end에서 가져온 값 -1로 설정한다. 즉 end에 넣는 값은 인덱스값+1)
이 값을 i+1의 위치로 옮긴다.
그리고 나서 end[i]에 l을 넣는다. l은 현재 피벗의 위치다.
그리고 나서 i를 1 증가시킨다.
이 과정을 하고 나서 다음 사이클로 넘어가서 l,r값이 어떻게 설정되는지 보자.
l = beg[i], r = end[i] - 1;
l=beg[i]이므로 전 사이클의 피벗값 +1인 값이다.
r=end[i]-1이므로 전 사이클의 r값과 동일하다.
그림으로 보면 이해가 쉽다. 피벗값 기준 오른쪽 부분으로 계속 이동하면서 정렬하는 것이다. 그런데 마지막에 보면 L==R이 되버렸다.
else {
//이번 사이클의 피벗 오른쪽 기준 정렬을 하려는데 l<r을 만족하지 않으면 정렬할게 없다.
//그러면 왼쪽을 해야 되니까 l<r을 만족할 때까지 i가 감소하게 된다
//그러다가 전에 저장해놓은 왼쪽 부분의 인덱스까지 오면 왼쪽도 마저 정렬하게 된다.
i--;
}그러면 if-else문의 else 부분이 실행된다.
i를 1 감소시킨다.
그러면 다음 사이클로 넘어가서 beg와 end에서 그 전 값을 가져와서 l,r을 설정하게 된다.
아까 사진을 다시 보면 end에는 계속 l-1값을 저장해주고 있었다.
이런 식으로 beg와 end에 저장해놓은 인덱스를 이용해서 피벗 기준 오른쪽에 더이상 정렬할 원소가 없으면 왼쪽으로 넘어와서 정렬하게 된다.
합병 정렬
Merge Sort - 교재 309p
합병 정렬은 정렬된 카드 패 2개를 합치는 방법과 비슷하다
각 카드 패의 첫번째 장을 비교하고 더 작은것을 새로운 카드패로 옮긴다
이것을 비교하다가 한 카드패가 다 사라지면 다른 카드패에 있는 카드는 모두 새로운 카드패의 카드보다 큰 카드니까 (이미 정렬된 카드패를 대상으로 한 것이므로) 뒤에 붙이면 된다.
퀵 정렬의 단점 : 분할원소에 따라 분할되는 두 부분배열의 성능이 다를 수 있어서 최악의 경우 성능이 O(n2)이다.
예를 들어 피벗 값이 배열의 최솟값이라면 피벗 값만 맨 앞으로 이동하고 나머지는 정렬되지 않는다.
합병정렬은 분할되는 두 부분배열의 크기가 항상 같다.
Left = 배열의 왼쪽 끝, Right = 배열의 오른쪽 끝, Mid = (Left+Right)/2가된다.
Mid, 즉 배열의 중간 위치를 구하여 배열을 둘로 나눈다. 원소가 하나가 될 때 까지 나눈 다음, 원소가 하나인 배열은 이미 정렬된 것이므로, 합병하면서 정렬한다.
#include "MergeSort.h"
#include <iostream>
using namespace std;
void showArr(int* arr, int length) {
for (int i = 0; i < length; i++) {
cout << arr[i] << " ";
}
cout << endl << endl;
}
void MergeSort(int* arr, int left, int right) {
//원소 개수가 2개 이상이면
if (left < right) {
int mid = (left + right) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
cout << "left : arr[" << left << "] = " << arr[left] << endl;
cout << "right : arr[" << right << "] = " << arr[right] << endl;
cout << "mid : arr[" << mid << "] = " << arr[mid] << endl;
showArr(arr, 10);
}
}
//mid기준으로 나눠서 각각 정렬된 배열 arr를 합쳐서 정렬해줌
void Merge(int* arr, int left, int mid, int right) {
//임시 저장공간 buffer
int* buffer = new int[right];
//3개의 변수 사용, bufPtr은 임시저장공간에서 저장위치를 나타냄
int leftPtr = left, rightPtr = mid + 1, bufPtr = left;
//leftPtr <= mid && rightPtr <= right은 왼쪽, 오른쪽 배열의 범위를 벗어나는지 학인
while (leftPtr <= mid && rightPtr <= right) {
//왼쪽 오른쪽 배열의 원소값을 비교해서 작은값을 buffer에 넣고 인덱스를 오른쪽으로 옮긴다
if (arr[leftPtr] < arr[rightPtr]) {
buffer[bufPtr++] = arr[leftPtr++];
}
else {
buffer[bufPtr++] = arr[rightPtr++];
}
}
//왼쪽이나 오른쪽 중 한 쪽의 배열을 buffer에 다 넣어서 위의 while문을 탈출했다면 나머지 배열을 buffer의 뒷부분에 다 넣어준다.
if (leftPtr <= mid) {
for (int i = leftPtr; i <= mid; i++) {
buffer[bufPtr++] = arr[i];
}
}
else {
for (int i = rightPtr; i <= right; i++) {
buffer[bufPtr++] = arr[i];
}
}
//arr에 buffer의 내용을 복사해준다.
for (int i = left; i <= right; i++) {
arr[i] = buffer[i];
}
}
MergeSort에서 재귀적 호출하는 순서에 의해 결과를 출력했다.
원소가 1개가 될때까지 나누고 합치면서 정렬함
시간복잡도
최악시간복잡도
힙 정렬
배열을 힙에 넣고 노드를 하나씩 제거하면서 다시 배열에 정렬한다.
힙
MaxHeap.h
//2018112424 장지담
#pragma once
#define SIZE 30
//Data typedef
typedef int Data;
//함수포인터 typedef
//
//MaxHeap의 a 인덱스 노드가 b 인덱스 노드보다 우선순위가 앞서면 true 아니면 false
typedef bool (*priorityCheck)(int a, int b);
//배열을 이용한 Max Heap
class MaxHeap {
private:
priorityCheck func;
Data arr[SIZE];
int numOfData;
public:
//생성자
MaxHeap(priorityCheck func);
void showHeap();
//Heap이 비었으면 true 아니면 false 반환
bool isEmpty();
//부모 노드의 인덱스 반환
int getParent(int index);
int getLeftChild(int index);
int getRightChild(int index);
int getHighPriorityChild(int index);
Data heapDelete();
//HeapInsert로 힙에 배열의 원소를 하나씩 넣으면서 재정비 (교안의 방법1)
void heapInsert(Data data);
//아래 두개 메소드는 교안의 방법 2로 힙 정렬하기 위한 메소드
//배열을 힙에 넣는다
void buildHeap(int* inputArr, int length);
//힙을 아래서부터 조정할 때 쓰는 메소드
void adjustHeap(int* arr, int from, int end);
};MaxHeap.cpp
//2018112424 장지담
#include "MaxHeap.h"
#include <iostream>
using namespace std;
//생성자
MaxHeap::MaxHeap(priorityCheck func) {
this->func = func;
this->numOfData = 0;
}
void MaxHeap::showHeap() {
for (int i = 1; i <= numOfData; i++) {
cout << arr[i] << " ";
}
cout << endl << endl;
}
//Heap이 비었으면 true 아니면 false 반환
bool MaxHeap::isEmpty() {
if (this->numOfData == 0) { return true; }
else { return false; }
}
//부모 노드의 인덱스 반환
int MaxHeap::getParent(int index) {
return index / 2;
}
int MaxHeap::getLeftChild(int index) {
return index * 2;
}
int MaxHeap::getRightChild(int index) {
return index * 2 + 1;
}
int MaxHeap::getHighPriorityChild(int index) {
int left = getLeftChild(index), right = getRightChild(index);
if (left > numOfData) { return false; }
else if (left == numOfData) { return left; }
else {
if (func(arr[left], arr[right])) {
return left;
}
else { return right; }
}
}
Data MaxHeap::heapDelete() {
//delete 방법 : 루트 노드의 데이터를 삭제 후 최하단 노드를 루트 노드의 자리에
//놓고 자식 노드 중 큰 노드와 비교하며 재정렬한다.
if (isEmpty()) { exit(1); }
else {
//반환할 루트 노드의 데이터 저장
Data toReturn = arr[1];
int spot = 1;
int spotChild;
//spot이 루트 노드 자리로 올라온 최하단 노드의 인덱스다
//spotChild는 spot의 child중 우선순위가 높은 자식노드의 인덱스다
//spot과 spotChild 인덱스의 데이터 값을 비교하며 자리를 찾는다.
while (spotChild = getHighPriorityChild(spot)) {
//func을 통해 우선순위 비교
//arr[numofData]=최하단 노드의 데이터, arr[spotChild] 현재 비교하는 자리 spot의 우선수위가 높은 자식노드의 데이터
//func는 앞의 인자가 더 우선순위가 높을경우 true, 아닐경우 false 반환
//최하단 노드의 데이터가 spotChild보다 크거나 같을 경우 spot 이동 멈춤
if (func(arr[numOfData], arr[spotChild])) {
break;
}
//spotChild의 우선순위가 더 높을경우
//spot은 spotChild로 이동하고 spotChild에 있던 값은 spot 자리에 넣음
arr[spot] = arr[spotChild];
spot = spotChild;
}
//while을 탈출하면 = spot의 위치가 결정되면
//spot의 자리에 최하단 노드의 데이터를 넣고 데이터 개수 1감소
arr[spot] = arr[numOfData--];
cout << toReturn << " 삭제\n";
//삭제한 값 반환
return toReturn;
}
}
//힙에 배열의 원소를 하나씩 넣으면서 넣는 동시에 재정비함
void MaxHeap::heapInsert(Data data) {
//heap의 최하단에 데이터를 놓고 부모 노드와 값을 비교하며 자리를 찾는다
int spot = ++numOfData;
int spotParent;
while ((spotParent = getParent(spot)) >= 1) {
if (func(arr[spotParent], data)) {
break;
}
arr[spot] = arr[spotParent];
spot = spotParent;
}
arr[spot] = data;
cout << "Arr : "<<spot<<"에 "<<data << " 삽입\n";
for (int i = 1; i <= numOfData; i++) {
cout << arr[i];
}
cout << endl << endl;
}
//배열을 힙에 넣는다
void MaxHeap::buildHeap(int* inputArr, int length) {
numOfData = length;
for (int i = 1; i <= length; i++) {
arr[i] = inputArr[i - 1];
}
//numOfData 번째 노드는 최하위 노드
//i= 최하위 노드의 부모 노드 ~ i=1까지 (루트노드까지) 반복하며 adjustHeap (힙 조정)
for (int i = numOfData / 2; i > 0; i--) {
adjustHeap(arr, i, numOfData);
}
}
//힙을 아래서부터 조정할 때 쓰는 메소드
void MaxHeap::adjustHeap(int* arr, int from, int end) {
//from부터 end까지 heap을 재조정함
//자식노드 중 우선순위가 큰 노드 얻기
int highPriorityChild = getHighPriorityChild(from);
if (highPriorityChild == false) { return; }
//부모노드와 비교해서 자리 조정
if (arr[highPriorityChild] > arr[from]) {
//swap
Data temp = arr[from];
arr[from] = arr[highPriorityChild];
arr[highPriorityChild] = temp;
//부모-자식노드 비교 후 자식노드 ~ 자식의자식노드 조정
adjustHeap(arr, highPriorityChild, end);
}
}
HeapSort.h
//2018112424 장지담
#pragma once
#include "MaxHeap.h"
#include <iostream>
using namespace std;
void showArr(Data* arr, int length) {
for (int i = 0; i < length; i++) {
cout << arr[i] << " ";
}
cout << endl << endl;
}
//우선순위 비교를 위한 함수
bool compare(int a, int b) {
if (a >= b) { return true; }
return false;
}
void heapSort(Data* arr, int length) {
//배열을 힙에 넣었다가 빼주면 된다
MaxHeap heap(compare);
for (int i = 0; i < length; i++) {
heap.heapInsert(arr[i]);
}
for (int i = 0; i < length; i++) {
arr[i] = heap.heapDelete();
}
}
void heapSort2(Data* arr, int length) {
MaxHeap heap(compare);
heap.buildHeap(arr, length);
cout << "힙에 배열을 넣고 재조정함" << endl;
heap.showHeap();
for (int i = 0; i < length; i++) {
arr[i] = heap.heapDelete();
}
}
힙을 이용해 배열을 정렬한다
최대 힙은 부모 노드의 값이 자식 노드보다 최소한 크거나 같은 힙이다.
-
힙에 배열을 넣을 때 원소를 하나씩 맨 뒤에 넣고 부모 노드랑 크기를 비교하면서 자리를 찾아서 그 자리에 삽입할 수 있다.
-
힙에 배열을 한번에 다 넣고 말단 노드의 부모노드부터 재귀적으로 재정비 할 수 있다.
이렇게 두가지 방법을 코드에 모두 구현해놓았다. (주석과 함께 참고)
힙에서 원소를 하나씩 삭제하며 배열에 넣으면 배열이 정렬된다.
힙에서 원소를 삭제할 때는 루트 노드를 삭제하고 말단 노드를 루트 노드의 자리로 옮긴 후 자식 노드중 큰 노드와 비교하며 자리를 찾는다.
