CS/알고리즘 (8) 썸네일형 리스트형 계수 정렬(Counting Sort) 개념계수 정렬 또는 카운팅 소트(counting sort)는 컴퓨터 과학에서 정렬 알고리즘의 하나로서, 작은 양의 정수들인 키에 따라 객체를 수집하는 것, 즉 정수 정렬 알고리즘의 하나이다.(계수 정렬은 비교 정렬이 아님) 예시 시간복잡도시간 복잡도 : O(n + k) -> k는 배열에서 등장하는 최대값 참고 https://gyoogle.dev/blog/algorithm/Counting%20Sort.htmlhttps://ko.wikipedia.org/wiki/%EA%B3%84%EC%88%98_%EC%A0%95%EB%A0%AC 힙 정렬(Heap Sort) 개념힙 정렬(Heap sort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최소 힙을 구성하고 오름차순 정렬을 위해서는 최대 힙을 구성하면 된다. 어떤 리스트에 값을 넣었다가 빼내려고 할 때, 우선순위가 높은 것 부터 빼내려고 한다면 정렬을 떠올리게 된다. 하지만 정렬은 숫자가 낮을 수록 우선순위가 높다고 가정할 때 매 번 새 원소가 들어올 때 마다 이미 리스트에 존재하는 원소들과 비교를 해서 정렬을 해야한다. 이렇게 하면 비효율적이기 때문에 좀 더 효율이 좋게 만들기 위하여 힙은 다음과 같은 조건이 있다. '부모 노드는 항상 자식 노드보다 우선순위가 높다.' 즉, 모든 요소들을 고려하여 우선순위를 정할 필요 없이 부모 노드는 자식노드보다 항상 우선순위가.. 기수 정렬(Radix sort) 개념기수 정렬(radix sort)은 기수 별로 비교 없이 수행하는 정렬 알고리즘이다.(비교정렬이 아니다!) 기수로는 다양한 자료를 사용할 수 있으나 크기가 유한하고 사전순으로 정렬할 수 있어야 한다. 예시 구현(Java) void countSort(int arr[], int n, int exp) { int buffer[n]; int i, count[10] = {0}; // exp의 자릿수에 해당하는 count 증가 for (i = 0; i = 0; i--) { buffer[count[(arr[i]/exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } for (i = 0; i 0; e.. 병합 정렬(Merge Sort) 개념합병 정렬 또는 병합 정렬은 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다.( * 분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다.) 구현(Java)요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식mergeSortpublic void mergeSort(int[] array, int left, int right) { if(left merge()public static void merge(int[] array, int left, int mid, int right) { int[] L = A.. 퀵 정렬(Quick Sort) 개념퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 주어진 배열을 정렬한다.퀵 정렬은 불안정 정렬이며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬이다.( * 분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다.) 과정리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.분할된 두 개의 작은 리스트에 .. 거품 정렬(Bubble Sort) 개념거품 정렬은 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다. 과정1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … , (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. 구현(Java)void bubbleSort(int[] arr) { int temp = 0; for(int i = 0; i .. 삽입 정렬(Insertion Sort) 개념삽입 정렬은 2번째 원소부터 시작하여 모든 요소를 차례대로 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 과정2번째 위치(index)의 값을 temp에 저장한다.temp와 이전에 있는 원소들과 비교하며 삽입해나간다.'1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다. 구현(Java)void insertionSort(int[] arr){ for(int index = 1; index = 0) && (arr[prev] > temp) ) { // 이전 위치가 음수가 아니며, 비교값이 선택값보다 크다면 arr[prev+1] = arr[prev]; // 값이 하나씩 뒤로 밀림 .. 선택 정렬(Selection Sort) 개념선택 정렬은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다. 과정주어진 리스트 중 최소값을 찾는다.그 값을 맨 앞에 위치한 값과 교체한다. (pass)맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 예시 구현(Java)void selectionSort(int[] arr) { int indexMin, temp; for (int i = 0; i 시간복잡도데이터의 개수가 n개일 때,첫 회전에서의 비교횟수 : 1 ~ n-1 => n-1두번째 회전에서의 비교횟수 : 2 ~ n-1 => n-2...(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 즉, n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸.. 이전 1 다음
