[기본] 정렬 알고리즘

알고리즘/지식

미니소곰 2020. 3. 2. 22:29

정렬 알고리즘

정렬 알고리즘은 주어진 배열이나 리스트의 원소를 비교 연산자에 따라 재배열하는데 사용됩니다.

비교 연산자는 각 각의 데이터 구조의 원소 순서를 정할때 사용됩니다.

제자리 정렬이란? in-place sorting

제자리 정렬 알고리즘은 정렬하기위해 일정한 추가 공간을 사용합니다..(주어진 배열만 사용)

주어진 리스트에 속한 원소의 순서만 바꿔서 리스트를 정렬합니다.

삽입 정렬과 선택 정렬은 추가적인 공간을 사용하지 않기에 제자리 정렬 알고리즘입니다.

합병정렬과 카운팅정렬은 제자리 정렬 알고리즘이 아닙니다.

내부정렬과 외부 정렬이란? internal sortring, external sorting

정렬해야할 데이터가 메모리에 한번에 올라올 수 없다면 외부 정렬이라고 합니다.

외부 정렬은 많은 양의 데이터를 정렬할 때 사용합니다.

외부 정렬을 위해 하드디스크, ssd를 사용합니다.

모든 데이터를 메모리에 두는 경우 내부정렬이라고 합니다.

안정 정렬이란? stable sorting

정렬 알고리즘의 안정성

안정성은 키-값 구조에서 같은 키를 갖는게 가능한 경우 중요합니다.

사람 이름처럼 동명이인이 나오고 그 인물의 데이터는 다른경우.

그리고 이 것을 키로 정렬하고 싶은 경우 알고리즘의 안정성에 신경써야합니다.

안정성이란?

같은 키 값을 갖는 원소들이 정렬되기 전의 상대적 위치와 정렬된 후의 상대적 위치가 같은 것을 말합니다.

두개의 원소를 갖는 다음과 같은 리스트를 정렬하는 경우

처음 원소로 정렬하기 위해

(1, A), (5, A), (2, A), (3, B), (2, B)를 정렬하는 경우 먼저 앞의 원소로 정렬을 하고

두번째 원소로 정렬하기 위해

(1, A), (2, A), (2, B), (3, B), (5, A) 다시 두번째 원소로 정렬을 합니다.

(1, A), (2, A), (5, A), (3, B), (2, B) 이때 불안정 정렬 알고리즘인 경우 두번째 원소만 신경 써서 배열하여 앞에서 했던 정렬이 무너질 수 있습니다. 이 때 안정 정렬을 사용하면 원하는 값을 얻을 수 있습니다.

어떤 정렬이 안정적인가?

버블정렬, 삽입 정렬, 합병정렬, 카운팅 정렬은 안정적입니다.

퀵정렬, 힙정렬은 불안정 정렬입니다.