우주수첩의 우주먼지

이전에 sorting 알고리즘 몇 가지를 직접 C++로 구현 해 보았는데 사실 다 부질없고 라이브러리 함수가 모두 존재한다. 하지만 기억 저 편 하드디스크에서 아직 디스패치 되지 않는 나의 데이터들을 적재하기위해 잠시 IO인터프리터가 되어 주었던 것으로 하겠다. 망할 운영체제. 여튼 헤더에 을 include 하면 우리가 원하는 정렬을 사용할 수 있다. #sort(a,b) sort 함수를 사용하기 위해서는 정렬할 각 원소들이 비교가능해야한다. 숫자는 크기순, 문자는 사전순, pair 나 tuple의 경우 처음 요소가 작은 순서대로 비교 연산자가 정의되어있다. 몇가지 예시를 들어주도록 하겠다. # vector 정렬 #include // 헤더파일 언급 한 번 해 드리께 vector v = {4,2,5,3,5,..

사이즈가 n인 array A가 있다. 해당 array의 inversion의 개수를 출력하는 프로그램을 작성하여라. #그냥 구현하기 #include #include using namespace std; int main(void) { int arr[10] = { 4,5,6,2,3,10,8,1,9,7 }; int inversion_count = 0; for (int i = 0; i arr[j]) inversion_count++; } } cout arr[j + 1]) { temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; inversion_count++; } } }..

Insertion Sort 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 매 순서마다 해당 원소를 삽입할 수 있는 적절한 위치를 찾아 해당 위치에 삽입한다. 삽입정렬은 두 번째 자료부터 시작하여 해당 위치 기준 왼쪽의 자료들과 비교하여 삽입할 위치를 지정한다. 이는 기준점의 왼쪽의 자료들은 모두 sorted상태임을 알 수 있다. 처음 key 값은 두번째 자료부터 시작한다. #include #include using namespace std; int main(void) { int arr[10] = { 4,5,6,2,3,10,8,1,9,7 }; int j; for (int i = 1; i < 10; i++) { int ..

Selection Sort 제자리 정렬 알고리즘 중 하나. 정렬되지 않은 입력 배열 외에 다른 추가 메모리를 요구하지 않는다. 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘. 첫번째 자료를 두번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓는 행위를 반복하며 정렬을 수행한다. 1회전을 하고 나면 가장 작은 값의 자료가 맨 앞에 위치. 다음 회전에는 두번째 위치의 배열부터 처리한다. 정렬 과정 주어진 배열에서 최소값을 찾는다. 현재 범위 내에서 맨 앞의 값과 교환한다. 교환한 위치를 제외한 나머지 배열을 같은 방법으로 교체한다. 하나의 원소만 남을 때 까지 반복한다. #include #include using namespace s..

BUBBLE SORT 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 => 인접한 두 개의 원소를 비교하여 순서대로 되어있지 않을 경우 서로 교환한다. => array[3] 제외되는 데이터가 하나씩 늘어난다. #include #include using namespace std; int main(void) { int arr[10] = { 4,5,6,2,3,10,8,1,9,7 }; int temp; for (int i = 0; i arr[j + 1]) { temp = arr[j + 1]; arr[j ..