C언어 정렬 shell, quick, heap sort 코드 구현, 정리

정렬 알고리즘에는 다양한 방법들이 있는데 이에 대해 알아보려고 한다.
기초적인 알고리즘으로 삽입정렬, 선택정렬, 버블정렬, 퀵정렬, 힙정렬, 합병정렬 등이 있으며
단순한 방법부터 알아보겠다.

단순한 방법

선택정렬 selection sort

구현방법

concept: n개의 원소를 가진 배열 list[]가 있다고 가정하자. 가장 작은 값부터 순차적으로 앞쪽으로 보낼 것이다.

반복문으로 배열을 순환하며 가장 작은 값을 꺼내 list[0] 값과 교환한다.
다시 정렬되지 않은 나머지 배열을 순환하며 그 중 최소값을 꺼내 list[1] 과 교환한다.
이를 반복하며 n-1번 반복하면 정렬이 완료된다.

삽입정렬 insertion sort

구현 방법

concept: 원소 하나씩 순회하며 값을 비교하며 앞쪽으로 보내는 방식이다.

마찬가지로 n개의 원소를 가진 배열을 가정한다. 비교할 원소를 key라 한다면 key 값을 배열의 인덱스를 1씩 증가시키며 바꿀 것이다. 우선 list[k] 값이 key 값이라면 이를 list[k-1]과 비교한다. key 값이 더 작다면 list[k-1] 값을 list[k]에 넣고 key 값을 list[k-2]와 비교할 것이다. 앞으로 나아가며 비교하다가 key값이 더 작지 않은 상황이 올 것이다. 이때 key 값을 빈 자리에 넣는 것이다.

void insertion_sort(int list[], int n){
	int i, key;
	for (i = 1; i<n; i++) {
		int j = i-1;
		key = list[i];
		while(key<list[j] && j>=0){
			list[j+1] = list[j];
			j--;
		}
		list[j+1] = key;
	}
}

 

버블 정렬 bubble sort

구현방법

앞서 소개한 정렬이 가장 작은 값부터 차례대로 정렬했다면 이번에는 큰 값부터 정렬하는 방식이다.

concept: 처음 두 값을 비교하고 작은 값이 앞으로 오도록 교환한다.(뒤의 값이 더 크다면 유지) 그 다음 2, 3번 값을 비교하고 마찬가지로 작은 값이 앞으로 오도록 교환한다. n개의 원소에 대해 n-1 번 반복한다면 마지막 값에는 가장 큰 값이 들어갈 것이다. 정렬된 값을 제외하고 이를 반복한다.

처음에는 인덱스 0부터 n-1 까지 앞뒤 값을 비교하면서 교체한다.
다음 반복에서는 인덱스 0부터 n-2까지 비교하며 교체한다.
이를 반복하다 인덱스 0과 1의 값을 비교하고 교체한 후 정렬을 마친다.

---

다음으로는 조금 더 복잡하지만 효율적인 방법을 알아볼 것이다.

효율적인 방법

shell sort

삽입 연산의 개선 버전이라 생각할 수 있다.

구현방법

concept: 배열을 일정 간격으로 나누고 각 부분(segment)들에 대해 삽입 정렬을 실시한다. 실시한 후 간격을 반으로 줄여나가며 실시한다. 간격이 1이 되었을 때 정렬을 종료한다.

우선 세그먼트 하나에 대한 정렬을 하는 함수를 정의한다.
일정한 간격인 gap이 선언되어 있다. gap이 5라면 key를 list[5]라고 하고
key가 list[0]보다 작으면 list[5]에 list[0]을 넣는다. 

 

•  
• 반복문 (첫 번째 for loop):
  • i는 first + gap부터 시작하여 last까지 gap씩 증가합니다. 즉, 간격만큼 건너뛰면서 배열을 순차적으로 확인합니다.
  • 이 반복문은 gap 간격으로 요소들을 탐색하고, 해당 요소를 삽입할 위치를 찾습니다.
• c
  코드 복사
  for (i = first + gap; i <= last; i = i + gap)
• key 선택:
  • i번째 요소를 key에 저장합니다. 이 값은 현재 삽입할 값이 됩니다.
• c
  코드 복사
  key = list[i];
• 두 번째 반복문 (삽입 위치 찾기):
  • key보다 큰 값을 왼쪽에서 찾아서 한 칸씩 오른쪽으로 밀어냅니다.
  • j는 i - gap부터 시작하여, key보다 큰 값을 찾아 j = j - gap을 이용해 gap만큼 건너뛰면서 진행됩니다.
  • 만약 key보다 큰 값이 있으면 그 값을 오른쪽으로 밀어냅니다. 이 과정은 삽입 정렬에서 key의 위치를 찾아가는 과정과 유사합니다.
• c
  코드 복사
  for (j = i - gap; j >= first && key < list[j]; j = j - gap) list[j + gap] = list[j];
• key 삽입:
  • key를 j + gap 위치에 삽입합니다. 즉, key보다 큰 모든 값들은 오른쪽으로 밀리고, key는 빈 공간에 적절히 삽입됩니다.
• c
  코드 복사
  list[j + gap] = key;

 

퀵정렬 quick sort

구현방법 

concept: 퀵정렬은 교환 정렬의 개선 버전이라 생각할 수 있다. 배열에서 기준 값(pivot)을 잡고 피봇보다 작은 값은 왼쪽, 큰 값은 오른쪽에 넣는다. 그리고 왼쪽, 오른쪽의 나머지 값에서도 각각 똑같이 진행하면 정렬할 수 있다.

우선 배열에서 가장 왼쪽 값을 피봇 값으로 잡는다. 중앙값을 피봇으로 잡으면 좋지만 편의상 왼쪽 값을 잡은 것일뿐 어떤 값도 상관은 없다. 그리고 피봇을 제외한 첫 번째 값을 low, 마지막 값을 high 로 칭한다. 
low에서 인덱스를 증가시키며 피봇값보다 작은지 확인한다. 만약 큰 값이라면 멈추고 high 인덱스 값을 감소시키며 피봇과 비교한다. high 값이 피봇보다 작다면 low 값과 high 값을 서로 교환해준다. 
차차 진행하다가 마지막엔 low 인덱스가 high 인덱스보다 커지는 순간이 생길 것이다. 이때 반복을 멈추고 high 인덱스에 있는 값과 피봇이 위치한 list[0]을 바꿔 피봇이 중앙에 위치하도록 한다.

힙정렬 heap sort

구현방법

Max heap에 대해 설명할텐데 max heap은 부모 노드의 값이 자식 노드의 값 이상인 완전 이진 트리이다.
이때 완전 이진 트리는 왼쪽부터 값이 완벽하게 채워진 이진트리이다. 

힙정렬은 트리를 만드는 삽입과 트리에서 값을 제거하며 정렬된 배열을 만드는 삭제로 이루어져있다.

삽입의 컨셉은 우선 값을 트리의 말단에 넣고  부모와 비교하면서 값이 크다면 부모 노드와 교환하며 올라가는 방식이다. 

삭제의 컨셉은 root 노드를 삭제하고 말단 노드를 root 노드에 올린다. 그리고 자식 노드를 root에 있는 값과 비교하면서 max heap을 성질을 만족할때까지 노드를 교체하며 내려간다. 완료가 되면 기존 삭제된 노드의 값을 반환할 것이다.

main 함수에서 우선 삽입함수를 이용해 하나하나씩 트리를 만들어줄 것이다. 이후삭제함수를 이용해 반환된 값을 배열의 끝부터 넣어줄 것인데, 이렇게 한다면 오름차순 정렬된 배열이 만들어질 것이다.