Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 2750 수 정렬하기
문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
공통 코드
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
int[] list = new int[num];
for (int i=0; i<num; i++) {
list[i] = scanner.nextInt();
}
// 정렬 코드
for (int i=0; i<num; i++) {
System.out.println(list[i]);
}정렬 방식
1. 선택 정렬
- 시간 복잡도: O(n^2)
- 가장 많이 봤던 정렬 코드
- 코드
for (int i=0; i<num-1; i++) {
for (int j=i+1; j<num; j++) {
if (list[i] > list[j]) {
int temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
}
- 결과
2. 삽입정렬
- 정렬되어 있는 부분에 새로운 레코드를 올바른 위치에 삽입하는 과정을 반복하는 정렬
- 코드
for(int i=0; i<num; i++) {
for (int j=i; j>0; j--) {
if (list[j] < list[j-1]) {
int temp = list[j];
list[j] = list[j-1];
list[j-1] = temp;
} else break;
}
}
-
결과
-
경우
1) 최선의 경우: 이미 정렬이 되어 있는 경우 시간복잡도 O(n)
2) 최악의 경우: 역순으로 정렬 되어 있는 경우 시간복잡도 O(n^2)
3) 평균의 경우: O(n^2)
3. 퀵 정렬
- 평균적으로 가장 빠른 정렬 방식
- 분할정복법 사용
-
- 과정
피벗을 기준으로 피벗의 값보다 작은 데이터, 큰 데이터 배열 2개를 부분 리스트로 비균등 분할
- 코드
public static void quickSort(int arr[], int start, int end) {
int pivot = start;
int left = start+1;
int right = end;
if(start>=end) {return;}
while(left<=right) {
while(left<=end&&arr[left]<=arr[pivot]) {
left++;
}
while(right>start&&arr[right]>=arr[pivot]) {
right--;
}
if(left>right) {
int temp = arr[pivot];
arr[pivot] = arr[right];
arr[right] = temp;
}
else {
int temp = arr[left];
arr[left]= arr[right];
arr[right]=temp;
}
}
quickSort(arr, start, right-1);
quickSort(arr, right+1,end);
}
- 결과
4. Arrays.sort
- 자바가 제공하는 기본 정렬 메소드
Arrays.sort(list);- 결과
