평균적으로 Θ(nlogn)의 시간이 소요되는 고급 정렬 알고리즘들 ✔️ 병합정렬(merge sort) ✔️ 퀵정렬(quicksort) ✔️ 힙정렬(heap sort) 📌 병합 정렬(merge sort) 병합 정렬은 먼저 입력된 배열을 반으로 나눈다. 이렇게 나눈 전반부와 후반부를 각각 독립적으로 정렬한다. 마지막으로 정렬된 두 부분을 합쳐서, 즉 병합하여 정렬된 배열을 얻는다. 여기서 전반부를 정렬할 때도 역시 반으로 나눈 다음 정렬해서 병합한다. 후반부도 마찬가지이다. 이 병합하는 일을 재귀적으로 반복한다. 배열을 오름차순으로 정렬한다. 각 루프마다 1️⃣ 배열을 이등분하기 위해 중간 지점을 계산한다 2️⃣ 전반부와 후반부를 각각 독립적으로 정렬한다 3️⃣ 정렬된 전반부와 후반부가 병합되어 하나의 정렬..

평균적으로 Θ(n2)의 시간이 소요되는 정렬 알고리즘들 ✔️ 선택 정렬(selection sort) ✔️ 버블 정렬(bubble sort) ✔️ 삽입 정렬(insertion sort) 📌 삽입 정렬(insert sort) 삽입 정렬은 이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더 더하여 정렬된 i+1개짜리 배열을 만드는 과정을 반복한다. 선택 정렬과 버블 정렬이 n개 짜리 배열에서 시작하여 그 크기를 하나씩 줄이는 데 반하여, 삽입 정렬은 한 개 짜리 배열에서 시작하여 그 크기를 하나씩 늘리는 정렬이다. 배열을 오름차순으로 정렬한다. 각 루프마다 1️⃣ 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교한다. 2️⃣ 비교했을 때 작다면 비교 대상이 되는 원소의 왼쪽, 크다면 오른쪽에 삽입한다..

평균적으로 Θ(n2)의 시간이 소요되는 정렬 알고리즘들 ✔️ 선택 정렬(selection sort) ✔️ 버블 정렬(bubble sort) ✔️ 삽입 정렬(insertion sort) 📌 버블 정렬(bubble sort) 버블 정렬도 선택 정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복한다. 다만 제일 큰 원소를 오른쪽으로 옮기는 방법이 다를 뿐이다. 배열을 오름차순으로 정렬한다. 각 루프마다 1️⃣ 왼쪽부터 시작해 이웃한 쌍들을 비교해나간다. 2️⃣ 순서대로 되어 있지 않으면 두 원소를 서로 교환한다. 3️⃣ 맨 오른쪽 원소를 제외한다. (가장 큰 원소는 자기 자리를 찾았기 때문) 〰️ 하나의 원소가 남을 때까지 위의 루프를 반복한다. 📌 버블 정렬(bubble sort) 알고리즘의 특징 👍🏻 장..

평균적으로 Θ(n2)의 시간이 소요되는 정렬 알고리즘들 ✔️ 선택 정렬(selection sort) ✔️ 버블 정렬(bubble sort) ✔️ 삽입 정렬(insertion sort) 📌 선택 정렬(selection sort) 선택 정렬은 원리가 간단한 정렬 알고리즘 중 하나다. 배열을 오름차순으로 정렬한다. 각 루프마다 1️⃣ 최대 원소를 찾는다. 2️⃣ 최대 원소와 맨 오른쪽 원소를 교환한다. 3️⃣ 맨 오른쪽 원소를 제외한다. (가장 큰 원소는 자기 자리를 찾았기 때문) 〰️ 하나의 원소만 남을 때까지 위의 루프를 반복한다. 📌 선택 정렬(selection sort) 알고리즘의 특징 👍🏻 장점 - 자료 이동 횟수가 미리 결정된다 👎🏻 단점 - 안정성을 만족하지 않는다 - 즉, 값이 같은 레코드가 있..