Im heedy

06-6 퀵 정렬 퀵 정렬 알아보기 퀵 정렬(quick sort): 가장 빠른 정렬 알고리즘 위 그림은 퀵 정렬 알고리즘을 사용하여 학생 그룹을 키 순서로 정렬하는 과정을 나타냈습니다. 먼저 키가 168cm인 학생 A를 선택하여 이 학생을 기준으로 168cm 미만인 그룹과 168cm 이상인 그룹으로 나눕니다. 이때 그룹을 나누는 기준(학생 A의 키)을 피벗(pivot)이라고 합니다. [피벗은 다른 말로 중심축이라고 합니다. 피벗은 임의로 선택할 수 있고, 선택된 피벗은 2개로 나눈 그룹 어디에 넣어도 상관없습니다.] 다시 각 그룹에서 피벗을 선택하여 나누기를 반복하며 모든 그룹이 1명씩 남으면 정렬이 완료됩니다. 배열을 두 그룹으로 나누기 먼저 피벗을 x, 왼쪽 끝 원소의 인덱스를 pl(왼쪽 커서), 오..

06-5 셸 정렬 단순 삽입 정렬의 특징 장점: 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상태에서는 속도가 아주 빠릅니다. 단점: 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아집니다. 셸 정렬 알아보기 셸 정렬(shell sort): 단순 삽입 정렬의 장점은 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘 셸 정렬은 단순 삽입 정렬의 장점을 살리고 단점을 보완하기 위해 사용합니다. 정렬 횟수는 늘어나지만 전체적으로 원소의 이동 횟수가 줄어들어 효율적입니다. 실습 6-8 셸 정렬 알고리즘 구현하기 # 셸 정렬 알고리즘 구현하기 from typing import MutableSequence def shell_sort(a: MutableSequence) -> None: """셸 정렬""" n = l..

06-4 단순 삽입 정렬 단순 삽입 정렬 알아보기 단순 삽입 정렬(straight insertion sort): 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘 단순 선택 정렬과 비슷해 보이지만 값이 가장 작은 원소를 선택하지 않는다는 점이 다릅니다. 정렬된 부분과 아직 정렬되지 않은 부분에서 다시 배열을 구성할 경우에는 다음 작업을 n - 1번 반복하면 정렬이 완료됩니다. 아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입합니다. 단순 삽입 정렬의 알고리즘 개요는 다음과 같습니다. for i in range(1, n): tmp ← a[i]를 넣습니다. tmp를 a[0], ···, a[i -1]의 알맞은 위치에 삽입합니다. 위 그림에서 반복 제어 변수 j에 i..

06-3 단순 선택 정렬 단순 선택 정렬 알아보기 단순 선택 정렬(straight selection sort): 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘 단순 선택 정렬에서 교환 과정은 다음과 같습니다. 아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택합니다. a[min]과 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환합니다. 이 과정을 n - 1번 반복하면 정렬하지 않은 부분이 없어지면서 정체 정렬을 완료합니다. 이 알고리즘의 개요는 다음과 같습니다. for i in range(n - 1): min# a[i], ···, a[n-1]에서 키값이 가장 작은 원소의 인덱스 a[i]와 a[min]의 값을 교환합니다. 실습 6-6 단순 선택 ..

06-2 버블 정렬 버블 정렬(bubble sort): 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘으로, 단순 교환 정렬이라고도 합니다. 버블 정렬 알아보기 위 그림은 이웃한 원소를 비교하고, 필요하면 교환하는 전체 작업 과정입니다. 이때 원소 수가 n인 배열에서 n -1번 비교·교환을 하면 가장 작은 원소 1이 맨 앞으로 이동합니다. 이러한 일련의 비교·교환하는 과정을 패스(pass)라고 합니다. 버블 정렬 프로그램 실습 6-1 버블 정렬 알고리즘 구현하기 이 프로그램은 n개의 원소 수와 각각의 원솟값을 입력받습니다. i값을 0부터 n - 2까지 1씩 증가시키고, 패스를 n - 1번 수행합니다. # 버블 정렬 알고리즘 구현하기 from typing import Mutab..

06-1 정렬 알고리즘 정렬이란? 정렬(sorting): 이름, 학번, 학점 등의 키(key)를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘여놓는 작업을 말합니다. 오름차순(ascending order): 값이 작은 데이터를 앞쪽에 늘어놓는 것 내림차순(descending order): 값이 큰 데이터를 앞쪽에 늘어놓는 것 정렬 알고리즘의 안정성 안정적인 알고리즘: 값이 같은 원소의 순서가 정렬한 후에도 유지되는 것 안정적이지 않은 알고리즘: 정렬한 후에도 우너래의 순서가 유지된다는 보장을 할 수 없는 것 내부 정렬과 외부 정렬 내부 정렬(internal sorting): 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘 외부 정렬(external sort..