티스토리

chaetudy
검색하기

블로그 홈

chaetudy

chae-d-2.tistory.com/m

chaeD2 님의 블로그입니다.

구독자
0
방명록 방문하기

주요 글 목록

  • Quick Sort 개요 분할 정복 방법을 통해 리스트를 정렬한다. 피봇을 정한 뒤 피봇의 위치를 확정해 가며 정렬한다. 시간 복잡도 최악의 경우 O(n^2), 평균적으로 O(nlogn)이다. 대부분 컴퓨터 아키텍쳐 설계 상 퀵 소트 내부 루프의 캐시 히트율이 높기 때문에, 일반적인 경우에 시간 복잡도 O(nlogn)인 알고리즘보다 빠르다. 코드 void quick_sort(int* arr, int low, int high) { // base condition if (low >= high) return; // divide int i = low, j = low; int& pivot = arr[high]; for (; j < high; j++) { if (arr[j] < pivot) { swap(arr[i++], arr[j]).. 공감수 0 댓글수 0 2022. 5. 20.
  • Bubble Sort 개요 두 인접한 원소를 정렬해 나간다. 구현은 쉬우나 효율은 좋지 않은 편에 속한다. 대충 이런 정렬이 있구나 하고 알고 넘어가면 된다. 55 07 78 12 42 초기값[파란색은 sorting] 07 55 78 12 42 첫 번째 패스(pass) 07 55 78 12 42 07 55 12 78 42 07 55 12 42 78 두 번째 패스(pass) 07 55 12 42 78 07 12 55 42 78 07 12 42 55 78 세 번째 패스(pass) 07 12 42 55 78 네 번째 패스(pass) 07 12 42 55 78 다섯 번째 패스(pass) 07 12 42 55 78 정렬 끝 시간 복잡도 n-1, n-2, ... 1번을 반복하게 되며 이를 식으로 나타내면 n(n-1)/2이므로, O(n^.. 공감수 0 댓글수 0 2022. 5. 20.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.