반응형

알고리즘 정렬기법 중 가장 기본적인 정렬 삽입, 버블, 선택 정렬을 정리했다

시간복잡도는 O(N^2)이고, 익숙해질 때까지 소스를 보면서 눈에 익히고 구현에 대해서도 계속 생각해보자.

선택정렬이 제일 헷갈렸다... 처음엔 제일 쉬워보였는데 어렵네

 

삽입정렬

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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tmp;
        int j;
        
        int n = sc.nextInt();
        int[] a = new int[n];
        
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        
        for(int i = 1; i < n; i++) {
            tmp = a[i];
            for(j = i - 1; j >= 0 && a[j] > tmp; j--) {
                a[j+1] = a[j];
            }
            a[j+1] = tmp;
        }
        
        for(int array : a) {
            System.out.println(array);
        }
    }
}
cs

 

버블정렬

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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tmp;
        int j;
        
        int n = sc.nextInt();
        int[] a = new int[n];
        
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        
        for(int i = 0; i < n-1; i++) {
            for(j = 0; j < n-i-1; j++) {
                if(a[j] > a[j+1]) {
                    tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                }
            }
        }
        
        for(int array : a) {
            System.out.println(array);
        }
        
    }
}
cs

 

선택정렬

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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tmp = 0;
        int j;
        int index;
        
        
        int n = sc.nextInt();
        int[] a = new int[n];
        
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        
        for(int i = 0; i < n-1; i++) {
            index = i;
            for(j = i + 1; j < n; j++) {
                if(a[j] < a[i]) {
                    index = j;
                    tmp = a[i];
                    a[i] = a[index];
                    a[index] = tmp;
                }
            }
        }
        
        for(int array : a) {
            System.out.println(array);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'공부 > Algorithm 이론' 카테고리의 다른 글

퀵정렬 예제소스  (0) 2023.01.25
LinkedList 예제 java  (0) 2023.01.19
LinkedList 예제  (0) 2023.01.11
이진 탐색  (0) 2023.01.07

+ Recent posts

티스토리툴바