알고리즘 정렬 정리

선택 정렬 (Selection Sort)

• 주어진 리스트에서 최소값을 맨 앞으로 옮기며 정렬.
• 내림차순의 경우 최대값을 맨 앞으로 옮김.
• 시간 복잡도 : //( O(n^2) //)

#include <stdio.h>
#include <algorithm>
using namespace std;

int main(){
	int n,min=0;
	int i,j;
	int num[1001];
	scanf("%d", &n);
	for(int i=0;i<n;i++)
		scanf("%d", &num[i]);

	for(i=0;i<n;i++){
		for(j=i;j<n;j++)
			if(num[i]>num[j]) 
				swap(num[i], num[j]);
	} 

	for(int i=0;i<n;i++)
		printf("%d\n", num[i]);

	return 0;
}

Baekjoon 2750 수 정렬하기

 

합병 정렬 (Merge Sort)

• 분할 정복 알고리즘 중 하나
• 재귀를 이용하여 리스트를 각 원소별로 나누고 정렬
• 시간 복잡도 : //( O(n log n) //)

#include <stdio.h>
#include <algorithm>
#define N 1000001
using namespace std;

int sortNum[N];
void mergeSort(int num[], int left, int right);
void merge(int num[], int left, int mid, int right);

int main(){
	int n;
	int num[N];
	scanf("%d", &n);
	for(int i=0;i<n;i++)
		scanf("%d", &num[i]);

	mergeSort(num, 0, n-1);
	for(int i=0;i<n;i++)
		printf("%d\n", num[i]);

	return 0;

}

void mergeSort(int num[], int left, int right){
	if(right <= left) return;
	int mid = (left+right)/2;
	mergeSort(num, left, mid);
	mergeSort(num, mid+1, right);
	merge(num, left, mid, right);
	
}

void merge(int num[], int left, int mid, int right){
	int i=left;
	int j=mid+1;
	int k=left;
	int flag;
	while(i<=mid && j<=right){
		if(num[i] < num[j]){
			sortNum[k++] = num[i++];
			flag=0;
		}
		else{
			sortNum[k++] = num[j++];
			flag=1;
		}
	}
	if(flag){
		for(int q=i;q<mid+1;q++)
			sortNum[k++] = num[q];
	} else {
		for(int q=j;q<=right;q++)
			sortNum[k++] = num[q];
	}

	for(int q=left;q <=right;q++){
		num[q] = sortNum[q];
	}
}

Baekjoon 2751 수 정렬하기2

 

퀵 정렬 (Quick Sort)

• 리스트의 원소 중 피벗(Pivot)을 무작위로 고름.
• 이를 중심으로 왼쪽은 피벗보다 작은 값, 오른쪽은 큰 값으로 정렬.
• 시간 복잡도 : //( O(n log n) //)

#include <stdio.h>
#include <algorithm>
#define N 1000001
using namespace std;

void quickSort(int num[], int left, int right);

int main(){
	int n;
	int num[N];
	scanf("%d", &n);
	for(int i=0;i<n;i++)
		scanf("%d", &num[i]);

	quickSort(num, 0, n);
	for(int i=0;i<n;i++)
		printf("%d\n", num[i]);
}

void quickSort(int num[], int left, int right){
	if(right <= left) return;
	int pivot=num[left];
	int i=left, j=right;
	while(1){
		do{
			i++;
		} while(pivot > num[i] && i<=j);
		do {
			j--;
		} while(pivot < num[j] && i<=j);
		if(i<j) swap(num[i], num[j]);
		else break;
	}
	swap(num[left], num[j]);
	quickSort(num, left, j);
	quickSort(num, j+1, right);

	
}

Baekjoon 2751 수 정렬하기2 (시간 초과로 인해 코드 수정 필요)

 

계수 정렬 (Counting Sort)

• 일반적 상황에서 가장 빠른 정렬 알고리즘
• 하지만 범위가 정해지지않은 경우, 메모리 낭비 유발 가능성 높음
• 시간 복잡도 : //( O(n) //)

#include <stdio.h>

int main(){
	int n, temp;
	int num[10001]={0,};
	scanf("%d", &n);
	for(int i=0;i<n;i++){
		scanf("%d", &temp);
		num[temp]++;
	}

	for(int i=0;i<10001;i++){
		if(num[i]>0){
			for(int j=0;j<num[i];j++)
				printf("%d\n", i);
		}
		else continue;
	}
}

Baekjoon 10989 수 정렬하기3