4주차 - 정렬과 탐색(백준 2750번) 합병 정렬 & 퀵 정렬

백준 2750번 문제를 합병 정렬과 퀵 정렬로 각각 풀어보자.

 * 재귀 알고리즘: 큰 문제를 작은 문제로 쪼개고 작은 문제의 해답을 return하면서 큰 문제의 답에 접근하는 알고리즘

백준 2750번: 수 정렬하기

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

1. 합병 정렬

: 리스트를 분할하여 정렬하고 합병

<합병 정렬 C++ 코드>

// 합병 정렬 알고리즘 코드
void merge(int list[], int left, int mid, int right) {
	int i, j, k, l; 
    i = left; j = mid+1; k = left; 
    while(i<=mid && j<=right) { 
    	if (list[i] <= list[j]) 
        	sorted[k++] = list[i++]; 
        else sorted[k++] = list[j++]; 
    }
    if (i>mid) for(l = j; l <= right; l++) sorted[k++] = list[l]; 
    else for(l = i; l <= mid; l++) sorted[k++] = list[l]; 
    
    for(l = left; l <= right; l++) list[l] = sorted[l]; 
}

void merge_sort(int list[], int left, int right){
	int mid;
    if(left < right) { 
    	mid = (left + right) / 2; 
        //분할 
        merge_sort(list, left, mid); 
        merge_sort(list, mid+1,right); 
        
        //병합하며 정렬 
        merge(list, left, mid,right); 
    }
}

---

<백준 2750번 - 합병 정렬 c++ 코드>

// 백준 2750번 합병 정렬 C++ 코드
#include <iostream> 
#define MAX_SIZE 1001 
using namespace std; 

int sorted[MAX_SIZE]; 

void merge(int list[], int left, int mid, int right) {
	int i, j, k, l; 
    i = left; j = mid+1; k = left; 
    while(i<=mid && j<=right) { 
    	if (list[i] <= list[j]) 
        	sorted[k++] = list[i++]; 
        else sorted[k++] = list[j++]; 
    }
    if (i>mid) for(l = j; l <= right; l++) sorted[k++] = list[l]; 
    else for(l = i; l <= mid; l++) sorted[k++] = list[l]; 
    
    for(l = left; l <= right; l++) list[l] = sorted[l]; 
}

void merge_sort(int list[], int left, int right){
	int mid;
    if(left < right) { 
    	mid = (left + right) / 2; 
        //분할 
        merge_sort(list, left, mid); 
        merge_sort(list, mid+1,right); 
        
        //병합하며 정렬 
        merge(list, left, mid,right); 
    }
}

int main() { 
	int n; 
	cin >> n; 
	int array[n];
	
	for(int i = 0; i < n; i++){
		cin >> array[i];
	}
    
    merge_sort(array, 0, n-1); 
    
    for(int i = 0; i < n; i++) { 
    	cout << sorted[i] << endl; 
    }
    
    return 0; 
}

틀렸다! 어째서.. 백준 입력 예시와 몇가지 예시를 넣었을 때는 문제없이 출력 되었는데! 이유를 정확하게 모르겠다..

어째서..

 

 

---

1. 퀵 정렬

    : 피봇을 기준으로 앞에 작은 값, 뒤에 큰 값을 정렬한다.

<퀵정렬 알고리즘 코드>

// 퀵정렬 알고리즘 코드
void quick_sort(int *data, int start, int end){ 
	if(start >= end){ 
	// 원소가 1개인 경우
 		return; 
	} 
	int pivot = start; 
	int i = pivot + 1;// 왼쪽 출발 지점 
	int j = end; // 오른쪽 출발 지점 
	int temp; 
	  
	while(i <= j){ // 포인터가 엇갈릴때까지 반복
		while(i <= end && data[i] <= data[pivot]){ 
	   		i++; 
		}
	    while(j > start && data[j] >= data[pivot]){
		 	j--; 
		} 
		if(i > j){ // 엇갈림 
			temp = data[j]; 
			data[j] = data[pivot]; 
			data[pivot] = temp; 
		} 
		else{ // i번째와 j번째를 스왑 
			temp = data[i]; 
			data[i] = data[j]; 
			data[j] = temp; 
		} 
	} 
	
	// 분할 계산 
	quick_sort(data, start, j - 1); 
	quick_sort(data, j + 1, end); 
}

---

<백준 2750번 - 퀵 정렬 c++ 코드>

// 백준 2750번 퀵정렬 C++ 코드
#include <stdio.h> 
#include <iostream> 
#define MAX_SIZE 1001
using namespace std; 

void quick_sort(int *data, int start, int end){ 
	if(start >= end){ 
	// 원소가 1개인 경우
 		return; 
	} 
	int pivot = start; 
	int i = pivot + 1; // 왼쪽 출발 지점 
	int j = end; // 오른쪽 출발 지점 
	int temp; 
	  
	while(i <= j){ // 포인터가 엇갈릴때까지 반복
		while(i <= end && data[i] <= data[pivot]){ 
	   		i++; 
		}
	    while(j > start && data[j] >= data[pivot]){
		 	j--; 
		} 
		if(i > j){ // 엇갈림 
			temp = data[j]; 
			data[j] = data[pivot]; 
			data[pivot] = temp; 
		} 
		else{ // i번째와 j번째를 스왑 
			temp = data[i]; 
			data[i] = data[j]; 
			data[j] = temp; 
		} 
	} 
	
	// 분할 계산 
	quick_sort(data, start, j - 1); 
	quick_sort(data, j + 1, end); 
} 
int main(){ 
	int n;
	cin >> n; 
	int array[n];	
	for(int i = 0; i < n; i++){
		cin >> array[i];
	}  
	quick_sort(array, 0, n-1);
	
	// 결과 확인 
	for(int i = 0; i < n; i++) { 
    	cout << array[i] << endl; 
    }    
    return 0; 
}

성공했다!

퀵정렬 코드는 오류 없이 한번에 성공했다! 이 말은.. 앞에 합병 정렬 코드에서 main 부분에는 문제가 없다는 뜻일 텐데.. 오류를 더 찾아보려고 한다. 어쩌면 새로 할당한 배열인 sorted[]를 설정하면서 문제가 생긴게 아닐까? 라는 생각도 든다.