정렬
[알고리즘] 시간 제한과 시간 복잡도
코딩 테스트에서 문제의 제한 시간은 보통 1~5초 정도이다.일반적인 CPU 기반의 PC나 채점용 컴퓨터에서 1초에 실행할 수 있는 최대 연산 횟수는 <span style="color:- 따라서 문제를 풀 때 먼저 시간 복
velog.io
선택 정렬
선택 정렬이란 정렬 해야하는 값들 중에서 가장 작은수를 선택하여 맨 앞으로 보내는 방법이다.
예를 들어 3 2 4 6 8 1 5 가 있다고 하자. 그렇다면 여기서 가장 작은 수는 1 이므로 1을 맨 앞으로 보낸다.
가장 앞에 있는 1은 정렬이 되었으므로 이제 두번째 자리부터 가장 작은 수를 찾는다.
3 2 4 6 8 1 5
1 2 4 6 8 3 5
1 2 4 6 8 3 5
다음으로 가장 작은 수는 2이다. 가장 작은 수인 2가 맨 앞에 있으므로 수열값은 변화하지 않는다.
이제 2번째 자리 까지 가장 작은 수를 찾았으므로 3번째 자리 부터 끝까지 가장 작은 수를 찾아 세번째 자리에 넣어준다.
이렇게 한번씩 반복할때 마다 가장 작은 수를 가장 앞에 위치 하게 하는 방식이 선택 정렬이다.
처음 반복문을 수행할때는 첫번째 자리 부터 끝까지 돌고, 그중 가장 작은 수를 찾아 첫번째 자리와 바꾼다.
두번째 반복문을 수행할때는 두번째 자리부터 끝까지 돌고, 그중 가장 작은 수를 찾아 두번째 자리와 바꾼다.
세번째 반복문을 수행할때는 세번째 자리부터 끝까지 돌고, 그중 가장 작은 수를 찾아 세번째 자리와 바꾼다.
이런식으로 계속 반복하여 모든 수를 정렬한다.
#include <iostream>
using namespace std;
int main(){
int idx; // 최솟값을 가진 원소의 인덱스
int arr[10]={2,6,3,8,4,5,9,1,10,7};
for(int i=0;i<9;i++){
int min=999;
for(int j=i;j<10;j++){
// 최솟값 찾기
if(min>arr[j]){
min=arr[j];
idx=j;
}
}
// 최솟값을 맨 앞의 원소의 값과 바꾸기
int temp=arr[i];
arr[i]=arr[idx];
arr[idx]=temp;
}
for(int i=0;i<10;i++){
cout<<arr[i]<<" ";
}
}
선택 정렬의 시간 복잡도 : o(N^2)
선택 정렬로 N개의 수를 정렬하기 위해서는 몇 번의 반복문이 수행되어야 할까?
선택 정렬은 한번 반복문이 수행 될때 마다 한개씩 정렬이 일어나며, 그 값을 제외하고 맨 마지막 값 까지 반복문을 수행한다.
즉, n+(n-1)+(n-2)+ ... +2+1 = n(n-1)/2 번의 수행 시간이 필요하다. (이때 n^2에 비해 상수값들은 무의미 하므로 무시한다)
예를 들어 10개의 수를 정렬하기 위해서는 대략 100번의 계산을 하고, 10,000개라면 약 1억번의 계산을 해야하는 셈이다.
지수함수의 특성 처럼 n의 값(x값)이 증가할때 계산값인 y값의 증가 속도는 기하급수적이다.
그렇다면 과연 이런 정렬 방법이 효율적이라고 할 수 있을지 고민해보자.
버블 정렬
#include <stdio.h>
int length=10;
int data[10]={1,4,2,3,5,10,9,8,6,7};
void bubble_sort(int *data,int size){
for(int i=0;i<size-1;i++){
for(int j=0;j<size-1-i;j++){
if(data[j]>data[j+1]){
int temp=data[j];
data[j]=data[j+1];
data[j+1]=temp;
}
}
}
}
void show(){
for(int i=0;i<length;i++){
printf("%d ",data[i]);
}
}
int main() {
bubble_sort(data,length);
show();
return 0;
}삽입 정렬
#include <iostream>
using namespace std;
int main() {
int arr[10]={1,10,5,8,7,6,4,3,2,9};
for(int i=1;i<10;i++){
for(int j=i-1;j>=0;j--){
if(arr[j]>arr[j+1]) {
int temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
else break;
}
}
for(int i=0;i<10;i++){
cout<<arr[i]<<' ';
}
return 0;
}퀵 정렬
피벗값을 이용하여 큰 값과 작은값을 반복적으로 바꿔준다.
분할 정복
#include <stdio.h>
int number=10;
int data[10]={1,10,5,8,7,6,4,3,2,9};
void quickSort(int *data,int start,int end){
if(start>=end){ // 원소가 1개인 경우 그대로 두기
return ;
}
int key=start; // 키는 첫번째 원소
int i=start+1;
int j=end;
int temp;
while(i<=j){ // 엇갈릴때 까지 반복
while(i<=end && data[i]<=data[key]){ // 키 값보다 큰 값을 만날때 까지
i++;
}
while(j>start && data[j]>=data[key] ){ // 키 값보다 작은 값을 만날때 까지
j--;
}
if(i>j){ // 엇갈린 경우 키 값과 교체
temp=data[j];
data[j]=data[key];
data[key]=temp;
}
else{ // 엇갈리지 않았다면 i와 j를 교체
temp=data[i];
data[i]=data[j];
data[j]=temp;
}
}
quickSort(data,start,j-1);
quickSort(data,j+1,end);
}
void show(){
for(int i=0;i<number;i++){
printf("%d ",data[i]);
}
}
int main() {
quickSort(data,0,number-1);
show();
return 0;
}병합 정렬
#include <iostream>
using namespace std;
const int number = 8;
int sorted[number];
void merge(int arr[], int m, int middle, int n) {
int i = m;
int j = middle + 1;
int k = m;
while (i <= middle && j <= n) {
if (arr[i] <= arr[j]) {
sorted[k] = arr[i];
i++;
} else {
sorted[k] = arr[j];
j++;
}
k++;
}
while (i <= middle) {
sorted[k] = arr[i];
i++;
k++;
}
while (j <= n) {
sorted[k] = arr[j];
j++;
k++;
}
for (int t = m; t <= n; t++) {
arr[t] = sorted[t];
}
}
void mergeSort(int arr[], int m, int n) {
if (m < n) {
int middle = (m + n) / 2;
mergeSort(arr, m, middle);
mergeSort(arr, middle + 1, n);
merge(arr, m, middle, n);
}
}
int main() {
int array[number] = {2,4,3,6,5,1,7,8};
mergeSort(array, 0, number - 1);
for (int i = 0; i < number; i++) {
cout << array[i] << " ";
}
return 0;
}