[알고리즘]정렬

 

◆◆정렬의 개념

◆정렬의 개념

●정렬의 정의

▷다수의 데이터를 일정항 규칙에 따라 순서대로 나열하는 방법이다.

- 오름차순(Ascending Order) : 작거나 앞선 데이터부터 순서대로 나열

- 내림차순(Descending Orde) : 크거나 뒷선 데이터부터 역순으로 나열

 

●정렬의 종류별 시간 복잡도

정렬 방식	평균	최악
삽입 정렬	O(N²)	O(N²)
버블 정렬	O(N²)	O(N²)
선택 정렬	O(N²)	O(N²)
쉘 정렬	O(N^1.5)	O(N²)
힙 정렬	O(NlogN)	O(NlogN)
이진 병합 정렬	O(NlogN)	O(NlogN)
퀵 정렬	O(NlogN)	O(N²)  //로직 추가로 O(NlogN) 가능
버킷 정렬	O(D+N)	O(N²)
계수 정렬(Counting sort)	O(N+K)	O(N+K)
기수 정렬(Radix sort)	O(N+K)	O(N+K)

---

◆◆정렬의 종류

◆선택 정렬

▷정렬 대상 중 기준값(Key)으로 선택된 데이터를 나머지 데이터와 비교하는 정렬 방식이다.

▷기준값과 나머지 데이터의 최소값을 찾아 둘의 자리를 바꿔준다.

▷데이터가 10000개 이상이면 정렬 속도가 급격하게 느려진다.

 

◆버블 정렬

▷정렬 대상 중 기준값으로 지정한 데이터와 해당 데이터의 다음 데이터와 비교하는 정렬 방식이다.

▷기준값과 오른쪽 데이터를 비교하여 필요시 서로를 교환하고 기준값을 오른쪽 값으로 변경한다.

 

◆삽입정렬

▷정렬 대상 중, 좌측에 이미 정렬된 요소와 비교하여 자신의 위치를 찾아 삽입하는 정렬 방식이다.

▷좌측 데이터와 비교해야 하므로 두 번째 데이터부터 정렬을 진행한다.

▷좌측 데이터가 삽입되면 기존의 데이터는 우측으로 한칸씩 이동한다.

▷비교범위는 단계와 맞게 커진다.

▷O(N²)이지만, 현재 배열의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. (퀵보다 빠를 수 있다.)

 

◆쉘 정렬

▷많은 데이터의 이동이 필요한 삽입 정렬의 단접을 보완한 정렬방식이다.

▷데이터들의 간격을 정하고 간격을 점차 줄여가면서 삽입 정렬을 진행하는 정렬 방식이다.

- 데이터의 수가 적거나 보편적인 상황에서의 공식 : N/2

 

◆힙 정렬

▷정렬 대상을 완전 이진 트리 형태로 만들어 정렬하는 방식이다.

▷자식 노드가 부모 노드보다 큰 경우 자료를 교환한다.

▷힙이 전부 삭제되면 오름차순 정렬되어 저장된다.

 

◆이진 병합 정렬??

▷두 데이터를 한 쌍으로 병합하여 정렬하고, 정렬된 두 그룹을 다시 한 쌍으로 하여 정렬을 반복하는 방식이다.

▷각 그룹의 요소를 비교하여 작은 값을 우선 병합하여 정렬한다.

 

◆버킷 정렬

▷정렬 대상의 데이터 범위를 균등하게 나눈 여러 버킷을 생성하여 정렬하는 방식이다.

▷데이터 범위 파악이 가능해야 한다.

▷각각의 버킷은 스택을 이용하여 정렬한다.

 

◆퀵 정렬

▷하나의 리스트를 기준값을 기준으로 2개의 비균등 크기의 배열로 분할하여 정렬하는 방식이다.

▷분할 정복 알고리즘을 적용한 정렬 기법으로, 매우 빠른 시간 복잡도를 가진다.

- 분할(Divide)  :  기준값(pivot)을 기준으로 큰 값은 오른쪽, 작은 값은 왼쪽의 부분 배열로 집합

- 정복(Conquer) : 부분 배열을 다시 문할, 적절한 크기가 되면 정렬

- 결합(Combine) : 정렬된 부분 배열들을 하나로 결합

▷순환 호출을 이용하여 정렬을 반복한다.

▷C++에서는 퀵 정렬을 기반으로 작성된 정렬 라이브러리를 제공하여 최악의 경우에도 시간 복잡도 O(NlogN)을 만족한다.

 

◆계수 정렬

▷각 요소의 배열 등장 횟수를 count해 index에 누적합으로 나타내는 배열을 만든뒤

▷그 배열을 사용해 index에 들어있는 수만큼 반복해서 출력하는 정렬이다.

▷최소값부터 큰 값까지 배열을 하나 선언해야해서 메모리 낭비가 클 수 있다.

 

◆기수 정렬

▷자리수를 기준으로 비교하는 정렬이다.

▷데이터 타입이 일정해야 하고, 양의 정수끼리 음의 정수끼리 비교해야하여 조건이 많다.

▷k는 자리수이다.