끵뀐꿩긘의 여러가지

◎퀵 정렬 pivot이라는 특정한 값을 기준으로 분할 정복(Devide and Conquer) 기법을 사용하여 작은 부분으로 분할하여 정렬하는 방식 ◎퀵 정렬의 특징 1. 비교 정렬(comparison sort) 퀵 정렬은 데이터를 비교하면서 찾는다. 2. 제자리 정렬(in-place sort) 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않는다. 3. 불안정 정렬(unstable sort) 정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지되지 않는다. ◎퀵 정렬의 동작 1. 피벗 선택(일반적으로 맨 왼쪽, 맨 오른쪽 또는 중간 index의 값 중 하나를 피벗으로 정한다) 2. 피벗을 기준으로 왼쪽에서부터는 피벗보다 큰 값을 찾고, 오른쪽에서부터는 피벗보다 작은 값..

◎계수 정렬 정수들로 이루어진 배열을 원소들의 비교를 하지않고, 최소값과 최대값 사이에 존재하는 원소의 개수를 세어서 정렬하는 방식 ◎계수 정렬의 특징 1. 비교 정렬(comparison sort)이 아니다 계수정렬은 데이터를 비교하면서 찾지 않는다 2. 제자리 정렬(in-place sort)이 아님 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 한다 3. 안정 정렬(stable sort) 정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지된다. ◎계수 정렬의 동작 ※계수 정렬은 원소들의 최댓값과 최솟값을 안다는 가정하에 실행된다 1. 배열 내에 원소 값들의 갯수를 저장하는 카운팅 배열을 만든다. - 카운팅 배열의 길이는 '원소들의 최댓값 - 원소들의 최소값 + 1'이다. ..

◎힙 정렬 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방식, 최대 힙을 구성하면 내림차순 정렬을, 최소 힙을 구성하면 오름차순 정렬을 할 수 있다. ◎힙 정렬의 특징 1. 비교 정렬(comparison sort) 힙 정렬은 데이터를 비교하면서 찾는다. 2. 제자리 정렬(in-place sort)이 아님 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 한다 3. 불안정 정렬(unstable sort) 정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지되지 않는다. ※자료구조 heap에 대하여! (heap 정렬의 이해를 위해서는 자료구조 heap을 무조건 알아야 한다.) & 자바에서 구현된 heap, priority queue에 대하여! https://kkwong-gui..

◎병합 정렬 배열 분할을 반복하여 최대한 작게 쪼개진 시점에 부분배열에서 인접한 원소들끼리 비교하여 정렬하는 방식 '분할 정복(Divide and Conquer)' 알고리즘을 기반으로 정렬한다. -분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘 이다. 보통 재귀함수를 통해 자연스럽게 구현된다. ◎병합 정렬의 특징 1. 비교 정렬(comparison sort) 병합 정렬은 데이터를 비교하면서 찾는다. 2. 제자리 정렬(in-place sort)이 아님 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 한다. 3. 안정 정렬(stable sort) 정렬되지 않은 상태에서 같은 키값을 가진 원..

◎선택 정렬 현재 위치에 들어갈 데이터를 찾아 선택하는 방식 일반적으로 전체에서 가장 작은 원소를 선택하거나, 가장 큰 원소를 선택하여 정렬한다. ◎선택 정렬의 특징 1. 비교 정렬(comparison sort) 선택 정렬은 데이터를 비교하면서 찾는다. 2. 제자리 정렬(in-place sort) 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않는다. 3. 불안정 정렬(unstable sort) 정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에는 유지되지 않는다. ◎선택 정렬의 동작 1. 배열에서 최솟값을 찾는다. (원소 3이 최솟값이다) 2. 1회전에서 찾은 최솟값이므로 idx 0의 원소와 최솟값을 교환한다 3. idx 0의 원소를 제외한 배열에서 최솟값을 찾는다.(원소 ..

◎삽입 정렬 현재 비교하고자 하는 target(타깃)을 그 이전의 원소들과 비교하며 자리를 교환(swap)하며 맞는 자리에 삽입하는 방식 ◎삽입 정렬의 특징 1. 비교 정렬(comparison sort) 삽입 정렬은 데이터를 바교하면서 찾는다. 2. 제자리 정렬(in-place sort) 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않는다. 3. 안정 정렬(stable sort) 정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지된다. ◎삽입 정렬의 동작 idx 0의 원소는 앞의 원소가 존재하지 않기 때문에, idx 1부터 비교를 시작한다. 1. idx 1의 원소 5가 target원소이다. 5가 idx 0의 원소 8보다 작으므로 8을 밀고 5를 그 자리에 넣는다. 2..

◎버블 정렬 두 개의 인접한 원소를 비교하여 정렬하는 방식. 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환한다. 정렬 과정에서 원소의 이동이 마치 거품이 수면 위로 올라오는 것 같다고 해서 bubble 정렬이다. ◎버블 정렬의 특징 1. 비교 정렬(comparison sort) 버블 정렬은 데이터를 바교하면서 찾는다. 2. 제자리 정렬(in-place sort) 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않는다. 3. 안정 정렬(stable sort) 정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지된다. ◎버블 정렬의 동작 1. 앞에서부터 현재 원소와 다음의 원소를 비교한다. 2. 현재 원소가 다음 원소보다 크면 서로 교환한다. 3...

◎선형 탐사 / 제곱 탐사 선형 탐사: 데이터를 저장할 위치에 충돌이 발생하면, 비어있는 곳을 발견할 때까지 계속 +1 하여 찾는 것 (OpenHasing의 일종) 제곱 탐사: 데이터를 저장할 위치에 충돌이 발생하면, 비어있는 곳을 발견할 때까지 계속 이동수의 제곱수만큼 하여 찾는 것 (OpenHasing의 일종) 코드: public class Main { public static void main(String[] args) { Contact person1 = new Contact("abc","010"); // 이름: abc, 연락처: 010 Contact person2 = new Contact("akj","011"); // 이름: akj, 연락처: 011 LinearHashTable hashtable ..