정렬 알고리즘(Sorting algorithm)

Comparison Sort

  • 데이터들의 상대적 크기 관계를 이용해서 정렬(문자열, 알파벳 등)
  • 최악 시간복잡도가 O(nlogn)보다 좋을 수 없다. (=시간복잡도의 하한이 nlogn이다)
  • 예시 : Selection sort, Bubble sort, Insertion sort, Merge sort, Quick sort, Heap sort

Non-comparison Sort

  • 정렬할 데이터에 대한 사전지식을 이용해서 정렬(적용에 제한)
  • 예시 : Bucket sort, Radix sort

정렬 알고리즘 비교 (참고)

Selection sort click

  • 최소값을 찾아 맨 앞의 요소와 교체하는 방법을 반복하여 정렬하거나
  • 최대값을 찾아 맨 뒤의 요소와 교체하는 방법을 반복하여 정렬한다.
  • // 바깥 for문은 0부터 끝 앞까지 이동
  • // 안쪽 for문은 바깥 for문 index부터 1씩 증가하여 가장 작은 값을 찾아서 스왑
  • 최악, 최선, 평균의 경우 O(n²)
  • 최악 = О(n²) // О(n²) comparisons, О(n) swaps
  • 최선 = О(n²) // О(n²) comparisons, О(n) swaps
  • 평균 = О(n²) // О(n²) comparisons, О(n) swaps


Bubble sort click

  • 그물로 가장 큰 물고기를 몰아넣는다.
  • 앞에서부터 이웃하는 원소의 값을 비교하여 위치를 교환하는 것을 반복한다. 이를 끝까지 수행하면 제일 큰 값이 맨 뒤에 위치하므로 정렬할 개수를 1 줄인 후에 다시 반복한다.
  • // 바깥 for문은 length-1부터 1씩 감소
  • // 안쪽 for문은 0부터 바깥 for문 index까지 1씩 증가하며 앞뒤 값을 스왑
  • 최악, 평균의 경우 O(n²), 최선의 경우 = O(n)
  • 최악 = О(n²) // 역정렬일 경우
  • 최선 = О(n) // 정렬일 경우
  • 평균 = О(n²)


Insertion sort click

  • 점진적으로 정렬 범위를 넓힌다. 새로운 범위에 포함하는 마지막 원소를 앞으로 이동하면서 자신보다 작은 요소를 찾을 때까지 이동하면서 자리를 교환한다.
  • // 바깥 for문은 1부터 끝까지 한칸씩 이동
  • // 안쪽 while문은 바깥 for문 index부터 1씩 감소하며 한칸씩 비교해서 자기자리 찾기
  • 최악, 평균의 경우 = O(n²), 최선의 경우 T(n) = O(n)
  • 최악 = О(n²) // 역정렬인 경우
  • 최선 = O(n) // 정렬인 경우
  • 평균 = О(n²)



병합정렬 / 퀵정렬


공통점 : 분할 정복 알고리즘

차이점 : 퀵소트는 분할 과정이 복잡하고, 머지소트는 병합 과정이 복잡하다


Merge sort click

  • 분할정복법 이용
    • 분할 : 배열을 반으로 계속 나눈다(Divide)
    • 정복 : 합병정렬을 사용하여 두 개의 배열을 정렬한다.(Conquer)
    • 합병 : 두 개의 정렬된 배열을 하나로 합친다(Combine)
  • 데이터를 정렬할 때 추가배열이 필요하다는 단점이 있다.
  • // 시간복잡도 О(n log n)
  • // 공간복잡도 О(n)
  • 최악, 평균, 최선의 경우 = O(nlogn)
  • 최악 = О(nlogn)
  • 최선 = O(nlogn)
  • 평균 = О(nlogn)


Quick sort click

  • 분할정복법 이용
    • 분할 : 배열을 pivot을 기준으로 작은 부분과 큰 부분으로 나눈다. (Partition)
    • 정복 : 각 부분을 순환적으로 정렬한다.
    • 합병 : 할 일이 없다. 이미 분할과 정복 과정에서 정렬이 완료되었기 때문이다.
  • // 최악의 시간복잡도 O(n2)
  • // 평균 시간복잡도 О(n log n)
  • // 공간복잡도 O(log n)
  • 배열의 마지막 수를 기준(pivot)으로 삼는다. 기준보다 작은 수는 왼쪽에 큰 수는 오른쪽에 오도록 재배치한다. 기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬한다.

  • 최악의 경우 = O(n²), 평균, 최선의 경우 = O(nlogn)
  • 최악 = О(n²)
  • 최선 = O(nlogn) (simple partition)
  • 평균 = О(nlogn)
  • 퀵정렬의 성능은 파티션이 얼마나 밸런스있게 나뉘냐에 결정된다.
  • 퀵정렬은 최악의 경우 O(n²)이지만 다른 알고리즘보다 빠르다. 최선, 최악의 경우처럼 실제적으로 일어나기 어려운 극단적인 경우만 아니라면 시간복잡도는 O(nlogn)이 되므로 상당히 빠른 정렬이다.


Heap sort click

  • 추가배열이 필요하지 않다.
  • Binary heap(이진 힙) 자료구조와 Heapify 연산을 이용하여 구현한다.
  • 정렬할 배열을 으로 만든다.
  • 힙에서 최대값(root)을 가장 마지막 값과 바꾼다.
  • 힙의 크기가 1 줄어든 것으로 간주한다. 즉, 가장 마지막 값은 힙의 일부가 아닌 것으로 간주한다.
  • 루트노드에 대해서 HEAPIFY(1)한다.
  • 2~4번을 반복한다.
  • 최악, 최선, 평균 T(n) = O(nlogn)
  • // max-heap생성 o(n)
  • // max-heapify 호출 횟수 o(n)
  • // max-heapify시간복잡도 o(logn)
  • // 총소요시간 o(nlogn)
예를 들어 A = {2,8,6,1,10,15,3,12,11}
 
BUILD-MAX-HEAP(A)
    heap-size[A] <- length[A] // 정렬할 데이터의 개수 (N = 9)
    for i <- [length[A]/2] downto 1 // leaf가 아닌 노드부터 HEAPIFY를 시작한다.
        do MAX-HEAPIFY(A, i)
 
HEAPSORT(A)
    BUILD-MAX-HEAP(A)
    for i <- heap_size downto 2 do // i는 현재 마지막 노드
        exchange A[1<-> A[i] // root와 마지막 노드를 교환한다.
        heap_size <- heap_size - 1
        MAX-HEAPIFY(A, i)
cs


package datastructure.list;


import java.util.LinkedList;


/**

 * TODO LinkedList에서 Array로 변환하기

 */

public class LinkedList_Array {

void swap(int arr[], int i, int j) {

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}


void max_heapify(int arr[], int i, int heapSize){

int leftIndex = 2 i;

int rightIndex = 2 i + 1;

int maxIndex;

if (leftIndex <= heapSize && arr[leftIndex-1] > arr[i-1])

maxIndex = leftIndex;

else

maxIndex = i;

if (rightIndex <= heapSize && arr[rightIndex-1] > arr[maxIndex-1])

maxIndex = rightIndex;

if (maxIndex != i){

swap(arr, i - 1, maxIndex - 1);

max_heapify(arr, maxIndex, heapSize);

}

}


void build_max_heap(int arr[], int arrLength) {

int i;

for (i = arrLength / 2; i > 0; i--)

max_heapify(arr, i, arrLength);

}


void heapSort(int arr[], int arrLength) {

int i;

build_max_heap(arr, arrLength);

for (i = arrLength; i > 1; i--) {

swap(arr, 0, i - 1);

arrLength = arrLength - 1;

max_heapify(arr, 1, arrLength);

}

}


void main(){

int arr[20];

int arrLength = sizeof(arr) / sizeof(int);

int i;

srand((unsigned)time(NULL));


for (i = 0; i < arrLength; i++){

    arr[i] = rand() % 100;

}

puts("[original sequence]");

for (i = 0; i < arrLength; i++){

    printf("%d ", arr[i]);

}

printf("\n");


puts("[after heapsort]");

heapSort(arr, arrLength);

for (i = 0; i < arrLength; i++){

    printf("%d ", arr[i]);

}

printf("\n");

}


}



























Sorting in leanar time(선형시간 알고리즘)



Radix sort click

  • n개의 d자리 정수들
  • 가장 낮은 자리수부터 정렬
  • Stable sort하다. (입력에 동일한 값이 있을 때, 입력에 먼저 나오는 값이 출력에서도 먼저 나온다)

 최악 

 최선 

 Stable

 In-place

 비교횟수

 이동횟수

 O( d*n )

 O( d*n )

 O

 X

 O

 O


RADIX-SORT(A, d) // A는 배열, d는 d자리 형식
    for i <- 1 to d
        do use a stable sort to sort array A on digit i
cs


Java Sorting

Primitive type 정렬하기

Reference type 정렬하기



참고

  • 영리한 프로그래밍을 위한 알고리즘

http://cs.kangwon.ac.kr/~leeck/DS2/DS_09.pdf

http://jwprogramming.tistory.com/247

https://www.youtube.com/watch?v=_MoTnAW6fs8


'Computer Science > 자료구조, 알고리즘' 카테고리의 다른 글

알고리즘 정렬  (0) 2018.10.10
알고리즘 순환(Recursion)  (0) 2018.10.10