정렬 알고리즘

 정렬 알고리즘은 정렬 방식에 따라서 선택 정렬, 삽입 정렬, 버블 정렬, 셸 정렬 등으로 나눌 수 있습니다. 이 각각은 간단하고 이해하기도 쉽다는 장점이 있지만, 속도 면에서는 그다지 빠르다고 볼 수 없습니다.

 정렬 알고리즘은 정렬 방식에 따른 분류 외에도 다른 분류 방법들이 있습니다.

 ● 내부 정렬 알고리즘(Internal Sort Algorithm) : 메모리에 있는 데이터를 정렬합니다.
 ● 외부 정렬 알고리즘(External Sort Algorithm) : 파일이나 외부의 특정한 저장 공간에 있는 데이터를 정렬합니다.
 ● 직접 정렬 알고리즘(Direct Sort Algorithm) : 실제 데이터를 직접 재배치하며 정렬합니다.
 ● 간접 정렬 알고리즘(Indirect Sort Algorithm) : 데이터가 저장된 주소 값만을 바꾸며 정렬합니다.

 알고리즘의 시간을 따질 때에는 시간복잡도(O(n))를 사용합니다. 예를 들어, for문 2개를 이용해서 정사각형을 길이 n만큼 찍는다고 할 때, 시간복잡도로는 O(n^2)으로 나타냅니다.

위에 예시로 들었던 선택 정렬, 삽입 정렬, 버블 정렬의 시간 복잡도는 주로 O(n^2)의 형태를 띄게 됩니다.