연숲하는 블로그

Quick Sort 분할 정복 알고리즘이라고도 하며, 특정값을 기준으로 한 배열을 두개의 부분 배열로 나누어 정렬하는 알고리즘이다. pivot을 정하고, 나머지 배열의 양쪽끝에서부터 검사를 한다. 배열의 왼쪽에는 pivot보다 작은 값, 배열의 오른쪽에는 pivot보다 큰 값이 놓이도록, 잘못된 위치에 있는 원소들을 교환한다. 한 검사가 끝나면 적어도 pivot은 제 위치를 찾은 것이고, 나눠진 배열들에 또 퀵 정렬을 적용하고 반복하면 정렬이 완료되게 된다. 이 알고리즘은 while문과 재귀함수로 구현할 수 있다. 배열들을 검사하며 교환하는 while문과 나눠진 두 배열에 퀵 정렬을 적용하는 재귀함수로 이루어진다. 퀵 정렬은 최선의 경우와 최악의 경우에 따라 시간 복잡도가 달라지는데 정렬된 배열을 검사할..

Insertion Sort 원소를 하나씩 삽입하는 것처럼 정렬하는 알고리즘이다. 삽입시 정렬된 이전 원소들과 비교하여, 자신이 더 작다면 자리를 교환하고, 이것을 반복한다. 이 알고리즘은 중첩 for문으로 구현할 수 있는데, 삽입 원소를 선정하는 for문과 삽입 원소와 이전 원소들을 비교하는 for문으로 이루어진다. 삽입 정렬은 최선의 경우와 최악의 경우에 따라 시간 복잡도가 달라지는데 정렬된 배열을 검사할 땐 원소를 비교하는 for문을 거치지 않아 O(n)이 되고 역순 배열을 검사할 땐 O(n^2)이 된다. 코드 #include using namespace std; void insertion_sort(int arr[],int n) { for(int i=1;i=0;j--) { if(new_>=arr[j]..

Selection Sort 최솟값을 이용한 방식으로, 배열의 최솟값인 원소를 찾고 배열의 앞과 값을 교환해서 정렬하는 알고리즘이다. 한 번 검사를 완료하면 최솟값이 앞에 놓이게 되고 다음 검사에선 그 부분을 제외하며 검사를 한다. 이 알고리즘도 중첩 for문으로 구현되는데, 검사 범위를 줄이는 for문과 최소값을 찾는 for문으로 이루어진다. 버블 정렬보단 교환의 수가 줄었지만 중첩 for문이기 때문에 시간 복잡도는 O(n^2)이 된다. 코드 #include using namespace std; void select_sort(int arr[],int n) { for(int i=0;i

Bubble Sort 가장 기본적이고 단순한 방식으로, 배열에서 인접 원소 2개를 비교하고, 교환해서 정렬하는 알고리즘이다. 앞부터 끝까지 검사를 완료하면 가장 큰 값이 끝에 놓이게 되고, 다음 검사에선 그 값을 제외하고 검사를 하기때문에 검사를 할 수록 검사 범위가 줄어들게 된다. 이 알고리즘은 중첩 for문으로 구현할 수 있는데, 검사 범위를 줄이는 for문과 시작부터 끝까지 검사하는 for문으로 이루어진다. 따라서 시간 복잡도는 O(n^2)이 된다. 코드 #include using namespace std; void bubble_sort(int arr[],int n) { for(int i=n-1;i>0;i--){ //검사 범위 축소: 0~n-1, 0~n-2, ... for(int j=0;jarr[j..