All about Data Structure & Algorithm (26) 썸네일형 리스트형 기수 정렬(Radix Sort) 계수 정렬(Counting Sort) 힙 정렬(Heap Sort) 향상된 퀵 정렬 셸 정렬(Shell Sort) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 셸 정렬(shell sort)는 삽입 정렬의 일반화된 형태이며, 먼 거리에 있는 요소들 간의 교환을 가능하게 해서 성능을 높였다. ㉠ 셸 정렬은 셸의 방법(shell 's method)으로도 불린다. ② 셸 정렬의 최악의 시간 복잡도는 삽입 정렬과 마찬가지로 O(log(n))이다. ㉠ 그렇지만, 퀵 정렬 다음으로 셸 정렬이 두 번째로 빠르다. ③ 셸 정렬의 기본 원리는 다음과 같다. ㉠ 정수로 된 갭 시퀀스를 정한다. (h1>h2>h3>h4>...hk = 1) ⓐ 갭은 하위 배열 간의 간격을 의미하며, 최종적으론 하위 정렬 간의 간격이 1이 되어야 함을 의미한다. ⓑ 갭이 1씩 줄어드는 갭 시퀀스를 가진 셸 정렬이 삽입 정렬이다. 삽입 정렬(In.. 퀵 정렬(Quick Sort) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 퀵 정렬(quick sort)은 분할 정복 (devide and conquer)을 이용한 대중적인 정렬 알고리즘 중 하나이다. ② 퀵 정렬의 최악의 경우의 시간 복잡도는 O(n^2)이지만 평균적인 경우의 시간 복잡도는 O(n log(n))인 특이한 정렬 방법이다. ③ 퀵 정렬의 기본 원리는 다음과 같다. ㉠ 배열에서 피벗 요소를 고른다. 피벗 요소는 임의로 선택될 수 있다. ㉡ 배열을 두 개의 하위 배열 A, B로 나눈다. 하위 배열 A는 피벗 요소보다 작은 값을, 하위 배열 B는 피벗 요소보다 크거나 같은 값을 분류한다. ㉢ 하위 배열 A와 B에 ㉠, ㉡을 재귀적으로 적용한다. ④ 퀵 정렬의 의사 코드(psuedo code)는 다음과 같다. H.. 병합 정렬(Merge Sort) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 병합 정렬(merge sort)은 분할 정복(devide and conquer)을 이용한 대중적인 정렬 알고리즘 중 하나이다. ㉠ 병합 정렬은 합병 정렬로도 불린다. ② 병합 정렬의 최악의 경우의 시간 복잡도는 O(nlog(n))으로 데이터의 크기가 큰 경우에 적절한 정렬 방법이다. ③ 병합 정렬의 기본 원리는 다음과 같다. ㉠ 정렬되지 않은 배열을 절반으로 나누는 행위를 배열의 사이즈가 1이 될 때까지 반복한다. ㉡ 사이즈가 같은 배열을 정렬하면서 배열을 하나로 합친다. ㉢ 합친 배열의 크기가 원래 배열이 될 때까지 ㉡를 반복한다. ④ 병합 정렬의 의사 코드(psuedo code)는 다음과 같다. HTML 삽입 미리보기할 수 없는 소스 ⑤ 병합.. 선택 정렬(Selection Sort) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 선택 정렬(selection sort)는 비교적 간단한 정렬 알고리즘이다. ㉠ 추가적인 메모리 공간이 필요하지 않지만, 알고리즘의 수행 시간이 O(n^2)이다. ② 삽입 정렬은 제자리 알고리즘(in-place algorithm) 중 하나이다. ㉠ 제자리 알고리즘은 자료 구조를 추가로 사용하지 않아 추가적인 메모리 공간이 필요하지 않다는 것을 의미한다. ③ 선택 정렬의 기본 원리는 다음과 같다. ㉠ 정렬된 부분 배열과 정렬되지 않은 부분 배열로 나눈다. ㉡ 정렬되지 않은 부분 배열에서 가장 작은(혹은 가장 큰) 요소를 찾는다. ㉢ 정렬되지 않은 부분의 첫 번째 인덱스(혹은 제일 뒤 인덱스)와 스왑한다. ㉣ ㉡과 ㉢를 반복해서 시행해서 전체 배열이 .. 이전 1 2 3 4 다음
