[백준/C++]2750번(수 정렬하기), 2751번(수 정렬하기 2)

첫 번째 문제는 다음과 같습니다.

이미 이 전에 풀었었던 문제였고, 이번 스터디때 또 풀게 된 문제입니다.
대신, 다른 정렬을 이용하여 풀어보았습니다.
이번 주 알고리즘 분석 수업시간에 "교환 정렬"에 대해서 배웠는데 이를 이용하여 풀어보았습니다.
교환 정렬은 즉, 이중 for문이 돌고,
겉의 for문을 i가 순회한다고 하면
i가 한 번 끝날 때 마다 i의 자리가 찾아지는 정렬 알고리즘입니다.
즉 -> 이 방향으로 자리가 찾아진다고 보면 됩니다.

제 코드는 다음과 같습니다.

#include <bits/stdc++.h>
 using namespace std;

 int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);

   int n; vector<int> v;
   cin>>n;
   for(int i=0; i<n; i++){
     int tmp; cin>>tmp; v.push_back(tmp);
   }

   for(int i=0; i<v.size()-1; i++){
     for(int j=i+1; j<v.size(); j++){
       if(v[i]>v[j]) swap(v[i], v[j]);
     }
   } // i가 끝날 때마다 i의 자리가 구해 짐 -> 방향으로

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

사실 버블 정렬과 거의 비슷한 것 같습니다.
버블정렬은 가장 뒤에서부터 정렬이 이루어지는데
즉, <- 순으로 되어지는데
교환정렬은 반대 방향 아닌가요? ㅎㅎ

교환정렬의 시간복잡도는
(n-1)+(n-2)+ ... + (1) = n(n-1)/2

즉 O(N^2)입니다.

두 번째 문제는 다음과 같습니다.

이번에는 합병 정렬을 이용하여 풀어보았습니다.
제 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int a[1000001];

void func(int l, int r){
  if(l>=r) return;

  int mid = (l+r)/2;
  func(l, mid);
  func(mid+1, r);

  vector<int> tmp;
  int i=l, j=mid+1;
  while(i<=mid && j<=r){
    if(a[i]<a[j]) tmp.push_back(a[i++]);
    else tmp.push_back(a[j++]);
  }
  while(i<=mid) tmp.push_back(a[i++]);
  while(j<=r) tmp.push_back(a[j++]);

  int k=l;
  for(int j=0; j<tmp.size(); j++){
    a[k++]=tmp[j];
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin>>n;
  for(int i=0; i<n; i++) cin>>a[i];

  func(0, n-1);

  for(int i=0; i<n; i++) cout<<a[i]<<"\n";
  return 0;
}

merge sort의 시간복잡도는 O(nlogn)입니다.
합병정렬 알고리즘은 거의 외우다시피 하였는데 오랜만에 다시 짜보려니 사알짝 버벅거렸네요
재귀 진짜 더 잘하구 싶습니당,,