[ 알고리즘 ] 정렬 알고리즘

버블 정렬(bubble sort)

양옆에 위치한 두 값을 비교하면서 크기 순으로 정렬한다.

 

⏰ 시간 복잡도 계산

배열의 n번째 요소(마지막 요소)를 정렬하는 데 n-1번 비교한다.

배열의 n-1번째 요소를 정렬하는 데 n-2번 비교한다.

=> (n-1)+(n-2)+(n-3)+ ··· + 2 + 1 = n(n-1) / 2

 

시간 복잡도 : O(n²)

 

 

 

선택 정렬(selection sort)

배열을 순회하면서 배열의 앞에서부터 차례대로 각 인덱스에 들어갈 값을 선택해 위치시킨다.

예) 오름차순 : 배열의 첫번째 자리에 최솟값, 두번째 자리에 최솟값 다음으로 작은 값

 

⏰ 시간 복잡도 계산(오름차순)

배열의 첫 번째 요소를 찾는데 n-1번 비교한다.

배열의 두 번째 요소를 찾는데 n-2번 비교한다.

=> (n-1)+(n-2)+(n-3)+ ··· + 2 + 1 = n(n-1) / 2

 

시간 복잡도 : O(n²)

 

 

 

 

삽입 정렬(insertion sort)

배열을 앞에서부터 순회하면서 정렬된 부분의 적절한 위치에 값을 삽입하는 방식이다.

 

⏰ 시간 복잡도 계산(오름차순)

첫 번째 : 한 개의 데이터를 정렬되었다고 생각하고 두 번째 데이터를 첫번째 데이터 앞이나 뒤에 삽입한다. (1개의 데이터 검사)

두 번째 :  두 개의 데이터를 정렬되었다고 생각하고 세 번째 데이터를 적절한 위치에 삽입한다. (2개의 데이터 검사)

세 번째 :  세 개의 데이터를 정렬되었다고 생각하고 네 번째 데이터를 적절한 위치에 삽입한다. (3개의 데이터 검사)

=> 1 + 2 + 3 + ··· + (n-2) + (n-1) = n(n-1) / 2

 

시간 복잡도 : O(n²)

 

 

 

합병 정렬(merge sort)

재귀를 이용하는 분할 정복 알고리즘이다분할 : 배열을 쪼개는 것, 정복 : 분할한 배열을 정렬하면서 하나로 합병하는 것

 

⏰ 시간 복잡도 계산

배열을 정렬하는 데 걸리는 시간 : O(n)배열의 합병 시 걸리는 시간 : O(logn)

 

시간 복잡도 : O(n logn)

 

 

 

힙 정렬(heap sort)

최대 힙이나 최소 힙 자료구조를 이용해 정렬을 수행한다.최대 힙 : 오름차순, 최소 힙 : 내림차순

 

💡 힙 정렬 과정

1. 배열을 힙으로 만든다. -> 자식노드가 부모 노드보다 크거나 같도록
2. 최대 힙에서 삭제 연산을 이용해 정렬을 수행한다.
   1. 루트노드를 삭제 -> 트리의 맨 마지막 노드와 위치 변경하고 기존 루트노드를 힙에서 제외한다.
   2. 마지막 노드였던 노드를 차례대로 위치 교환을 통해 최대 힙 속성을 만족 시킨다.
   3. 반복한다.
      * 왼쪽 자식 : 2n + 1, 오른쪽 자식 : 2n + 2, 부모 : (n-1) / 2

 

⏰ 시간 복잡도 계산

힙 생성 알고리즘을 수행하는 데 O(log n)

전체 요소가 n개여서 전체 정렬하는데 O(n log n)이 걸린다.

 

시간 복잡도 : O(nlog n)

 

 

 

 

퀵 정렬(quick sort)

퀵 정렬도 합병 정렬과 마찬가지로 분할 정복 알고리즘이다.피봇(pivot)이라는 특정 값을 선택해서 피복보다 작은 값, 큰값으로 구성된 배열로 분할해서 정렬한다.

• 분할은 배열의 크기가 1 이하가 될 때까지 반복한다.

 

⏰ 시간 복잡도 계산

평균 : 피봇이 가운데에 위치하게 되고 다음 각각의 피봇도 각각의 배열의 가운데에 위치하게 된다면 nlogn의 시간이 걸린다.

최악 : 피복이 계속 오른쪽이나 왼쪽에 위치하게 되면 n² 의 시간이 걸린다.

 

평균 시간 복잡도 : O(n logn) -> 피봇을 기준으로 배열을 균등하게 분할할 수 있을 때

최악 시간 복잡도 : O(n²) -> 역순으로 정렬된 배열일 때 배열이 분할되지 않는다.

 

☝🏻 즉, 피봇으로 어떤 값을 선택하느냐에 따라 퀵 정렬의 성능이 좌우된다.

 

 

 

기수 정렬(radix sort)

비교하지 않는 알고리즘으로, 낮은 자릿수부터 정렬을 수행한다.

 

💡 기수 정렬 과정

1. 0-9까지 버킷이라는 큐 배열을 만든다
2. 첫번째 자릿수에 해당하는 큐에 데이터를 넣는다.
3. 0번 큐부터 차례대로 데이터를 꺼내고
4. 두번째  자릿수에 해당하는 큐에 데이터를 넣는다.
5. 0번 큐부터 차례대로 데이터를 꺼낸다.
6. 반복한다.

 

⏰ 시간 복잡도 계산

자릿수별로 비교하는 시간 O(n)

자릿수만큼 수행 O(d)

 

시간 복잡도 : O(dn) -> d는 가장 큰 데이터의 자릿수

 

☝🏻 시간복잡도가 빠른 편에 속하지만 버킷이라는 큐를 만들기 위해 추가 메모리가 필요하고, 정렬할 수 있는 데이터 타입이 한정적이다.

 

 

 

계수 정렬(counting sort)

데이터의 개수를 세서 정렬하는 방식이다.

 

💡 계수 정렬 과정

1. 만약 데이터의 범위가 0-99라면 크기가 100인 배열을 만든다
2. 정렬하려는 배열을 순회하며 해당 데이터를 배열의 인덱스로 취급하고 ++연산을 수행한다.
   * 계수 정렬은 데이터의 범위가 0또는 양의 정수여야한다.

 

⏰ 시간 복잡도 계산

정렬하려는 데이터의 개수 n,

정렬하려는 데이터의 범위 k

=> 범위 배열에 넣기 위해 순회하는 시간 n, 정렬을 위해 배열을 탐색하는 시간 k

 

시간 복잡도 : O(n+k)

-> 데이터의 범위가 무한대이면 시간 복잡도 역시 무한으로 수렴한다. 즉, 정렬하려는 데이터의 범위가 시간 복잡도에 영향을 끼침

 

☝🏻 기수 정렬과 같이 메모리 공간이 사용된다.(데이터 범위만한 크기의 배열을 생성해야함)