기본적인 정렬 알고리즘

선택 정렬

 

정렬?

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

-데이터를 저장하는 위치에 따라 내부정렬과 외부정렬로 구분한다

 

내부 정렬

-데이터 양이 적을 떄 주기억장치 내에 저장한 자료를 정렬하는 방법

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

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

 

외부 정렬

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

 

정렬 알고리즘의 복잡도

 

기본적인 정렬 알고리즘

-선택, 버블, 삽입 정렬등이 있다.

 

선택 정렬

-각 루프마다

    >최대 원소를 찾음

    >최대 원소와 맨 오른쪽 원소를 교체함

    >맨 오른쪽 원소를 제외함

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

ㄴ특징

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

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

 

버블정렬

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

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

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

 

삽입 정렬

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

-가장 간단한 정렬 방식

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

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

 

방식

-처음 A[0]으 정렬된 데이터로 취급

-다음 데이터 A[1]은 정렬된 데이터 A[0]과 비교하여 적절한 위치에 삽입

-다음 데이터 A[2]는 정렬된 데이터 A[0]과 비교하여 적절한 위치에 삽입

-다음 데이터 A[2]는 정렬된 데이터 A[0], A[1]과 비교하여 적정한 위치에 삽입

-같은 방식으로 나머지 데이터들을 삽입하여 정렬

 

특징

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

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

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

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

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

-반면에 역으로(반대로) 정렬된 입력에 대해서는 O(n2) 시간이 걸림

-삽입 정렬의 평균 경우 시간복잡도는 최악 경우와 같음