200926 토 [BOJ] 2750

( 정렬 공부 참고 블로그 https://reakwon.tistory.com/37 )

💡 정렬의 종류

• 선택정렬 (Selection Sort),
• 버블정렬 (Bubble Sort),
• 삽입정렬 (Insertsion Sort),
  
  
• 병합정렬 (Merge Sort) - ✔Divide and Conquer,
• 힙정렬 (Heap Sort) - ✔Heap,
• 퀵정렬 (Quick Sort) - ✔Divide and Conquer, ✔Pivot
  
  

BOJ 2750

1. 선택 정렬 (Selection Sort)

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

public class Main {	

    public static void main(String[] args) throws IOException {
    	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[N];
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(br.readLine());
    	}
    	br.close();
    	
    	int minIndex;
    	for(int i=0;i<N-1;i++) {
    		minIndex = i;
    		for(int j=i+1;j<N;j++) {
    			if(arr[j] < arr[minIndex]) {
    				minIndex = j;
    			}
    		}
    		int tmp = arr[i];
    		arr[i] = arr[minIndex];
    		arr[minIndex] = tmp;
    	}
    
    	for(int i=0;i<N;i++) {
    		bw.write(String.valueOf(arr[i]));
    		bw.newLine();
    	}
    	bw.flush();    	
    	bw.close();
    }
}

메모리 14352KB, 시간 100ms 소요

맨 첫번째 index부터 마지막-1 index까지 큰 반복문을 한 번 돌고 (비교 대상 index),
그 안에서 현재 index(i) 바로 다음 index(i+1)부터 마지막 index까지 도는 반복문을 한 번 더 실행하여,
가장 작은 값의 index를 찾아 minIndex로 지정하고, 그 값을 i index의 값과 위치를 바꾸는 방식으로 해결했다.

(당연히 반대로 가장 큰값을 맨 뒤로 방식으로도 풀이할 수 있음.)

2. 버블 정렬 (Bubble Sort)

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

public class Main {	

    public static void main(String[] args) throws IOException {
    	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[N];
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(br.readLine());
    	}
    	br.close();
    	
    	for(int i=N-1;i>0;i--) {
    		for(int j=0;j<i;j++) {
    			if(arr[j]>arr[j+1]) {
    				int tmp = arr[j];
    				arr[j] = arr[j+1];
    				arr[j+1] = tmp;
    			}
    		}
    	}
    
    	for(int i=0;i<N;i++) {
    		bw.write(String.valueOf(arr[i]));
    		bw.newLine();
    	}
    	bw.flush();    	
    	bw.close();
    }
}

메모리 13704KB, 시간 108ms 소요

3. 삽입 정렬 (Insertion Sort)

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

public class Main {	

    public static void main(String[] args) throws IOException {
    	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[N];
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(br.readLine());
    	}
    	br.close();
    	
    	int i,j,key;
    	for(i=1;i<N;i++) {
    		key = arr[i];
    		j = i-1;
    		while(j>=0 && arr[j]>key) {
    			arr[j+1] = arr[j];
    			j--;
    		}
    		arr[j+1] = key;
    	}
    
    	for(int k=0;k<N;k++) {
    		bw.write(String.valueOf(arr[k]));
    		bw.newLine();
    	}
    	bw.flush();    	
    	bw.close();
    }
}

메모리 13620KB, 시간 108ms 소요

---