1. 정렬 알고리즘 [Sorting]

 

정렬 알고리즘 (Sorting Algorithm)

 

무작위로 섞여있는 데이터를 어떤 기준에 맞춰 정렬하는 알고리즘

 

 

정렬 알고리즘은 다양한 경우에 매우 유용하게 사용됨

 

• 각종 데이터 목록을 정리하고 싶을 때
  
  
• 분포도의 중위값을 알아내고 싶을 때
  
  
• 데이터에서 중복값을 잡아내고 싶을 때
  
  
• 이진 탐색을 하고 싶을 때

 

사실, 자바스크립트에서 정렬을 하고자할때 sort()라는 메서드를
사용하면 정렬을 해준다. 하지만 정렬 알고리즘을 배우는 이유는
데이터들의 양이나 상황에 따라 어떤 정렬을 사용하는 것이
좋은지를 알고 가리기 위해 몇몇 유명한 정렬 알고리즘을 알아보려한다.

 

 

알아볼 정렬 알고리즘:

 

1. 버블 정렬
   
   
2. 선택 정렬
   
   
3. 삽입 정렬
   
   
4. 퀵 정렬
   
   
5. 힙 정렬
   
   
6. 병합 정렬

 

 

먼저, 정렬의 Stable정렬, In-place정렬에 대해 알아보자

 

 

Stable 정렬

 

정렬을 했을 때 중복된 값들의 순서가 변하지 않는 것

예를 들어, 

arr=[1,2,3,4,5(1),5(2),7] 이면 Stable (안정)

arr=[1,2,3,4,5(2),5(1),7] 이면 Unstable (불안정)

 

 

In-place 정렬

 

정렬하는데 추가적인 메모리 공간이 거의 들지않는 것

즉, 제자리 정렬이다.

 

 

 

1. 버블 정렬

 

버블정렬은 첫번째 원소부터 인접한 원소와 비교하며

자리를 바꾸면서 맨 끝부터 정렬하는 방식

 

 

⏱️시간 복잡도

 

• 어떠한 경우에도 2개의 원소를 비교하기 때문에
  최선, 평균, 최악 모든경우 O(n^2)로 동일하다.

 

 

👍 장점

 

• 구현이 매우 간단
  
  
• 정렬하고자 하는 배열 안에서 교환하는 방식 In-place방식
  
  
• Stable 정렬

 

 

👎 단점

 

• 시간복잡도가 최악, 최선, 평균 모두 O(n^2)로 비효율적
  
  
• 데이터를 하나씩 비교하기 때문에 시간이 오래걸림
  
  
• 정렬된 상태에서 새로운 데이터가 추가되면 정렬 효율이 안좋아짐

---

 

2. 선택 정렬

 

선택정렬은 앞쪽부터 정렬하는 방식

주어진 배열에서 가장 작은 최소값을 찾고,
배열의 맨앞의 값과 위치를 바꾸면서 정렬

 

 

⏱️시간 복잡도

 

• (n-1) + (n-2) + ... + 2 + 1 = n(n-1) / 2 이기때문에
  최선, 평균, 최악 모든경우 O(n^2)로 동일하다.

 

 

👍 장점

 

• 구현이 매우 간단
  
  
• 정렬하고자 하는 배열 안에서 교환하는 방식 In-place방식
  
  
• 비교하는 횟수에 비해 교환하는 횟수가 적기 때문에,
  많은 교환이 일어나야 하는 자료 상태에서 비교적 효율적

 

 

👎 단점

 

• 시간복잡도가 최악, 최선, 평균 모두 O(n^2)로 비효율적
  
  
• Unstable 정렬.
  
  
• 정렬된 상태에서 새로운 데이터가 추가되면 정렬 효율이 안좋아짐

---

 

3. 삽입 정렬

 

삽입정렬은 버블정렬의 비효율성을 개선하기 위한 방법

 

i번째와 i+1번째를 비교하며 위치를 바꾼 버블정렬과는 달리

삽입 정렬은 i번째 원소를 정렬된 상태의 앞부분과 비교하여 적절한 위치에 삽입

 

 

⏱️시간 복잡도

 

• 최악의 경우(역으로 정렬되었을 때) :  (n-1) + (n-2) + .... + 2 + 1 = n(n-1 )/ 2 으로 O(n^2) 입니다.
  
  
• 하지만 최선의 경우(정렬이 모두 되어 있는 경우),
  한번씩 밖에 비교를 안하므로 O(n)의 시간복잡도를 가진다.
  

 

👍 장점

 

• 입력으로 들어오는 배열의 원소가 정렬되어 있을수록 속도가 빠름
  
  
• 정렬된 값은 교환이 일어나지 않음
  
  
• 이미 정렬된 배열에 자료를 하나씩 삽입 / 제거하는 경우
  현실적으로 최고의 정렬 알고리즘
  
  
• In-place 정렬
  
  
• Stable 정렬
  
  
• 선택 정렬, 버블 정렬과 같은 알고리즘에 비해 상대적으로 빠름

 

 

👎 단점

 

• 시간복잡도가 최악, 평균 모두 O(n^2)로 비효율적
  
  
• 선택 정렬, 버블 정렬과 마찬가지로 배열의 길이가 길어질수록 비효율

---

 

4. 퀵 정렬

 

퀵 정렬은 분할 정복 방법을 통한 정렬,

하나의 pivot(축)을 정해서 이 pivot보다 작은값은 왼쪽,

큰값은 오른쪽에 위치시키는 방법

 

왼쪽과 오른쪽에 해당하는 원소들에 대해 두개의 배열로 나눔 -> 분할

분할된 두개의 작은 배열에 대해 재귀로 이 과정을 반복

재귀 호출이 한번 진행될 때마다 최소 하나의 원소는 최종위치가 정해진다.

 

 

⏱️시간 복잡도

 

• 최선과 평균의 경우 O(nlogn) 이다.
  
  
• 최악의 경우(정렬이 되어 있는 경우) O(n^2) 이다.

 

👍 장점

 

• 불필요한 데이터의 이동을 줄이고 먼거리의 데이터를 교환
  
  
• 한번 결정된 pivot들이 추후 연산에서 제외되는 특성 때문에,
  시간복잡도 O(nlogn)을 가지는 다른 정렬 알고리즘과 비교했을 때 가장 빠름
  
  
• In-place 정렬
  
  

 

👎 단점

 

• 정렬된 배열에 대해서는 불균형 분할에 의해 오히려 수행시간이 더 많이 걸림
  
  
• Unstable 정렬

---

 

5. 힙 정렬

 

힙 정렬은 최대 힙트리(Max Heap Tree)나 최소 힙트리(Min Heap Tree)를

구성하여 정렬하는 방식

 

내림차순으로 정렬하기 위해서는 최대 힙 트리를 구성하고,

오름차순으로 정렬하기 위해서는 최소 힙 트리를 구성한다.

 

• 힙(Heap)이란?? 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조
• 완전 이진트리 란?? 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리
  
  
• 최대 힙 트리란?? 부모 노드의 키 값이 자식 노드의 키값보다 크거나 같은 완전 이진트리
  
  
• 최소 힙 트리란?? 부모 노드의 키 값이 자식 노드의 키값보다 작거나 같은 완전 이진트리
  
  

 

⏱️시간 복잡도

 

• 최선, 평균, 최악 모두 O(nlogn) 이다.
  

 

👍 장점

 

• 가장 크거나 가장 값을 구할 때 유용 -> 한번의 힙 구성을 통해 구하는 것이 가능
  
  
• 멀리 떨어진 요소들을 정렬할 때 유용
  
  
• In-place 정렬이 가능
  
  
• 항상 같은 시간 복잡도를 가지기 때문에 성능이 좋음

 

👎 단점

 

• 같은 시간 복잡도를 가진 다른 정렬 알고리즘에 비하면 느린편
  
  
• Unstable 정렬

---

 

6. 병합 정렬

 

병합 정렬은 배열을 작은 단위로 쪼개어 정렬한 결과를 합치면서

전체를 정렬하는 분할 정복 방식이다.

 

배열을 왼쪽 절반, 오른쪽 절반으로 분할하며 최소 단위로 쪼갠 후 정렬진행

쪼갠 영역들(이미 정렬된)을 차례대로 두개씩 병합

 

 

⏱️시간 복잡도

 

• 최선, 평균, 최악 모두 O(nlogn) 이다.
  
• 분할할 때 걸리는 시간 O(n), 병합에 걸리는 시간 O(n),
  그리고 레벨의 수가 O(logn)이므로 전체 레벨의 병합에 걸리는 시간은 O(nlogn)

 

👍 장점

 

• 항상 일정한 시간 복잡도 O(nlogn)을 가짐
  
  
• Stable 정렬

 

👎 단점

 

• 정렬을 하는 배열외의 추가적인 임시 배열(추가적인 메모리)가 필요.
  
  
• 순차 접근이 아닌 임의 접근이기 때문에 Linked List 정렬에는 비효율적