디노문경

퀵 정렬(quick sort)에서는 기준이 되는 수(pivot)를 수열 안에서 임의로 하나를 선택합니다. 그리고 피봇 이외의 수를 '피봇보다 작은 수'와 '피봇 이상인 수'의 두 그룹으로 나누고 이것을 다음과 같이 배치합니다. '피봇보다 작은 수' < 피봇 < '피봇 이상인 수' 그리고 양쪽 그룹을 또 다시 퀵 정렬을 사용해 나누고 이것을 계속 반복하면 자연스럽게 정렬이 이루어집니다. - 책 알고리즘 도감 위의 막대기들을 퀵 정렬을 사용해 오름차순으로 정렬해 보겠습니다. 1. pivot을 임의로 하나 선택합니다. 여기서는 40이 선택되었다고 가정하겠습니다. 2. pivot 이외의 각 숫자를 pivot과 비교해 갑니다. pivot보다 작은 숫자는 왼쪽, 큰 숫자는 오른쪽으로 이동합니다. 20 < 40 이므..

병합 정렬(merge sort)은 정렬하고 싶은 수열을 두 개의 수열(거의 같은 길이)로 분할해 갑니다. 더 이상 분할되지 않는 상태에 이르면(즉, 각 그룹이 한 개의 숫자가 된 경우) 그룹들을 병합(merge) 해 나갑니다. 병합할 때에는 정렬이 끝난 두 개의 수열을 병합해서 정렬이 끝난 하나의 수열로 만듭니다. 이것을 전체가 하나의 그룹이 될 때까지 반복합니다. - 책 알고리즘 도감 1. 수열을 반씩 분할해 나갑니다. 2. 병합하면서 정렬하는 작업을 반복합니다. [4, 6]과 [3, 7]을 병합할 때처럼 2개 이상의 숫자를 포함하고 있는 그룹들을 서로 병합할 때는 선두의 숫자를 비교해서 작은 숫자를 이동시킵니다, 1. 4와 3을 비교하고 4 > 3 이므로 3을 이동시킵니다. 2. 그 다음 선두인 4과..

힙 정렬(heap sort)은 힙이라는 데이터 구조를 사용하는 것이 특징입니다. -책 알고리즘 도감 1. 힙에 숫자를 저장 처음에는 힙에 모든 숫자를 저장합니다. 그리고 힙을 내림차순 혹은 오름차순으로 구축합니다. 여기서는 내림차순으로 구축해보겠습니다.(내림차순 힙은 큰 것부터 순서대로 데이터를 추출하는 성질이 있으므로 꺼낸 숫자를 역순으로 나열하면 정렬이 완료됩니다. 반대로 오름차순 힙은 꺼낸 숫자를 그냥 나열하면 정렬이 완료될 것입니다.) 2. '꺼내고 재구축' 반복 힙에 저장된 숫자를 하나씩 '꺼내고 재구축'하는 것을 반복해주면 정렬이 완료됩니다. (재구축을 하는 방법은 '[자료 구조] 힙'을 참고하세요.) 힙 정렬을 위해 n개의 숫자를 저장할 때 걸리는 시간은 O(n log n)이 됩니다. 빈 상..

삽입 정렬(insertion sort)은 수열의 왼쪽부터 순서대로 정렬하는 방식입니다. 작업하다 보면 좌측에는 정렬이 끝난 숫자가 오게 되고 우측에는 아직 확인하지 않은 숫자가 남게 됩니다. 우측의 미탐색 영역에서 숫자를 하나 꺼내서 정렬이 끝난 영역의 적절한 위치에 삽입해 나가는 방식입니다. -책 알고리즘 도감 위의 막대기들을 삽입 정렬을 사용해 오름차순으로 정렬해보겠습니다. 1. 처음에는 왼쪽 끝의 숫자(20)를 정렬이 끝났다고 간주합니다. 2. 아직 정렬되지 않은 숫자 중에서 왼쪽 끝에 있는 숫자(10)을 꺼내서 왼쪽에 정렬된 숫자와 비교해서 꺼낸 숫자가 더 작으면 자리를 바꿉니다. 20 > 10 이므로 20과 자리를 바꿉니다. 이제 숫자 10과 20은 정렬이 된 것으로 간주합니다. 따라서 정렬되지..

선택 정렬(selection sort)에서는 '수열 중에서 최소값을 검색해서 왼쪽 끝에 있는 숫자와 교체하는 작업을 반복합니다. 수열 중에서 최소값을 찾을 때는 선형 탐색을 사용합니다. -책 알고리즘 도감 위와 같이 서있는 막대기들을 선택 정렬을 사용해 오름차순으로 정렬해보겠습니다. 1. 선형 탐색을해서 최소값을 찾습니다.(여기서는 10) 그리고 왼쪽 끝에 있는 20과 자리를 바꿉니다. (만약, 최소값이 이미 왼쪽끝에 있다면 그대로 둡니다.) 그리고 이제 제일 왼쪽에 있는 10은 신경쓰지 않습니다. 2. 이제 남은 4개의 숫자중에서 최소값을 찾아서 20과 자리를 바꿉니다. 여기서는 4개의 숫자중 최소값이 20이므로 그대로 둡니다. 그리고 이제 정렬된 20도 신경쓰지 않습니다. 3. 이제 남은 3개의 숫자..

버블 정렬(bubble sort)은 '오른쪽부터 왼쪽 방향으로 인접한 두 개의 숫자를 비교해서 교환하는 작업을 반복합니다.' 오른쪽부터 왼쪽으로 숫자를 옮겨가는 모양이 물속에서 거품이 올라오는 모양과 비슷하다고 해서 버블이라고 합니다. -책 알고리즘 도감 위의 그림처럼 생긴 막대기들을 버블 정렬을 이용해 오름차순으로 정렬한다고 해봅시다. 오른쪽부터 왼쪽 방향으로 인접한 두 개의 숫자를 비교해서 교환하는 작업을 반복한다고 했죠? 오른쪽부터 좌우 숫자를 비교해서 오른쪽 숫자가 작으면 위치를 바꿔줍니다. 1. 40과 50을 비교한다. 40이 더 작으므로 50과 위치를 변경한다. 2. 30과 40을 비교한다. 30이 더 작으므로 위치를 변경하지 않는다. 3. 10과 30을 비교한다. 10이 더 작으므로 위치를 ..