정렬(Sort)

목차

1. 선택정렬

2. 거품정렬

3. 삽입정렬

4. 퀵 정렬

5. 병합 정렬

6. 힙 정렬

안정 정렬과 불안정 정렬

 1. 안정 정렬: 동일한 값에 대해 기존의 순서가 유지되는 정렬 방식

  ex) caBb -> aBbc (여기서 B==b 같은 값이다.)

 

 2. 불안정 정렬: 동일한 값에 대해 기존의 순서가 유지되지 않는 정렬 방식

  ex) caBb -> abBc (여기서 B==b 같은 값이다.)

 

선택정렬 - 불안정 정렬

1. 특징

 가. 버블 정렬과 유사한 알고리즘이다

 나. 해당 자리를 선택하고 그 자리에 오는 값을 찾는 알고리즘이다. 

  1) 주어진 배열 중에 최소값을 찾는다. 

  2) 그 값을 맨 앞에 위치한 값과 교체한다. 

  3) 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. 

 

 다. 구현이 매우 간단하며, 소스코드가 직관적이다. 

 라. 다른 메모리 공간을 필요로 하지 않는다. 

 마. 많은 교환이 일어나는 자료 알고리즘(버블, 선택, 삽입) 중 비교적 효율적이다. 

2. 복잡도

 가. 시간 복잡도: O(n^2)

 나. 공간 복잡도: O(n)

3. 예시 

- 선택정렬 -

거품 정렬 - 안정 정렬

1. 특징

 가. 선택정렬과 유사하다.

 나. 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면, 자리를 교환하며 정렬한다.

 다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동을 한다. (오름차순 정렬 경우) 

 라. 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 정렬을 수행한다. 

 마. 구현이 매우 간단하며, 소스코드가 직관적인다. 

 바. 다른 메모리 공간을 필요로 하지 않는다. 

2. 복잡도

 가. 시간 복잡도: O(n^2)

 나. 공간 복잡도: O(n)

3. 예시 

- 거품 정렬 -

삽입 정렬 - 안정 정렬

1. 특징

 가. 2번째 원소부터 시작한다. 

 나. 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후 원소를 뒤로 옮기고, 지정된 자리에 자료를 삽입한다. 

  1) 두번째 원소 index 값을 temp 변수의 저장 

  2) temp 와 이전에 있는 원소들과 비교를 한 후 삽입

  3) 1),2) 계속적으로 반복

 

 다. 최선의 경우 O(n)이라는 엄청나게 빠른 효율성을 가지고 있다. 

 라. 구현이 매우 간단하며, 코드가 직관적이다. 

 마. 다른 메모리 공간을 필요로 하지 않는다. 

 바. 거품, 선택정렬보다 상대적으로 빠르다. 

2. 복잡도

 가. 시간 복잡도: O(n^2)

 나. 공간 복잡도: O(n)

3. 예시 

- 삽입 정렬 -

퀵 정렬 - 불안정 정렬 

1. 특징

 가. 분할과 동시에 정렬을 수행하는 알고리즘이다. 

 나. 피벗(pivot)을 하나 설정하여 기준을 만들고, 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기는 방식으로 정렬을 진행한다. 

 다. 피벗은 전체 배열 값 중 중간값이나, 랜덤값으로 설정한다. 

 라. 이를 계속 반복하여 분할된 배열의 크기가 1이 되면, 배열이 모두 정렬 된 것이다. 

 마. 최악의 경우 합병 정렬보다는 느리지만, 발생할 수 있는 가능성이 드물고, 일반적으로 합병정렬보다 20% 빠르다고한다.   

2. 복잡도 

 가. 시간 복잡도: O(n log n)

 나. 공간 복잡도: O(n)

3. 예시 

- 퀵 정렬 -

 

병합정렬 - 안정 정렬

1. 특징 

 가. 큰 문제를 작은 문제 단위로 쪼개면서 해결해 나가는 분할 정복 방법을 통해 구현된 알고리즘이다 

 나. 배열 내에 요소를 쪼갠 후 다시 합병시키면서 정렬해 나간다. 

  1) 현재 배열을 반으로 쪼갠다. 

  2) 배열의 시작위치와 종료위치를 입력받아 둘을 더해 2를 나눈 뒤 그 위치를 기준으로 계속 나눈다. 

  3) 이를 쪼갠 배열의 크기라 0이거 1일때까지 계속 반복한다. 

 

 다. 퀵 정렬과 병합정렬의 차이점 

  1) 퀵 정렬: 피벗을 통해 정렬 -> 영역을 쪼갬

  2) 영역을 쪼갬 -> 병합을 하면서 정렬 

 

 라. 병합정렬은 순차적인 비교를 통해 정렬을 진행하므로, LinkedList 사용이 효과적이다. 

   * LinkedList: 삽입, 삭제, 연산은 유동적, 검색은 비 효율적

 

 마. 퀵 정렬과 마찬가지로 빠르다. 

2. 복잡도

 가. 시간 복잡도: O(n log n)

 나. 공간 복잡도: O(2n)

3. 예시 

- 병합 정렬 -

힙 정렬 - 불안정 정렬

1. 특징

 가. 완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로 한 정렬방식이다. 

 * 완전 이진 트리: 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리

 

 나. 최소 힙 or 최대 힙을 구성해야한다. (여기서는 최대 힙을 예시로 들겠습니다.)

  1) 현재 힙 루트는 가장 큰 값이 존재 

  2) 루트의 값을 마지막 요소와 바꾼후 다시 최대 힙을 구성할 때까지 부모노드와 자식노드를 swap 하며 재귀를 진행

  3) 힙의 사이즈가 1보다 크면 계속 1), 2) 과정을 반복

  

 다. 가장 크거나 가장 작은 값을 구할 때 유용하다. 

2. 복잡도

 가. 시간 복잡도: O(n log n)

 나. 공간 복잡도: O(n)

3. 예시 

- 힙 정렬 -

< 참고자료 >

 

[도서] 자료구조  - 정광식 지음-

https://intelligentjava.wordpress.com/2014/07/05/sorting-algorithms/

https://www.globalsoftwaresupport.com/sorting-algorithms-fundamentals/

 

<Data structures> chapter 8,  정렬(Sort) end