[Algorithm] 백준 단계별로 풀어보기 - 단계 11. 정렬

정렬 알고리즘 기본, 응용

2750. 정렬 

시간 복잡도 O(n²)

 

(1) 선택 정렬: 배열의 앞이 줄어든다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ_2750 {
	public static void main(String[] args) throws Exception {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(rd.readLine());
		
		//수 입력
		int number[] = new int[N];
		for(int i=0; i<N; i++) {
			number[i] = (Integer.parseInt(rd.readLine()));
		}
		
		//선택 정렬
		int tmp;
		for(int i=0; i<N-1; i++) {
			for(int j=i; j<N; j++) {
				if(number[j] < number[i]) {
					tmp = number[j];
					number[j] = number[i];
					number[i] = tmp;
				}
			}
		}
		
		//출력
		for(int i=0; i<N; i++) {
			System.out.println(number[i]);
		}
	}
}

 

(2) 버블정렬: 배열의 뒤가 줄어든다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ_2750_bubble {
	public static void main(String[] args) throws Exception {
		BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(rd.readLine());
		
		//수 입력
		int number[] = new int[N];
		for(int i=0; i<N; i++) {
			number[i] = (Integer.parseInt(rd.readLine()));
		}
		
		int tmp;
		for(int i=N-1; i>0; i--) {
			for(int j=0; j<i; j++) {
				if(number[j+1] < number[j]) {
					tmp = number[j+1];
					number[j+1] = number[j];
					number[j] = tmp;
				}
			}
		}
		
		//출력
		for(int i=0; i<N; i++) {
			System.out.println(number[i]);
		}
	}
}

2751. 정렬 2

시간 복잡도가 O(nlogn)인 정렬 알고리즘 사용하기. (ex. 병합 정렬, 힙 정렬)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
 
public class Main {
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            int n = Integer.parseInt(br.readLine());
            ArrayList<Integer> data = new ArrayList<Integer>();
            for(int i=0; i<n; i++) {
                data.add(Integer.parseInt(br.readLine()));
            }
            Collections.sort(data);
            for(int i=0; i<n; i++) {
                System.out.println(data.get(i));
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

10989. 정렬 3

카운팅 정렬 사용하여 문제 풀기

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());

		int arr[] = new int[10001];
		for(int i=0; i<N; i++) {
			int index = Integer.parseInt(br.readLine());
			arr[index]+=1;
		}

		for(int i=0; i<10001; i++) {
			if(arr[i] > 0) {
				for(int j=0; j<arr[i]; j++) {
					bw.write(String.valueOf(i));
					bw.newLine();
				}
			}
		}
		br.close();
		bw.flush();
	}
}