[삽입 /선택 / 버블 정렬 구현하기]

JAVA로 구현했습니다.

가끔씩 까먹을 때 한번씩 찾아 보려구 작성했습니다.


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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
package pracitce_note;
 
/* 실행시간이 n2인 정렬
 * 오름차순 기준 */
public class Sort {
    
    public void print_array(int[] answer) {
        for(int i : answer) {
            System.out.print(i+" ");
        }
        System.out.println();
        System.out.println();
    }
    
    public int[] insert_sort(int[] answer) {
        
        int temp;
        /* insert Array (삽입정렬)
         * i번째 값을 선택 , i값은 answer길이보다 커지면 스탑 
         * j번째 부터 n번째까지 비교
         * 
         * */
        
        for(int i=1; i<answer.length; i++) {
            temp = answer[i];
            for(int j=i-1; j>=0; j--) {
                if(temp < answer[j]) {
                    answer[j+1] = answer[j];
                    answer[j] = temp;                    
                }
            }    
            System.out.println(i+"번째 회전 후");
            print_array(answer);
        }
        
        return answer;
        
    }
    
    public int[] slection_sort(int[] answer) {
        int min;
        int temp=0;
        
        /* Selection Sort (선택정렬 )
         * 1) min값을 찾는다 (min 선택)
         * 2) min값을  (i 번째와 바꾼다)
         * */
        
        for(int i=0; i<answer.length-1; i++) {
            min = i;
            for(int j=i+1; j<answer.length; j++) {
                
                if(answer[min]>answer[j]) {
                    min = j;
                }
            }
            temp = answer[i];
            answer[i] = answer[min];
            answer[min] = temp;
            
            System.out.println(i+1+"번째 회전 후");
            print_array(answer);
        }
        
        return answer;
    }
    
    public int[] bubble_sort(int[] answer) {
        
        int temp;
        
        /*
         * 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
         * j번과 j+1번을 비교해서 j가 더 크면 서로 자리 변경
         * 
         * */
        for(int i=0; i<answer.length-1; i++) {
            for(int j=0; j<answer.length-1-i; j++) {
                if(answer[j] > answer[j+1]) {
                    temp = answer[j];
                    answer[j] = answer[j+1];
                    answer[j+1] = temp;
                }
            }
            System.out.println(i+1+"번째 회전 후");
            print_array(answer);
        }
        
        return answer;
    }
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        int[] answer = {4,1,5,3,2};//{2,1,4,3,5};
        
        Sort s= new Sort();
        
        System.out.println("초기 배열 : ");
        s.print_array(answer);
        
        s.insert_sort(answer);        
        //s.bubble_sort(answer);
        //s.slection_sort(answer);
        
        
    }
 
}
 
cs




'알고리즘 공부 > 알고리즘 개념' 카테고리의 다른 글

Union Find 알고리즘  (0) 2019.05.29
트리 구현 - 인접행렬, 인접리스트  (0) 2019.04.08
DFS 알고리즘 (2) - 예제(행렬의 영역 구하기)  (0) 2019.04.08
DFS 알고리즘 (1) - 이론  (0) 2019.04.08
알고리즘 들어가기  (0) 2018.12.06

알고리즘에 문제들을 풀어보기 전에 기본적으로 사용되는 알고리즘에 대하여 정리 해보겠습니다.

(아래 내용들의 출처는 Topcit 에센스 내용을 참고 했습니다.)

(https://www.topcit.or.kr/edubox/essence/topcitEssence.do)



* 알고리즘이란 ? 

- 문제 해결을 위한 과정을 단계적으로 기술한 것.

  명확성(Definitness), 유한성(Finiteness), 유효성 (Effectiveness)를 만족해야 한다.


* 분석 기준

- 정확성 : 시간 내에 결과를 산출해야 한다

- 작업량 : 결과가 나올때까지 수행하는 횟수

- 기억 저장소 사용량 : 메모리 사용량

- 최적성 : 최적합 여부

- 단순성 : 작성 및 디버깅이 수월해야함


또 알고리즘에 대한 성능을 분석하는 방식이 있는데, 다음 2가지 방식이 있습니다.


* 성능 분석

- 공간 복잡도

프로그램으로 실행하여 완료하기까지 필요한 총 저장공간(고정 공간량 + 가변 공간량)

          •  고정 공간량 : 입출력에 상관 없이 고정적으로 필요한 공간
          •  가변 공간량 : 수행 과정에 사용되는 공간

- 시간 복잡도

프로그램을 실행하여 완료하기까지 걸리는 컴파일 시간과 실행 시간의 합

tip) 알고리즘 성능

log n < n < nlogn < n^2 < n^3 < 2^n


주로 알고리즘 문제를 풀때는 시간복잡도를 이용하여 계산을 많이하지요 ㅎㅎ


본격적으로 알고리즘 기초인 정렬에 관하여 공부해 보겠습니다.

알고리즘 코드를 들어가기 전! 어떤 정렬 방식들이 있는지 살펴 보아요!


내부 정렬은 다음과 같이 10가지로 나눌 수 있습니다. 

전공 수업을 들었을땐  계수정렬과 기수정렬은 안배워서 저도 이번에 알게 되었네요!


* 정렬


- 내부 정렬의 분류

내부 정렬은 아래 그림과 같이 나눌 수 있고 수행시간도 같이 적어 놓았습니다.





이상으로 알고리즘 기초와 정렬에 관하여 정리를 했고

다음 시간부터는 각 정렬에 관하여 공부를 해보도록 합시다!



'알고리즘 공부 > 알고리즘 개념' 카테고리의 다른 글

Union Find 알고리즘  (0) 2019.05.29
트리 구현 - 인접행렬, 인접리스트  (0) 2019.04.08
DFS 알고리즘 (2) - 예제(행렬의 영역 구하기)  (0) 2019.04.08
DFS 알고리즘 (1) - 이론  (0) 2019.04.08
삽입 /선택 / 버블 정렬 JAVA로 구현하기  (0) 2019.03.12

+ Recent posts

티스토리툴바