[85] 알고리즘 04차시 기본적인 정렬 알고리즘

1. 선택 정렬

가. 정렬(Sorting)

데이터의 순서를 결정하는 것

데이터를 저장하는 위치에 따라 내부 정렬(Internal Sort)과 외부 정렬(External Sort)로 구분

나. 내부 정렬

데이터 양이 적을 때 주기억장치 내에 저장한 자료를 대상으로 정렬하는 방법

정렬할 자료의 양이 적어서 자료 전체가 주기억장치에 저장될 수 있는 경우에는 내부 정렬을 사용하여 자료를 정렬

선택 정렬, 버블 정렬, 삽입 정렬, 쉘 정렬, 퀵 정렬 등

다. 외부 정렬

입력의 크기가 주기억 장치 공간보다 큰 경우 보조 기억 장치에 있는 입력을 여러 번에 나누어 주기억 장치에 읽어 들인 후 정렬하여 보조 기억 장치에 다시 저장하는 과정을 반복

라. 정렬 알고리즘의 복잡도

대부분 \(O(n^{2})\)과 \(O(n\log{n})\) 사이

입력이 특수한 성질을 만족하는 경우에는 \(O(n)\) 정렬도 가능

마. 기본적인 정렬 알고리즘

평균적으로 \(O(n^{2})\)의 시간이 소요되는 정렬 알고리즘들

선택 정렬, 버블 정렬, 삽입 정렬

바. 선택 정렬

실제로 많이 사용하는 내부 정렬에 속함.

주어진 데이터에서 가장 큰 값이나 가장 작은 값을 찾은 후 그 값만을 교환하는 방식으로 단계적으로 정렬함.

각 루프마다 최대 원소를 찾아 맨 오른쪽 원소와 교환하고 맨 오른쪽 원소를 제외함.

하나의 원소만 남을 때까지 위의 루프를 반복

수행 시간: \( (n-1) + (n-2) + \cdots+ 2+ 1 = O(n^{2}) \)

사. 선택 정렬의 특징

입력이 거의 정렬되어 있든지, 역순으로 정렬되어 있든지, 랜덤하게 되어 있든지를 구분하지 않고 항상 일정한 시간복잡도를 나타냄.

입력에 민감하지 않은 알고리즘

https://ko.wikipedia.org/wiki/선택_정렬

선택 정렬 - 위키백과, 우리 모두의 백과사전

2. 버블 정렬

이웃하는 숫자를 비교하여 작은 수를 앞으로 이동시키는 과정을 반복하여 정렬하는 알고리즘

주어진 파일에서 인접한 2개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식

오름차순으로 정렬한다면 작은 수는 배열의 앞부분으로 이동

수행 시간: \( (n-1) + (n-2) + \cdots+ 2+ 1 = O(n^{2}) \)

https://ko.wikipedia.org/wiki/버블_정렬

버블 정렬 - 위키백과, 우리 모두의 백과사전

3. 삽입 정렬

새로운 데이터를 정렬된 데이터에 삽입하는 과정을 반복하여 전체 데이터를 정렬하는 방식

가장 간단한 정렬 방식

이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식

어느 정도 정렬이 되어 있을 경우 매우 효과적

삽입 정렬 복잡도: 최악(\(O(n^{2})\)), 평균(\(O(n^{2})\)), 최선(\(O(n)\))

가. 삽입 정렬의 특징

입력의 상태에 따라 수행 시간이 달라질 수 있음.

입력이 이미 정렬되어 있으면 항상 각각 현재 원소가 자신의 왼쪽 원소와 비교 후 자리이동 없이 원래 자리에 있게 됨.

따라서 \((n-1)\)번의 비교만 하면 정렬을 마치게 됨.

이때가 삽입 정렬의 최선 경우이고 시간복잡도는 \(O(n)\)

삽입 정렬은 거의 정렬된 입력에 대해서 다른 정렬 알고리즘보다 빠름

https://ko.wikipedia.org/wiki/삽입_정렬

삽입 정렬 - 위키백과, 우리 모두의 백과사전