개발자로 살아남기

기수 정렬 (Radix Sort) 기수 정렬 (Radix Sort) 비교 연산이 없는 정렬 알고리즘 적용할 수 있는 범위가 제한적임 - 정수, 알파벳, 특수문자 등의 아스키로 표현할 수 있는 것들 - 소수는 불가능 기수 (Radix)를 이용한 정렬 - 2진수의 경우 : 0, 1 / 10진수의 경우 : 0 ~ 9 / 알파벳 소문자의 경우 : a ~ z (0 ~ 25) 기수만큼의 추가 저장 공간이 필요함 - 저장 공간을 버킷 (Bucket) 이라고 부름 Queue를 이용한 정렬 알고리즘 LSD (Least Significant Digit) 정렬 방법과 MSD (Most Significant Digit) 정렬 방법이 있음 - LSD : 덜 중요한 첫번째 자리수부터 정렬 (즉, 가장 작은 자리수) ex) 123..

퀵정렬 (Quick Sort) 퀵정렬 (Quick Sort) 분할정복 (divide and conquer) 알고리즘 중 하나 피벗(pivot)이라는 것을 이용해 정렬 피벗 : 데이터 리스트에서 하나를 고르는 것 불안정 정렬 (unstable sort) - 같은 데이터끼리의 순서가 보장되지 않음 ex) 5(A), 5(B), 3, 2, 1 => 1, 2, 3, 5(B), 5(A) nlog2(n) 알고리즘들 중 평균적으로 가장 빠름 제자리 정렬 (in-place sort) - 데이터 크기만큼의 저장공간을 제외하고 추가적인 공간이 필요하지 않음 퀵정렬 방법 데이터들 중 하나를 골라 피벗으로 설정 데이터 리스트의 앞과 뒤에서 탐색하며 피벗보다 작은 값들은 앞에 오고 피벗보다 큰 값들은 뒤로 가도록 분할 분할된 리..

힙 정렬 (Heap Sort) 힙 정렬 (Heap Sort) 최대힙 트리나 최소힙 트리를 구성해 정렬하는 방법 내림차순 정렬은 최대힙으로 구성 오름차순 정렬은 최소힙으로 구성 힙 관련 내용 참고 (https://banjjak1.tistory.com/45) 힙 정렬 방법 내림차순일 경우 데이터를 최대힙으로 구성하고 오름차순일 경우 최소힙으로 구성 최대힙의 경우 루트노드는 해당 트리에서 항상 최대값을 가지고 있으므로 힙 구성 후 삭제를 반복하면 다음 최대값이 루트노드가 되어 결국 내림차순 정렬이 됨 성능 시간복잡도 최악의 경우 : n log2(n) 최선의 경우 : n log2(n) : 데이터 저장 및 삭제의 시간복잡도 log2(n) : 정렬할 데이터가 n개인 경우 n개의 데이터를 저장 및 삭제해야 하므로 n..

합병(병합) 정렬 (Merge Sort) 합병(병합) 정렬 (Merge Sort) 안정 정렬 (stable sort) - 정렬 후에도 같은 값들끼리의 순서가 보장됨을 의미함 ex) 5, 4, 3(A), 2, 3(B), 1 1, 2, 3(A), 3(B), 4, 5 분할정복 (divide and conquer) 알고리즘 중 하나 정렬 시 데이터 크기만큼의 추가 공간이 필요하므로 제자리 정렬 (in-place sort)가 될 수 없음 합병 정렬 방법 분할 (divide) : 데이터 리스트에서 데이터가 하나씩 정렬될 때까지 리스트를 절반씩 나눈다. 정복 (conquer) : 나눈 데이터들끼리 재귀적으로 정렬을 진행한다. 결합 (combine) : 정렬된 데이터들을 하나로 합친다. 성능 시간복잡도 최악의 경우 :..

삽입 정렬 (Insertion Sort) 삽입 정렬 (Insertion Sort) 구현이 간단함 안정 정렬 (stable sort) - 정렬 후에도 같은 값들 끼리의 순서가 보장됨을 의미함 ex) 5, 3(A), 2, 4, 3(B), 1 => 1, 2, 3(A), 3(B), 4, 5 제자리 정렬 (in-place sort) - 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미 선택 정렬, 버블 정렬보다 비교적 빠르지만 마찬가지로 배열이 클수록 효율이 떨어짐 선택 정렬과 비슷하지만 선택 정렬은 배열의 모든 값을 탐색해 최소값을 구한 후 정렬하는 방식이지만 삽입 정렬은 데이터의 앞쪽을 탐색하며 자신의 위치를 찾아 정렬함 삽입 정렬 방법 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 ..

선택 정렬 (Selection Sort) 선택 정렬 (Selection Sort) 제자리 정렬 (in-place sort) - 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미 비안정 정렬 (unstable sort) - 정렬 후에 같은 값들의 순서가 변함 - 아래는 같은 값을 A, B로 구분하였음 ex) 3(A), 6, 2, 5, 4, 3(B), 1 1, 2, 3(B), 3(A), 4, 5, 6 정렬할 데이터의 개수가 적을때는 나쁘지 않은 속도를 보임 선택 정렬 방법 위 그림은 아래 방법을 그림으로 표현한 것 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 성능 시간복잡도 최악의 경우 : O(n^2..

버블 정렬 (Bubble Sort) 버블 정렬 (Bubble Sort) 가장 단순한 정렬 알고리즘 인접한 요소와 정렬 기준(오름차순, 내림차순)대로 교환 안정 정렬 (stable sort) : 정렬 후에도 같은 값들 끼리의 순서가 보장됨을 의미 제자리 정렬 (in-place sort) : 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미 정렬한 데이터의 개수가 적을때는 나쁘지 않은 속도를 보임 버블 정렬 방법 (오름차순 기준) 첫 번째 사이클이 끝나면 맨 마지막 값이 정렬되고, 두 번째 사이클이 끝나면 뒤에서 두 번째의 값이 정렬된다. 이같은 과정을 계속 반복하면 최종적으로 정렬이 된다. 버블 정렬의 성능 시간복잡도 최악의 경우 : O(n^2) 최선의 경우 : O(n) 최악의 경우 : 모든..