동빈북 6장 개념정리 정렬(Sort)

정렬의 사전적 의미는 말그대로 요소를 순서대로 놓는것이다.

예를들어 2,5,10,9,8 이라는 숫자들이 나열되어 있을때, 2, 5, 8, 9, 10 등으로 말이다.

정렬에는 굉장히 여러가지 종류가 있는데,

삽입정렬, 선택정렬, 버블정렬, 퀵정렬, 힙정렬, 합병정렬 등 여러가지가 있다.

이 정렬들이 어떻게 구현되어 있고(어떤 방법을 이용하여 정렬했는지)

시간복잡도가 얼마나 되며 왜 그런 복잡도를 가지는지를 아는 것은 매우 중요하다.

(사실 나도 삽입 정렬이랑 선택 정렬은 아직도 햇갈린다.)

그래서 정리를 하려고 한다.

• 선택정렬

저장된 데이터의 요소 중 최소값을(또는 최대 값) 찾고 데이터의 요소 중 첫번째와 뒤집는 방식이다.

• 삽입정렬

저장된 데이터의 요소를 하나씩 찾아서 올바른 위치에 삽입 해준다.

즉, 오름차순을 예로들면 내가 선택한 key의 값보다 작은 요소가 있는 부분 뒤에 집어 넣는다.

• 버블정렬

모든 키값을 한번씩 돌며 key+1의 요소가 자신보다 더 작다면 뒤집는다.

이 동작을 모든 요소에서 반복한다.

이상 N^2의 시간 복잡도를 가지는 정렬들이었다.

• 퀵정렬

이 방식은 분할정복을 이용한 방식이다.

키 값을 초기에 중앙값 또는 배열의 첫번째 요소를 두고 left와 right를 둔다.

그 키 값을 기준으로 작으면 왼쪽 크면 오른쪽으로 배열을 재배치 한다.

그러면 그 키값은 올바른 곳에 가 있는거이므로 left와 rigth를 -1,+1로 갱신해준다.

이것을 재귀적으로 반복한다.

이렇게 하면 각 원소가 한개가 될 때까지(또는 받은 배열의 요소가 없을 때 까지) 반복한다.

시간복잡도의 경우 N개의 원소가 될 때 까지 반씩 잘라서 정렬하므로 O(NlogN)의 복잡도를 가지게 된다. 그러나, 완전히 한쪽으로 편향되어있는 배열의 경우는 최악의 경우 시간복잡도가O(N^2)을 가진다.

우선은 3가지만 정리를 하고 안정정렬과 불안정정렬의 차이점에 대해서 설명해보겠다.

이 경우는 보통 MAP과 같은 자료구조를 사용할때에 등장하는 개념이다.

 

 

위 사진을 보면 직관적으로 이해될 것이라 생각한다.

그러므로 삽입정렬과 버블정렬 그리고 합병정렬(머지소트)는 안정정렬이며

선택정렬과 퀵정렬의 경우는 불안정 정렬이다.

선택정렬과 퀵정렬이 불안정 정렬인 이유는 동작 순서를 보면 대충 예상할 수 있는데,

선택 정렬의 경우 배열 요소중 최소의 숫자를 특정위치와 뒤집기 때문에 순서가 뒤집힐 수 있다.

퀵정렬 역시 마찬가지이다.

반면 삽입정렬의 경우 그 요소를 찾아서 뒤집지않고 한칸씩 밀며 삽입하기 때문에 순서가 바뀌지 않는다. 또한, 버블정렬은 비교할때에 바로 뒤의 원소만 비교하기 때문에 또 순서가 바뀌지 않는다.

또한, 정렬에 따라 메모리를 추가적으로 사용하느냐 안하느냐에 따른 분류도 있다.