백준(BOJ) 2750번 수 정렬하기

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

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

나의풀이 :

N이 최대 1000이니 삽입정렬의 시간복잡도(N^2)로도 충분히 가능하기에 삽입정렬로 풀이 하였다. 삽입정렬은 필요한 만큼만 정렬을 할 수 있기에

N^2의 복잡도중 가장 효율이 좋다.

사실 이 문제는 c++ stl algorithm에 std::sort 로 간단히 해결 가능하다. std:sort는 quicksort를 기반으로 구현되며 nlgn 에 복잡도를 보장하기 때문에 가능하다.

코드 ( C ++ )

#include <iostream>

#include <vector>

using namespace std;

int N;

const int MAX = 1000;

int arr[MAX];

void InsertionSort()

{

for (int i = 0; i < N; ++i)

{

int j = i;

// j 는 0보다 크고 j-1 이 j보다 크다면 바꿔준다.

while (j > 0 && arr[j - 1] > arr[j])

{

swap(arr[j - 1], arr[j]);

//  j가 0보다 크고 j-1이 큰 경우를 발견할때까지 j를 -1 시킨다.

j--;

}

}

}

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(0);

cin >> N;

for (int i = 0; i < N; ++i)

cin >> arr[i];

InsertionSort();

for (int i = 0; i < N; ++i)

cout << arr[i] << endl;

return 0;

}

*/

//  std::sort 써보기

#include <iostream>

#include <algorithm>

using namespace std;

int N;

const int MAX = 1000;

int arr[MAX];

int main()

{

int N;

cin >> N;

for (int i = 0; i < N; ++i)

cin >> arr[i];

sort(arr, arr + N);

for (int i = 0; i < N; ++i)

cout << arr[i] << endl;

return 0;

}

*/