[Algorithm] 기초 정렬 문제

백준 사이트

초심자라면 단계별로 풀어보기, 알고리즘 분류에서 문제 풀어보는 게 좋다.

그 중에서도 단계별로 풀어보기에서 정렬해보기부터 시작하면 좋다.

 

기본적으로 1초에 1억 번 정도 연산한다고 생각하고 문제 풀면 됨.

 

1. 수 정렬하기(2750)

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

2750번: 수 정렬하기

데이터의 개수가 최대 1,000개. N^2 = 1,000,000개

N^2 알고리즘으로 풀어도 크게 문제 없이 해결 가능하다.

#include <iostream>
using namespace std;

void Print(int *data, int N){
    for(int i=0;i<N;i++)
        cout << data[i] << endl;
}

void Selection_Sort(int *data, int N){
    int tmp, min, idx = 0;
    for(int i=0;i<N;i++){
        min = 1001;
        for(int j=i;j<N;j++){
            if(min > data[j]){
                min = data[j];
                idx = j;
            }
        }

        tmp = data[i];
        data[i] = data[idx];
        data[idx] = tmp;
    }
}

void Bubble_Sort(int *data, int N){
    int tmp = 0;
    for(int i=0;i<N;i++){
        for(int j=0;j<N-1;j++){
            if(data[j] > data[j+1]){
                tmp = data[j];
                data[j] = data[j+1];
                data[j+1] = tmp;
            }
        }
    }
}

int main(void){
    int N;
    int data[1000];

    cin >> N;
    for(int i=0;i<N;i++)
        cin >> data[i];

    Selection_Sort(data, N);
    Bubble_Sort(data, N);
    //Insert_Sort(data, N);
    //Quick_Sort(data, N);
    Print(data, N);
    return 0;
}

 

2. 세수정렬

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

2752번: 세수정렬

#include <iostream>
using namespace std;
#define N 3

int arr[3]={0,};

void Input(){
    for(int i=0;i<N;i++)
        cin >> arr[i];
}

void Output(){
    for(int i=0;i<N;i++)
        cout << arr[i] << " ";
}

void Insertion_Sort(){
    int j, tmp;
    for(int i=0;i<N-1;i++){
        j = i;
        while(arr[j] > arr[j+1]){
            tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
            j--;
        }
    }
}

int main(void){

    Input();
    //Selection_Sort();
    Insertion_Sort();
    Output();

    return 0;
}

 

3. 수 정렬하기 2

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

2751번: 수 정렬하기 2

#include <iostream>
using namespace std;

int N;
int arr[1000000+10];

void Input(){
    cin >> N;
    for(int i=0;i<N;i++)
        cin >> arr[i];
}

void Output(){
    for(int i=0;i<N;i++)
        cout << arr[i] << "\n";
}

void Quick_Sort(int start, int end){
    
    if(start >= end)
        return;

    int mid = start;
    int i = start+1;
    int j = end;
    int tmp;

    while(i <= j){
        // 오른쪽으로 가면서 pivot값보다 큰 값 찾기
        while(arr[mid] >= arr[i]){
            i++;
        }

        // 왼쪽으로 가면서 pivot값보다 작은 값 찾기
        while(arr[mid] <= arr[j] && start < j){
            j--;
        }

        // 엇갈렸으면 pivot 값과 작은 값 변경
        if(i > j){
            tmp = arr[j];
            arr[j] = arr[mid];
            arr[mid] = tmp;
        }
        // 엇갈리지 않았으면 두 값 변경
        else{
            tmp = arr[j];
            arr[j] = arr[i];
            arr[i] = arr[j];
        }
    }

    // start, end 다시 조정해 재귀
    Quick_Sort(start, j-1);
    Quick_Sort(j+1, end);
}

int main(void){
    Input();
    Quick_Sort(0, N-1);
    Output();
}