전체 글 (163) 썸네일형 리스트형 바이토닉 정렬(Bitonic Sort) ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. ① 바이토닉 정렬(bitonic sort)는 병렬 배열들을 정렬하기에 효과적인 정렬 방법이다. ② 바이토닉 정렬의 최악의 시간 복잡도는 O(n log^2 (n))이다. ㉠ 시간 복잡도를 볼 경우 그다지 뛰어난 성능을 가진 것 같아 보이지 않는다. ⓐ 그러나 바이토닉 정렬은 병렬 배열을 정렬할 때와 같은 특정 상황에서 쉽게 병렬화할 수 있고, 캐시 효율이 좋다는 장점이 있다. ③④⑤⑥⑦⑧⑨⑩⑪⑫⑬⑭⑮ ㉠㉡㉢㉣㉤㉥㉦㉧㉨㉩㉪㉫㉬㉭ ⓐⓑⓒⓓⓔⓕⓖⓗⓘⓙⓚⓛⓜ 기수 정렬(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 삽입 미리보기할 수 없는 소스 ⑤ 병합.. 이전 1 2 3 4 5 6 7 ··· 21 다음
