728x90
반응형
728x90
반응형

 

삽입 정렬 알고리즘

삽입 정렬(Insertion Sort) 알고리즘은 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘입니다.

  • Index가 2번째부터 시작합니다.
  • (오름차순) Index의 값보다 크면 한 칸씩 뒤에 저장합니다.
  • 위치를 찾으면 그 위치로 삽입합니다.
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
public class Insertion_Sort {
    public static void main(String[] args) {
        
        int[] arr = { 10, 50, 80, 90, 70 };
 
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            for (int j = i; j > 0; j--) {
                
                if (arr[j - 1] > temp) {
                    arr[j] = arr[j - 1];
                    
                    if (j == 1) {
                        arr[j] = temp;
                        break;
                    }
                    
                } else {
                    arr[j] = temp;
                    break;
                }
            }
        }
        output(arr);
    }
 
    private static void output(int[] arr) {
        
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter
728x90
반응형
저작자표시

'알고리즘' 카테고리의 다른 글

[알고리즘] 쉘정렬 (Shell Sort) Java Example  (0) 2019.06.23
[알고리즘] 버블정렬 (Bubble Sort) Java Example  (0) 2019.06.23
[알고리즘] 선택정렬 (Selection Sort) Java Example  (0) 2019.06.16
[알고리즘] 퀵정렬 (Quick Sort) Java Example  (0) 2019.06.16
[알고리즘] 합병정렬/병합정렬 (Merge Sort) Java Example  (0) 2019.06.16
Modify | Delete
728x90
반응형

 

선택 정렬 알고리즘

선택 정렬(Selection Sort) 알고리즘은 원소가 앞에서부터 정렬되는 알고리즘입니다.

  • 원소들 중에서 최솟값을 찾는다.
  • 맨 앞의 값과 최솟값과 교체(Swap) 한다.
  • 마지막으로 교체(Swap)한 다음 위치부터 위와 같이 진행한다.
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
public class Selection_Sort {
    public static void main(String[] args) {
        int[] arr = { 10, 50, 80, 90, 70 };
 
        for (int i = 0; i < arr.length - 1; i++) {
            
            int min = i;
 
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    /*최솟값의 위치를 변경한다*/
                    min = j;
                }
            }
            
            /*맨 앞 부터 최솟값의 원소와 교체한다.*/
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
        output(arr);
    }
 
    private static void output(int[] arr) {
        
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter
728x90
반응형

'알고리즘' 카테고리의 다른 글

[알고리즘] 버블정렬 (Bubble Sort) Java Example  (0) 2019.06.23
[알고리즘] 삽입정렬 (Insertion Sort) Java Example  (0) 2019.06.16
[알고리즘] 퀵정렬 (Quick Sort) Java Example  (0) 2019.06.16
[알고리즘] 합병정렬/병합정렬 (Merge Sort) Java Example  (0) 2019.06.16
[알고리즘] 이진탐색 (Binary Search) Java Example  (0) 2019.06.16
Modify | Delete
728x90
반응형
 

퀵 정렬 알고리즘

퀵 정렬(Quick Sort) 알고리즘은 원소들 중에서 특정한 기준을 피봇(Pivot)라고 부르며

피봇보다 작은 원소는 왼쪽으로 큰 원소는 오른쪽으로 이동한다.

초기 세팅 변수 left = 0 , rigth = 배열 길이-1 , pivot = (left+right)/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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class Quick_Sort {
 
    public static void main(String[] args) {
        
        int[] arr = { 10, 50, 80, 90, 70 };
        
        quick_Sort(arr, 0, arr.length - 1);
        output(arr);
    }
 
    private static void quick_Sort(int[] arr, int start, int end) {
        
        int left = start;
        int right = end;
        /*pivot을 중앙 값으로 셋팅*/
        int pivot = arr[(left + right) / 2];
 
        do {
            while (arr[left] < pivot) {
                left++;
            }
            while (arr[right] > pivot) {
                right--;
            }
 
            if (left <= right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
 
        } while (left <= right);
 
        if (start < right) {
            quick_Sort(arr, start, right);
 
        }
        if (end > left) {
            quick_Sort(arr, left, end);
        }
    }
 
    private static void output(int[] arr) {
        
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

 

퀵 정렬 성능 향상 방법

  • 작은 데이터 구간에는 삽입 정렬을 사용하여 퀵 정렬의 재귀의 깊이를 줄여 스택 사용을 줄여 준다
  • 비 재귀 구현
  • 난수(Random) 분할 > Worst 경우 인 정렬된 배열과 역순 배열일 때 문제를 해결하기 위해 난수로 선택한다
  • 메디안 퀵 정렬(Median of Three QuickSort) - 세 값(처음, 가운데, 끝)의 중윗값을 찾아 Pivot으로 선택한다
728x90
반응형

'알고리즘' 카테고리의 다른 글

[알고리즘] 삽입정렬 (Insertion Sort) Java Example  (0) 2019.06.16
[알고리즘] 선택정렬 (Selection Sort) Java Example  (0) 2019.06.16
[알고리즘] 합병정렬/병합정렬 (Merge Sort) Java Example  (0) 2019.06.16
[알고리즘] 이진탐색 (Binary Search) Java Example  (0) 2019.06.16
[알고리즘] 알고리즘(algorithm)이란 ?  (0) 2019.06.16
Modify | Delete
728x90
반응형

 

합병정렬 알고리즘

합병정렬(Merge Sort) 알고리즘은 원소를 반으로 분할한 후 분할한 원소를 다시 병합하는 정렬 방법입니다.

초기 세팅 변수 left = 0 , rigth = 배열 길이-1 , mid = (left+right)/2

  • 원소를 반으로 계속 나눈다 >>> 배열(리스트)의 길이가 1이 될 때 까지 분할합니다. (mergeSortDevide)
  • 1개씩 분할된 원소들을 정렬하면서 합친다. (Merge)
 
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
public class Merge_Sort {
 
    public static void main(String[] args) {
        
        int[] arr = { 10, 80, 91, 90, 70 };
        
        /*원소를 반으로 나누는 함수*/
        mergeSortDevide(arr, 0, arr.length - 1);
        
        /*합병 정렬된 배열을 출력하는 함수*/
        output_merge_arr(arr); 
    }
 
    private static void mergeSortDevide(int[] arr, int left, int right) {
        
        /*원소의 수가 2개 이상일경우 실행*/
        if (left < right) { 
            
            /*반으로 나누기 위한 변수*/
            int mid = (left + right) / 2; 
            
            /*앞(왼쪽)부분 재귀 호출*/
            mergeSortDevide(arr, left, mid); 
        
            /*뒤(오른쪽)부분 재귀 호출*/
            mergeSortDevide(arr, mid + 1, right);
            
            /*원소를 Merge하는 함수*/
            merge(arr, left, mid, right); 
        }
    }
 
    private static void merge(int[] arr, int left, int mid, int right) {
 
        int i = left;
        int j = mid + 1;
        int temp_index = left;
 
        int[] temp = new int[arr.length];
 
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                temp[temp_index++] = arr[i++];
            } else {
                temp[temp_index++] = arr[j++];
            }
        }
        
        /*앞(왼쪽)부분 배열에 원소가 남아있는 경우*/
        while (i <= mid) { 
            temp[temp_index++] = arr[i++];
        }
        
        /*뒤(오른쪽)부분 배열에 원소가 남아있는 경우*/
        while (j <= right) {
            temp[temp_index++] = arr[j++];
        }
 
        for (int index = left; index < temp_index; index++) {
            arr[index] = temp[index];
        }
    }
 
    private static void output_merge_arr(int[] arr) {
        
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
 
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter
728x90
반응형

'알고리즘' 카테고리의 다른 글

[알고리즘] 삽입정렬 (Insertion Sort) Java Example  (0) 2019.06.16
[알고리즘] 선택정렬 (Selection Sort) Java Example  (0) 2019.06.16
[알고리즘] 퀵정렬 (Quick Sort) Java Example  (0) 2019.06.16
[알고리즘] 이진탐색 (Binary Search) Java Example  (0) 2019.06.16
[알고리즘] 알고리즘(algorithm)이란 ?  (0) 2019.06.16
Modify | Delete
728x90
반응형

 

이진탐색 알고리즘

이진탐색(Binary Search) 알고리즘은 원소를 반으로 분할(분류)하여 찾는 방법입니다.

이진탐색 알고리즘 조건

★ 모든 원소는 정렬되어야 한다. ★

초기 세팅 변수 left = 0 , rigth = 배열 길이-1 , mid = (left+right)/2

  • 찾고자 하는 KEY 값이 arr[mid]인 경우 mid위치가 찾고자하는 KEY값의 INDEX위치
  • 찾고자 하는 KEY 값이 arr[mid]보다 작은 경우 mid위치보다 앞(왼쪽)에 위치한다. (오름차순일 경우)
  • 찾고자 하는 KEY 값이 arr[mid]보다 큰 경우 mid위치보다 뒤(오른쪽)에 위치한다. (오름차순일 경우)

 

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
public class BinarySearch {
    public static void main(String[] args) {
 
        /* 찾고자 하는 원소들 */
        int[] arr = { 3, 19, 34, 50, 87 };
 
        /* 찾고자 하는 KEY값 */
        int key = 19;
 
        binarySearch(arr, key);
    }
 
    private static void binarySearch(int[] arr, int key) {
 
        /* 배열의 첫번째 인덱스 값 */
        int left = 0;
 
        /* 배열이라서 -1함 */
        int right = arr.length - 1;
        int mid;
 
        while (left <= right) {
 
            /* 중앙값을 계산한다 */
            mid = (left + right) / 2;
 
            if (key == arr[mid]) {
                System.out.println(key + "값의 Array Index 위치 : " + mid);
                break;
            }
 
            /* 찾고자 하는 KEY값이 배열의 중앙값보다 작을경우 */
            if (key < arr[mid]) {
 
                /* 데이터는 왼쪽에 위치함으로 right를 mid에서 1을 뺀 값으로 변경 */
                right = mid - 1;
            }
 
            /* 찾고자 하는 KEY값이 배열의 중앙값보다 클 경우 */
            else {
 
                /* 데이터는 오른쪽에 위치함으로 left값을 mid에서 1을 더한 값으로 변경 */
                left = mid + 1;
            }
        }
    }
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter
728x90
반응형

'알고리즘' 카테고리의 다른 글

[알고리즘] 삽입정렬 (Insertion Sort) Java Example  (0) 2019.06.16
[알고리즘] 선택정렬 (Selection Sort) Java Example  (0) 2019.06.16
[알고리즘] 퀵정렬 (Quick Sort) Java Example  (0) 2019.06.16
[알고리즘] 합병정렬/병합정렬 (Merge Sort) Java Example  (0) 2019.06.16
[알고리즘] 알고리즘(algorithm)이란 ?  (0) 2019.06.16
Modify | Delete
728x90
반응형

 

알고리즘이란 ?

문제를 해결하는 단계적 절차 또는 방법이다.

 

알고리즘의 특성 4가지

정확성 : 알고리즘은 주어진 입력에 대해 결과를 줘야 한다.

수행성 : 알고리즘은 컴퓨터에서 수행 가능해야 한다

유한성 : 알고리즘은 일정 시간 내에 종료되어야 한다

효율성 : 알고리즘은 효율적일수록 가치가 높아진다

 

알고리즘 표현 방법

프로그래밍 언어(JAVA, C 등) 혹은 의사 코드(pseudo code)로 표현한다.

 

알고리즘 효율성이란 ?

알고리즘의 효율성은 알고리즘의 수행 시간 혹은 수행하는 동안 사용되는 메모리 공간의 크기로 나타낸다.

                                  시간복잡도 (time complexity)                      공간복잡도 (space complexity)

일반적으로 알고리즘을 비교할 때 시간 복잡도가 주로 사용한다.

 

복잡도의 점근적 표기

점근적 표기(Asymptotic Notation) : 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법

O - (Big-Oh) 표기 : 복잡도의 점근적 상한을 표시

Ω - (Big-Omega) 표기 : 복잡도의 점근적 하한을 표시

θ - (Theta) 표기 : 복잡도의 하한과 상한을 표시

                                 O-(Big-Oh) 표기와 Ω-(Big-Omega) 표기가 같은 경우에 사용한다.

 

성능 비교

O(1) < O(log2N) < O(n) < O(Nlog2N) < O(n^2) < O(n^3) < O(2^n) < O(n!)

728x90
반응형

'알고리즘' 카테고리의 다른 글

[알고리즘] 삽입정렬 (Insertion Sort) Java Example  (0) 2019.06.16
[알고리즘] 선택정렬 (Selection Sort) Java Example  (0) 2019.06.16
[알고리즘] 퀵정렬 (Quick Sort) Java Example  (0) 2019.06.16
[알고리즘] 합병정렬/병합정렬 (Merge Sort) Java Example  (0) 2019.06.16
[알고리즘] 이진탐색 (Binary Search) Java Example  (0) 2019.06.16
Modify | Delete

+ Recent posts

티스토리툴바