백준 1517 버블소트

문제이름이 버블소트라 일단 버블소트를 설명하자면 첫번째 인덱스부터 바로 다음 인덱스의 값과 비교하여 현재 기준이 되는 인덱스가 더 클경우 다음 인덱스와 자리를 바꿔주는 정렬이다. 1회 정렬이 끝날때마다 맨 끝순서에 가장 큰 수들이 정렬된다.

버블 정렬은 해당 블로그를 참고했다
https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html 

[알고리즘] 버블 정렬(bubble sort)이란 - Heee's Development Blog

버블소트를 공부한 후 버블 소트를 직접 구현해 swap할 때마다 변수의 숫자를 증가시켜주었는데 아쉽게도 시간초과가 났다. 즉 이 수열을 분할해 작게 만든 후에 계산을 해주어야한다는 것이다.

따라서 버블 소트 대신 합병정렬을 사용했다. 합병 정렬은 수열을 계속 반으로 나누어 가장 작은 경우까지 도달할 경우 (수열에 수가 두개인 경우)에 두 수를 비교하여 작은 수를 앞으로 정렬하는 것을 반복해 나눠진 수열들을 마지막에 합치는 정렬 방법이다. 

버블 정렬은 해당 블로그를 참고했다

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;
int list[500001];
int sorted[500001];
long long s = 0;
void merge( int left, int mid, int right){
  int i, j, k, l;
  i = left;
  j = mid+1;
  k = left;

  while(i<=mid && j<=right){
      
      if(list[i]<=list[j]){
          sorted[k++] = list[i++];
          
         
      } else{
          sorted[k++] = list[j++];
          s += (mid - i + 1);
          
      }
  }

  if(i>mid){
      for(l=j; l<=right; l++){
          sorted[k++] = list[l];
      }
      
  } else{
      for(l=i; l<=mid; l++){
          sorted[k++] = list[l];
      }
      
  }


  for(l=left; l<=right; l++){
    list[l] = sorted[l];
  }
}

// 합병 정렬
void merge_sort(int left, int right){
  int mid = (left+right)/2;
  if(left<right){
      
    merge_sort(left, mid);
    merge_sort( mid+1, right);
    merge(left, mid, right);
  }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;

    for(int i=1; i<=n; i++){
        
        cin >> list[i];
    }
    
    merge_sort(1, n);
    cout << s;

   
        

}