01. 정렬

📍정렬이란?

레코드(record)를 오름차순 또는 내림차순으로 나열하는 것.

레코드(record) : 필드(field)라는 단위로 구성됨.

- 키(key) 필드로 레코드 간에 구별이 가능함.

 

+) 정렬 알고리즘의 안정성(stability)

동일한 키 값을 갖는 레코드들의 상대적인 위치가 정렬 후에도 바뀌지 않음.

안정하지 않은 정렬의 경우

 

대표적인 정렬 알고리즘

O(n²) : 선택 정렬, 삽입 정렬, 버블 정렬 → 단순하지만 비효율적

O(nlogn) : 합병 정렬, 퀵 정렬, 힙 정렬 → 비교적 복잡하지만 효율적

(오름차순 정렬이라 가정하고 설명합니다)

 

📍 O(n²)

# 선택 정렬

: 정렬된 왼쪽 리스트(초기에는 비어있는 상태)와 정렬되지 않은 오른쪽 리스트를 가정하고, 오른쪽 리스트에서 가장 작은 값을 현재 인덱스에 들어있는 값과 교환.

selection_sort(A, n) :
	for i <- 0 to n-2 do
    		least <- A[i], A[i+1], ..., A[n-1] 중에서 가장 작은 값의 인덱스;
        	A[i]와 A[least] 교환;

- 비교 횟수는 O(n²)이지만 이동 횟수는 3(n-1)로 적은 편이며, 안정성을 만족하지 않음.

 

# 삽입 정렬

: 정렬되어 있는 부분에서 올바른 위치를 찾아 새로운 레코드를 삽입. (=콘서트 스탠딩 입장 줄 서기와 같은 방식)

2번째 레코드부터 시작함

insertion_sort(A, n) :
	for i <- 1 to n-1 do		//i번째 숫자를 삽입하고자 할 때
    		key <- A[i];
        	j <- i-1;		//i번째 숫자 바로 앞의 숫자부터 비교 시작
        	while j>=0 and A[j]>key do
            		A[j+1] <- A[j];		//i번째 숫자보다 큰 것은 한 칸씩 오른쪽으로 이동
                	j <- j+1;
		A[j+1] <- key;

- 비교 횟수와 이동 횟수 모두 O(n²)이지만 안정된 정렬 방법.

- 많은 이동이 필요하므로 레코드가 클 경우 불리하지만, 대부분의 레코드가 정렬되어 있는 경우라면 매우 효율적임.

 

# 버블 정렬

: 인접한 2개의 레코드를 비교해 정렬되어있지 않으면 교환.

뒤에서부터 정렬됨

bubble_sort(A, n) :
	for i <- n-i to 1 do
    		for j <- 0 to j <- i-1 do
            		j와 j+1번째의 값이 크기 순이 아니면 교환

- 비교 횟수와 이동 횟수 모두 O(n²)이며, 레코드의 이동이 과다함.

- 어디까지 정렬되어 있는지 알 수 있는 경우 효율 상승.

 

📍 O(nlogn)

# 합병 정렬

: 전체 리스트를 두 개의 균등한 크기로 반복 분할한 후, 분할된 부분 배열들을 정렬→합병하는 과정을 반복함.

분할 정복 (문제를 2개의 작은 문제들로 분리하고 각각 해결해, 그 결과를 모아 원래의 문제를 해결하는) 기법을 이용

merge_sort(list, left, right) :
	if left<right
    		mid=(left+right)/2;		//중간 위치를 구한 다음
            	merge_sort(list, left, mid);		//앞쪽 부분 배열 정렬을 위한 순환 호출
            	merge_sort(list, mid+1, right);		//뒤쪽 부분 배열 정렬을 위한 순환 호출
            	merge(list, left, mid, right);		//정렬된 두 배열을 통합

- 비교 횟수는 O(logn), 이동 횟수는 O(nlogn)이므로 레코드의 크기가 큰 경우 시간적 낭비 또한 커지지만, 안정된 정렬 방법.

- 데이터의 초기 분산 순서에 영향을 덜 받음.

- 레코드를 연결리스트로 구성해 합병 정렬할 경우, 매우 효율적!

 

# 퀵 정렬

: 피벗을 기준으로 전체 리스트를 두 개의 비균등 리스트로 분할해 각 리스트를 퀵 정렬함.

(분할 정복 기법을 사용했으나, 정복 과정 없이 정렬됨!)

quick_sort(list, left, right) :
	if left<right		//정렬할 범위가 2개 이상의 데이터이면
        	q <- partition(list, left, right);		//피벗 기준으로 리스트를 분할
                quick_sort(list, left, q-1);		//피벗 바로 앞까지 퀵 정렬 순환 호출
                quick_sort(list, q+1, right);		//피벗 바로 뒤부터 퀵 정렬 순환 호출

partition(list, left, right) :
	low <- left; high <- right+1; pivot <- list[left];
    	while(low<high)		//low와 high가 만나기 전까지
    		while(low<=right && list[low]<pivot) do
    			low++;		//앞에서부터 이동하다 list[low]>pivot이면 멈추고
    		while(high>=left && list[high]>pivot) do
    			high--;		//뒤에서부터 이동하다 list[high]<pivot이면 멈춰서
    		if low<high
    			swap(list[low], list[high]);		//둘이 교환
    	swap(list[left], list[high]);		//이후 피벗을 제 위치로 이동
    	return high;

- 비교 횟수는 O(nlogn)이고 이동 횟수는 없으므로, 평균적으로 가장 빠른 정렬 방법.

- 다만 극도로 불균등한 리스트로 분할되는 경우, 비교 횟수가 O(n²)이 됨.

- 중간값을 피벗으로 선택해 불균등 분할을 완화하는 방식 이용.

 

# 힙 정렬

: 정렬할 요소들을 최소 힙(min heap)에 삽입 후 삭제 연산을 통해 힙으로부터 요소를 하나씩 저장함.

+) 힙에서의 삭제 연산

   (1) 루트 노드 삭제.

   (2) 마지막 노드를 루트 노드로 이동.

   (3) 루트에서부터 단말 노드까지의 경로에 있는 노드들을 교환해, 힙의 성질을 만족시킴.

 

- n번의 삭제 연산이므로 O(nlogn).