(1) [C++] 백준 No.2751 : 수 정렬하기 2

문제

풀이

자세한 풀이 : 

 

# C++(방법1 : Quick Sort 직접 구현 - lomuto partition 알고리즘 사용)

#include <iostream>

using namespace std;

int a[1000000];

void swap(int &x, int &y) 
{
    int z = x;
    x = y;
    y = z;
}

int choosePivot(int low, int high) 
{
    return low + (high-low)/2; // 중간 index 반환
}

/* i와 j가 모두 증가하는 Lomuto Partition방식의 구현으로 swap을 진행하고 분할기준점을 반환함*/
int partition(int low, int high) 
{
    int pivotIndex = choosePivot(low, high); // 피봇을 레코드에서 그냥 중앙에 위치한 값으로 지정해 줬는데 이 함수를 수정하면 내가 원하는 방식대로 지정 가능
    int pivotValue = a[pivotIndex];
    
    swap(a[pivotIndex], a[high]);
    
    int storeIndex = low;                    // 블로그에 필기해둔 거에서 i의 역할
    
    for (int i=low; i<high; i++)             // 블로그에 필기해둔 거에서 j의 역할
    {
        if (a[i] < pivotValue) 
        {
            swap(a[i], a[storeIndex]);
            storeIndex += 1;
        }
    }
    
    swap(a[storeIndex], a[high]);            // 이때 피봇이 옮겨진 자리가 정렬이 되어 고정된 자리.
    
    return storeIndex;                       // 피봇이 옮겨진 자리의 Index값을 반환함
}

void quicksort(int low, int high) 
{
    if (low < high) 
    {
        int pivot = partition(low, high);
        quicksort(low, pivot-1);            // 피봇이 옮겨진 자리를 기준으로 왼쪽 정렬
        quicksort( pivot+1, high);          // 피봇이 옮겨진 자리를 기준으로 오른쪽 정렬
    }
}

int main() 
{
    int n;
    cin >> n;
    for (int i=0; i<n; i++)
        cin >> a[i];
    
    quicksort(0, n-1);
    
    for (int i=0; i<n; i++)
        printf("%d\n",a[i]);
}

# C++(방법2 : Merge Sort 직접 구현)

#include <cstdio>

int a[1000000];  // original source
int b[1000000];  // temp array

// 왼쪽 집합의 startIndex, 오른쪽 집합의 endIndex를 매개변수로 받아서 두 집합을 병합하는 함수
void merge(int start, int end) 
{
    int mid = (start+end)/2;
    int i = start;         // 왼쪽 뭉텅이의 시작 인덱스
    int j = mid+1;         // 오른쪽 뭉텅이의 시작 인덱스
    int k = 0;             // 배열 b의 index로 사용되는 변수

    // 왼쪽집합과 오른쪽집합을 정렬된 상태로 배열 b에 저장하는 것
    while (i <= mid && j <= end) 
    {
        if (a[i] <= a[j])
            b[k++] = a[i++];
        else
            b[k++] = a[j++];
    }

    // 위 과정에서 오른쪽 집합은 b에 모두 옮겨졌는데 왼쪽 집합은 아직 옮겨지지 않은게 남아있다면 b에 마저 옮김
    while (i <= mid)
        b[k++] = a[i++];
    
    // 위 과정에서 왼쪽 집합은 b에 모두 옮겨졌는데 오른쪽 집합은 아직 옮겨지지 않은게 남아있다면 b에 마저 옮김
    while (j <= end)
        b[k++] = a[j++];

    // 정렬된 것을 저장한 배열 b의 값을 원본 배열인 a에 옮김
    for (int i=start; i<=end; i++)
        a[i] = b[i-start];
}

void sort(int start, int end)
{
    if (start == end)  // 재귀호출 시 start == mid, mid+1 == end 인 경우 재귀호출을 멈추기 위함
        return;

    int mid = (start+end)/2;

    sort(start, mid);  // 분할
    sort(mid+1, end);  // 분할
    merge(start, end); // 정렬하면서 병합
}

int main() 
{
    int n;
    scanf("%d",&n);

    for (int i=0; i<n; i++) 
        scanf("%d", &a[i]);

    sort(0, n-1); // index 0 ~ n-1 구간을 정렬시킴

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

    return 0;
}

# C++(방법3 : STL sort 함수 이용)

/*배열을 사용한 구현*/
#include <cstdio>
#include <algorithm>

using namespace std;

int a[1000001];
int main() {
    int n;
    scanf("%d",&n);
    for (int i=0; i<n; i++)
        scanf("%d",&a[i]);
        
    sort(a,a+n);
    
    for (int i=0; i<n; i++)
        printf("%d\n",a[i]);
}


/*벡터를 사용한 구현*/
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<int> vec;

    int T;
    cin >> T;

    for (int i = 0; i < T; i++){
        int temp;
        cin >> temp;
        vec.push_back(temp);
    }
        
    sort(vec.begin(), vec.end());

    int len = vec.size();
    for(int i = 0; i < len ;i++)
        cout << vec[i] << "\n";
}