백준 2751 Merge Sort, QuickSort, HeapSort

www.acmicpc.net/problem/2751

#include <iostream>
using namespace std;

int list[1000000];

void merge(int arr[], int left, int middle, int right){
    int i, j, k, l;
    i = left;
    j = middle +1;
    k = left;
    // 배열 합병
    while(i <= middle && j <= right){
        if(arr[i] <= arr[j])
            list[k++] = arr[i++];
        else
            list[k++] = arr[j++];
    }
    // 남은 값 복사
    if(i > middle){
        for(l = j; l <= right; l++)
            list[k++] = arr[l];
    }
    else {
        for(l = i; l <= middle; l++)
            list[k++] = arr[l];
    }
    // 인자로 온 배열값 복사
    for(l = left; l <= right; l++)
        arr[l] = list[l];
}

void mergeSort(int arr[],int left,int right){
    int middle;
    if(left < right){
        middle = (left + right) / 2;

        mergeSort(arr, left, middle);
        mergeSort(arr, middle + 1, right);

        merge(arr, left, middle, right);
    }
}

int main(void){
	int N;
	cin >> N;
	int arr[N];
	
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	
	mergeSort(arr, 0, N-1);
	
	for(int i = 0; i < N; i++)
		cout << arr[i] << '\n';
		
	return 0;
}

 

 

 

#include <iostream>
#include <algorithm>
using namespace std;
int n, arr[1000000];

void QuickSort(int i, int j){
    if(i >= j)
        return;
    int pivot = arr[(i+j)/2];
    int left = i;
    int right = j;

    while(left<=right){
        while(arr[left] < pivot)
            left++;
        while(arr[right] > pivot)
            right++;
        if(left >= right){
            swap(arr[left], arr[right]);
            left++; right--;
        }
    }
    QuickSort(i, right);
    QuickSort(left, j);
}
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }
    QuickSort(0, n-1);
    for(int i = 0; i < n; i++){
        printf("%d\n", arr[i]);
    }
}

- 퀵소트의 경우 다른 사람들도 시간초과가 뜬다고 한다. 개념만 알고 가는게 좋을듯?

---

#include <iostream>
using namespace std;
//힙정렬
int n, heap[10000001];

void MakeHeap(int i) {
// 부모 > 자식 의 구조로 만드는 과정
// i가 부모이고 cur(현재 가리키는 인덱스)은 i의 왼 자식
// 왼쪽 오른쪽을 비교한 뒤 더 큰걸 선택
// 부모와 제일 큰 자식을 비교
// 만약 부모가 교체되고 cur <= n/2 현재 가리키는 인덱스가 말단이 아니면 재귀
// 재귀를 하는 이유는 바뀐 노드랑 형제간 비교를 하기 위해
	int cur = 2 * i;

	if(cur < n && heap[cur] < heap[cur+1]) cur++;

	if(heap[i] < heap[cur]) {
		swap(heap[i],heap[cur]);
		if(cur <= n/2) MakeHeap(cur);
	}
}

void HeapSort(int i) {
// cur가 말단을 가리키는게 아니라면 while문 시작
// 루트~자식이 있는 노드까지 계속 반복
// 한번 과정을 거치면 i(말단)은 제일 큰 값이 되고 그 다음으로 큰게 루트가 된다
// 그러니 다음 과정에서 루트를 i-1(for문에서 조정함)과 바꾸면 제일 큰수가 뒤로 가게 되는 구조
	swap(heap[1],heap[i]);

	int root = 1;
	int cur = 2;

	while(cur/2<i) {
		cur = 2*root;
		if(cur < i-1 && heap[cur] < heap[cur+1])
            cur++;
		if(cur < i && heap[root] < heap[cur])
			swap(heap[root],heap[cur]);

		root = cur;
	}
}

int main() {
	scanf("%d",&n);
	for(int i = 1; i <= n; i++)
		scanf("%d",&heap[i]);
	
	for(int i = n/2; i > 0; i--) // 최초 heap 생성
		MakeHeap(i);
	for(int i = n; i > 0; i--) // heap 정렬
		HeapSort(i);

	for(int j = 1; j <= n; j++) // 출력
		printf("%d\n",heap[j]);
}

- 자료구조 강의를 들어둔게 도움이 되었다

- MakeHeap의 경우 힙의 구조( 부모 > 자식 )의 경우를 만드는데 사용

- HeapSort의 경우 이전 과정에서 부모가 제일 큰 수가 되는걸 이용, [ 루트(제일 큼)를 말단으로 보내고 남은 애들중 제일 큰 수를 루트로 ] 하는 작업을 한다.

  (한마디로 작은걸 앞으로가 아니라 큰걸 맨 뒤로 보내는 역할을 하는 것이다)

이해를 하기 위해 발버둥친 노트 (왼쪽 위 > 오른쪽 > 왼쪽 아래 로 읽으면 편하다)