https://www.acmicpc.net/problem/2750
2750번: 수 정렬하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
시간 복잡도가 O(n²)인 정렬 알고리즘으로 풀 수 있다. 예를 들면 삽입 정렬, 버블 정렬 등이 있다.
1. 버블 정렬
버블정렬은 이웃하는것과 하나하나씩 비교를 하여 정렬을 한다.
따라서 하나하나씩 비교를 할때 모두다 오름차순이면 더이상 진행을 하지 않아도 된다.
따라서, i가 n-1부터 시작을하여 i의 값을 1씩 줄어들게 만들고 i이하의 범위 내에서 가장 큰 수는 배열에서 i의 위치에 오도록 만든다.
2. 삽입 정렬
pivot은 i가 1일때 부터 시작하고 j는 i-1부터 시작해서 1씩 줄어든다.
삽입정렬은 pivot 전의 배열의 원소들을 pivot과 비교해서 크면 한칸씩 뒤로 보낸다.
그리고 맨마지막으로 j+1위치에 pivot을 넣으면 되는데 j+1을 하는 이유는 for문을 빠져나올때 j값이 1이 더 감소하기 때문이다.
https://www.acmicpc.net/problem/2750
2750번: 수 정렬하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
시간 복잡도가 O(n²)인 정렬 알고리즘으로 풀 수 있다. 예를 들면 삽입 정렬, 버블 정렬 등이 있다.
1. 버블 정렬
버블정렬은 이웃하는것과 하나하나씩 비교를 하여 정렬을 한다.
따라서 하나하나씩 비교를 할때 모두다 오름차순이면 더이상 진행을 하지 않아도 된다.
따라서, i가 n-1부터 시작을하여 i의 값을 1씩 줄어들게 만들고 i이하의 범위 내에서 가장 큰 수는 배열에서 i의 위치에 오도록 만든다.
2. 삽입 정렬
pivot은 i가 1일때 부터 시작하고 j는 i-1부터 시작해서 1씩 줄어든다.
삽입정렬은 pivot 전의 배열의 원소들을 pivot과 비교해서 크면 한칸씩 뒤로 보낸다.
그리고 맨마지막으로 j+1위치에 pivot을 넣으면 되는데 j+1을 하는 이유는 for문을 빠져나올때 j값이 1이 더 감소하기 때문이다.
