끵뀐꿩긘의 여러가지

지금까지 여러 기본 정렬 알고리즘을 알아보고 구현하였다. 여기서는 매우 복잡하지만 실제로 쓰이는 Tim sort, Dual pivot sort 등등과 실용성은 없지만 재미있는 여러 정렬 알고리즘을 소개하겠다. ◎Tim sort https://d2.naver.com/helloworld/0315536 ◎Dual Pivot quick sort https://defacto-standard.tistory.com/38 Dual-Pivot Quick Sort ( Arrays.sort() 내부 정렬 알고리즘 ) Arrays.sort()는 내부적으로 3개의 Sorting을 쓴다. 1. Insertion Sort 2. Merge Sort 3. QuickSort 예전에는 3개를 분리하여서 각각의 경우에 따로 사용을 했지만 ..

◎기수 정렬 가장 작은 자릿수부터 가장 큰 자릿수까지 자릿수(기수) 별로 자리를 찾아주는 방식으로 숫자를 정렬하는 방식 ◎기수 정렬의 특징 1. 비교 정렬(comparison sort)이 아니다 기수 정렬은 데이터를 비교하면서 찾지 않는다. 2. 제자리 정렬(in-place sort)이 아니다 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 한다. 3. 안정 정렬(unstable sort) 정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지된다. ◎기수 정렬의 동작 기수 정렬은 모든 데이터의 길이가 같아야 사용할 수 있다. ex. [aaa,bbb,dsd,gdf,ret] => 모든 데이터의 길이가 3이므로 기수정렬 사용가능 1. 0~9번까지의 Queue를 생성한다 2. 모든 데..

◎셸 정렬 삽입 정렬이 어느 정도 정렬되어 있는 배열에 대해서는 대단히 빠르다는 점을 이용하여, 삽입 정렬을 보완한 알고리즘 ◎삽입 정렬의 문제점 삽입 정렬은 타깃 원소가 앞의 숫자보다 작으면 앞의 원소들을 모두 교환해야 한다는 단점을 가지고 있다. ex. [1,2,3,4,0]인 배열이 있다고하면, 맨 마지막 원소인 0 때문에, [0,2,3,4,1] [0,1,3,4,2] [0,1,2,4,3] [0,1,2,3,4] 의 과정을 거치며 모든 원소들을 교환하는 비효율적인 상황이 발생한다 ◎셸 정렬의 특징 1. 비교 정렬(comparison sort) 셸 정렬은 데이터를 비교하면서 찾는다. 2. 제자리 정렬(in-place sort) 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않는다. 3. 불안..

◎퀵 정렬 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의 원소를 제외한 배열에서 최솟값을 찾는다.(원소 ..