공부한 이야기/알고리즘

정렬 - 퀵정렬

퀵 정렬 퀵 정렬은 정렬 중에서 빠른 속도로 인해 유명한 대표적인 정렬 방법론 중 하나이다. 이는 분할 정복 방법을 통해서 배열을 정렬하게 된다. 배열의 값들 중 하나의 원소를 고르고, 이를 피벗이라고 명한다. 이 앞에는 피벗보다 작은 값이 오도록, 이 뒤에는 큰 값이 오도록 배열을 정렬하고 둘로 나눈 뒤, 다시 이 작은 배열에 대해 재귀적으로 퀵 정렬을 반복한다. generateRandomArray, printArray, swap int partition(int *myArray, int left, int right) { int pivot = myArray[left]; int i = left, j = right; while (i < j) { while (pivot < myArray[j]) { j--; }..

정렬 - 힙정렬

힙 정렬 힙 정렬은 이진 트리를 이용해서 정렬해 나가는 방식이다. 힙 생성 시 최대 힙으로 생성하고, 왼쪽 자식의 인덱스는 부모 인덱스의 / 2, 오른쪽 자식의 인덱스는 부모 인덱스의 / 2 + 1 이라는 점을 이용한다. 단, 배열은 인덱스가 0부터 시작하지만 힙 정렬에서 예시로 사용하기 위해서, 배열의 0번을 비우고 1번부터 사용하기로 한다. 이를 위해 출력과 랜덤 값 채우기 메서드를 힙 정렬에 맞추어 아래와 같이 조금 변경했다. template void swap(T *a, T *b) { T temp = *a; *a = *b; *b = temp; return; } template void printArrayForHeap(T &array, int size) { for (int i = 1; i = 2; i..

정렬 - 기수정렬

기수 정렬 기수 정렬은 값의 자릿수를 이용해서 정렬하는 특이한 정렬인데, 이는 비교를 하지 않고 정렬한다는 또 다른 특징을 가지고 있다. 우선 n진수인지에 따라서 n개의 저장 공간 (일반적으로 스택 등) 을 마련한다. 배열과는 다르게, 이 저장 공간에는 여러 데이터가 들어갔다가 순차적으로 나올 수 있어야 한다. 그리고 나서, n진수의 끝의 자리 숫자 (10진수라면 1의 자리 숫자) 를 기준으로, 해당 값에 맞는 버킷을 값을 push 한다. 예를 들어, 142 라는 값은 2 번째 버킷에 들어가는 형식이다. 이후, 이 모든 버킷들을 첫번재 버킷부터 순차적으로 pop 하면서 배열에 다시 담는다. 그 후, 배열의 값 중 최대 자리 수만큼 이 행위를 반복하면서, 정렬을 만들어내는 과정이다. generateRand..

정렬 - 삽입정렬

삽입 정렬 삽입 정렬은 기준점을 점점 뒤로 이동시키면서 해당 기준점 이전의 앞 데이터가 정렬되도록 유지하는 정렬 방식이다. generateRandomArray, printArray, swap static int arrayLength = 20; int *myArray = generateRandomArray(arrayLength); // 랜덤으로 값이 초기화된 배열 생성 printArray(myArray, arrayLength); // 정렬 전 배열 출력 for (int i = 0; i < arrayLength; i++) { // 배열의 첫 번재 요소부터 뒤쪽으로 탐색하는데, int tempValue = myArray[i]; // 임시 값의 초기화는 현재 위치의 배열 값 int searchIndex = i ..

정렬 - 선택정렬

선택 정렬 선택 정렬은 첫 for문을 통해 기준 요소를 하나 지정한 뒤, 내부 for문으로 min 혹은 max 의 위치를 찾고, 기준 요소와 찾은 요소를 필요 시 swap 하는 형태이다. 버블 정렬과는 달리 swap 의 실행이 최대 n-1 번만 일어난다는 특징이 있다. generateRandomArray, printArray, swap static int arrayLength = 20; int *myArray = generateRandomArray(arrayLength); // 랜덤으로 값이 초기화된 배열 생성 printArray(myArray, arrayLength); // 정렬 전 배열 출력 for (int i = 0; i < arrayLength; i++) { // 배열의 첫 번재 요소부터 뒤쪽으로..

정렬 - 버블정렬

버블 정렬 버블 정렬은 이웃하는 값들의 크기를 비교하여 자신이 원하는 정렬 방식 (오름차순/내림차순) 에 부합하도록 해당 요소들의 자리를 변경하고, 이 비교 작업이 배열을 한 번, 한 뱡항으로 훑게 되면 결국 마지막 요소는 가장 큰/작은 값임을 보장받게 된다. 따라서, 이후 이 마지막 요소를 제외하고 다시 처음부터 비교 작업을 진행해가는 방식이다. 이웃한 요소를 비교하고 필요시 곧바로 swap 한다는 특징이 있다. generateRandomArray, printArray, swap static int arrayLength = 20; int *myArray = generateRandomArray(arrayLength); // 랜덤으로 값이 초기화된 배열 생성 printArray(myArray, arrayL..

정렬 - 기본기

기본 다지기 - 정렬 정렬이야말로 기본기 중 가장 밑단이면서도, 모든 알고리즘의 대표격이라고 생각한다. 여러 정렬의 종류를 알아보고, 새로운 정렬 방식이 있는지, 그것의 복잡도는 어떻게 계산되는지 생각해 보자. 정렬이란 비교 가능한 요소를 가지고 있는 데이터셋의 연속 (배열이나 리스트 등) 에서, 특정한 조건을 기준으로 요소들의 순서를 재배치 하는 방법론이다. 일반적으로 특정 값을 오름차순, 내림차순으로 순서를 매기는 것이 대표적이다. 하지만 특정 값에 가장 가까운 순서라던지, 특정 계산식을 거쳤을 때 원하는 값에 가깝게 나오는 순서라던지 등등 확장은 마음껏 가능할것 같다. 물론 이들도 결국 계산식을 거친 후 그 값에 의한 오름 내림차순이기는 하겠지만. 들어가기 앞서 swap 두 요소 간 배열 등 연속된..