포스트

정렬 알고리즘

게시
By Kim Jung Wook 5 분읽는 시간

Arrays.sort() 메소드 이용하기 (164ms)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import java.io.*;
import java.util.*;

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));
    StringBuilder sb = new StringBuilder();
    
    int n = Integer.parseInt(br.readLine());
    
    int[] arr = new int[n];
    
    for(int i = 0; i < n; i++){
      arr[i] = Integer.parseInt(br.readLine());
    }
    
    Arrays.sort(arr);
    
    for(int i = 0; i < n; i++){
      sb.append(arr[i] + "\n");
    }

    bw.write(sb + "");
    bw.flush();
    bw.close();
    br.close();
  }
}
  • 메모리 : 16168 KB
  • 시간 : 164 ms

선택정렬 (200ms), 시간 복잡도 : O(n²)

  • 오름차순이므로, 현재 배열에서 가장 작은 수를 찾는다.
  • 가장 작은 수를 현재 배열의 맨 앞으로 이동한다.
  • 앞에 확정된 인덱스의 다음 인덱스부터 끝 범위까지의 값들 중 작은 값을 찾아낸다.
  • 확정된 인덱스 다음의 인덱스에 값을 넣는다.
  • 단계가 진행될 때마다 앞에 작은수들이 쌓여간다.
    ⇒ 5, 2, 3, 4, 1 ⇒ 1, 5, 2, 3, 4 ⇒ 1, 2, 5, 3, 4 ⇒ 1, 2, 3, 5, 4 ⇒ 1, 2, 3, 4, 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

import java.io.*;
import java.util.*;

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));
    StringBuilder sb = new StringBuilder();
    
    int n = Integer.parseInt(br.readLine());
    
    int[] arr = new int[n];
    
    for(int i = 0; i < n; i++){
      arr[i] = Integer.parseInt(br.readLine());
    }
    
    for(int i = 0; i < n-1; i++){
      int temp = i;
      
      for(int j = i+1; j < n; j++){
        if(arr[temp] > arr[j]){
          temp = j;
        }
      }
      
      if(i != temp){
        int swap = arr[i];
        arr[i] = arr[temp];
        arr[temp] = swap;
      }
    }

    
    for(int i = 0; i < n; i++){
      sb.append(arr[i] + "\n");
    }

    bw.write(sb + "");
    bw.flush();
    bw.close();
    br.close();
  }
}
  • 메모리 : 18956 KB
  • 시간 : 200 ms

삽입정렬 (172ms), 시간 복잡도 : O(n²)

  • 현재 인덱스에서 제일 앞의 인덱스(0)까지 값들을 비교
  • 비교 값이 현재 값보다 높으면 자리를 바꾼다.
  • 다음 인덱스로 이동하여 비교 진행을 반복한다.
  • 단계가 진행될 때마다 앞에 작은수들이 쌓여간다.
    ⇒ 5, 2, 3, 4, 1 ⇒ 2, 5, 3, 4, 1 ⇒ 2, 3, 5, 4, 1 ⇒ 2, 3, 4, 5, 1 ⇒ 1, 2, 3, 4, 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

import java.io.*;
import java.util.*;

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));
    StringBuilder sb = new StringBuilder();
    
    int n = Integer.parseInt(br.readLine());
    
    int[] arr = new int[n];
    
    for(int i = 0; i < n; i++){
      arr[i] = Integer.parseInt(br.readLine());
    }
    
    for(int i = 1; i < n; i++){
        
      for(int j = i; j > 0; j--){
        if(arr[j] < arr[j-1]){
          int swap = arr[j-1];
          arr[j-1] = arr[j];
          arr[j] = swap;
        }                
      }
    }

    
    for(int i = 0; i < n; i++){
      sb.append(arr[i] + "\n");
    }

    bw.write(sb + "");
    bw.flush();
    bw.close();
    br.close();
  }
}
  • 메모리 : 16736 KB
  • 시간 : 172 ms

버블정렬 (180ms), 시간 복잡도 : O(n²)

  • 현재 인덱스의 값과 다음 인덱스의 값을 비교하며 이동.
  • 현재 값이 더 크면 값을 바꾼다.
  • 다음 인덱스로 이동하여 비교 진행을 반복
  • 단계가 진행될 때마다 앞에 작은수가 뒤로는 큰수들이 이동한다.
    ⇒ 5, 2, 3, 4, 1 ⇒ 2, 3, 4, 1, 5 ⇒ 2, 3, 1, 4, 5 ⇒ 2, 1, 3, 4, 5 ⇒ 1, 2, 3, 4, 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

import java.io.*;
import java.util.*;

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));
    StringBuilder sb = new StringBuilder();
    
    int n = Integer.parseInt(br.readLine());
    
    int[] arr = new int[n];
    
    for(int i = 0; i < n; i++){
      arr[i] = Integer.parseInt(br.readLine());
    }
    
    while(true){
      boolean flag = true;
      for(int i = 0; i < n-1; i++){
        if(arr[i] > arr[i+1]){
          int temp = arr[i];
          arr[i] = arr[i+1];
          arr[i+1] = temp;
          flag = false;
        }
      }
      if(flag) break;
    }

    
    for(int i = 0; i < n; i++){
      sb.append(arr[i] + "\n");
    }

    bw.write(sb + "");
    bw.flush();
    bw.close();
    br.close();
  }
}
  • 메모리 : 16544 KB
  • 시간 : 180 ms
알고리즘, 정렬
정렬