알고리즘

Dec 18, 2023

Contents

💡

함수를 절차적 으로 나눠서 코딩 하는 것 ex)라면 1.라면 봉지를 뜯는다. 2.물을 500ml만큼 냄비에 넣고 끓인다. 3.물이 끓으면 라면을 넣는다. 4.라면을 넣고 또 물이 끓으면 계란을 넣는다 5.15초 뒤에 불을 끈다.

버블 정렬

💡

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.


버블 정렬은 첫 번째 인덱스와 두 번째 인덱스를, 두번째 인덱스와 세 번째 인덱스를, 
... 이런식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.


1회전(값의 갯수 -1) 할때 가장 큰 수가 마지막 자리에 오게 끔 정렬 하는 것이다.

ex)

5, 8, 2, 4, 3

1회전 (4바퀴)

(1) 5, 8 비교하기 (변화 없음)

(2) 8, 2 비교 (5, 2, 8, 4, 3)

(3) 8, 4 비교 (5, 2, 4, 8, 3)

(4) 8, 3 비교 (5, 2, 4, 3, 8)

2회전(3바퀴)

(1) 5, 2 비교 (2, 5, 4, 3, 8)

(2) 5, 4, 비교(2, 4, 5, 3, 8)

(3) 5, 4, 비교(2, 4, 3, 5, 8)

3회전(2바퀴)

(1) 2, 4, 비교(2, 4, 3, 5, 8)

(2) 4, 3, 비교(2, 3, 4, 5, 8)

3, 4, 8, 2, 5

(1) 3, 4, 8, 2, 5

(2) 3, 4, 8, 2, 5

(3) 3, 4, 2, 8, 5

(4) 3, 4, 2, 5, 8

완성된 코드


package ex03;

/**
 * 5, 8, 2, 4, 3 (N)
 * 회전수 : N-1
 * 1회전 비교 횟수 : N-1
 * 2회전 비교 횟수 : N-2
 * 3회전 비교 횟수 : N-3
 * 4회전 비교 횟수 : N-4
 * <p>
 * 1회전 (4바퀴)
 * (1) 5, 8 비교 (변화없음)
 * (2) 8, 2 비교 (5,2,8,4,3)
 * (3) 8, 4 비교 (5,2,4,8,3)
 * (4) 8, 3 비교 (5,2,4,3,8)
 * <p>
 * 2회전 (3바퀴)
 * (1) 5,2 비교 (2,5,4,3,8)
 * (2) 5,4 비교 (2,4,5,3,8)
 * (3) 5,3 비교 (2,4,3,5,8)
 * <p>
 * 3회전 (2바퀴) - 끝
 * (1) 2,4 비교
 * (2) 4,3 비교 (2,3,4,5,8)
 * <p>
 * 4회전 (1바퀴)
 * (1) 2,3 비교
 */

public class BubbleEx01 {

    static void bubble(int[] arr) {
        final int N = arr.length;

        int temp;

        for (int loop = 1; loop < 5; loop++) {
            for (int i = 0; i < N - loop; i++) {
                if (arr[i] > arr[i + 1]) {
                    temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
        }

        // 출력코드
        for (int i = 0; i < 5; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 4, 3};
        BubbleEx01.bubble(arr);
        System.out.println();

        int[] arr2 = {5, 8, 2, 4, 3, 10, 500, 7, 6};
        BubbleEx01.bubble(arr2);
    }
}

정렬의 목적

💡

정렬의 목적은 ex)5, 7, 9, 10, 15, 3, …. 이렇게 값이 있을 때 자료 구조의 검색에 초점이 맞춰져 있다. 효율적으로 원하는 데이터를 찾기 쉬워진다. 중복이 데이터가 있어도 멈추는 타이밍을 알 수 있게 된다. -클러스터링(Clustering) :중심점을 기준으로 가까운 데이터들을 할당하고, 그룹화를 반복적으로 수행 한다.

선택 정렬

💡

0번째 인덱스 값과 첫 번째 인덱스 값부터 마지막 인덱스 값까지 차례대로 비교하며 가장 작은 값을 찾아 0번째에 놓고, 1번째 인덱스 값을 2번째 인덱스 값부터 마지막 인덱스 값까지 비교하여 그 중 가장 작은 값을 찾아 1번째 인덱스 값에 놓는 과정을 반복하며 정렬을 수행 한다.


제자리 정렬
P=PLACE

5, 8, 2, 4, 3

final i = 0 (해당 위치 변경), P=0(교환 인덱스)

5, 8 (0, 1)

5, 2 (0, 2)(P = 2)

2, 4 (2, 3)

2, 3 (2,4)

if( i ! =p )

(1) 2, 8, 5, 4,. 3 (i, p 교환)

final i = 1 (해당 위치 변경), P=1(교환 인덱스)

8, 5 (1, 2) p = 2

5, 4 (2, 3) p =3

4, 3 (3. 4) p = 4

if( i! = p)

2, 3, 5, 4, 8

final i = 2 (해당 위치 변경), P=2(교환 인덱스)

5, 4 (2, 3) p =3

4, 8 (3, 4)

if( i! = p)

2, 3, 4, 5, 8

final i = 3 (해당 위치 변경), P=3(교환 인덱스)

5, 8 (3, 4)

if( i! = p) x

p값은 (교환해야 될 인덱스) +1 씩 증가한다.

💡

for which문은 전체를 순환해서 전체 출력 할 때 사용

(완성된 코드 내부 for (int v : arr) { System.out.print(v + " "); })


package ex03;

public class SlectedEx01 {
    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 4, 3};
        final int N = arr.length;

        // 변경 해야될 위치 5 -> replace -> rep


        // 변경 해야될 위치 8 -> min -> min

        final int rep = 0;
        int i = rep;
        int min = rep;

       
        }

						 i=i+1; // 1
            if(arr[min] > arr[i]){ // 5, 8, 2, 4, 3
                min = i;
        }

        i=i+1; // 2
        if (arr[min] > arr[i]){// 5, 8, 2, 4, 3 -> min = 2
            min = i;

        }

        i=i+1; //3
        if (arr[min] > arr[i]){ // 5, 8, 2, 4, 3 -> min = 2
            min = i;
        }

        i=i+1; //4
        if (arr[min] > arr[i]){ // 5, 8, 2, 4, 3 -> min = 2
            min = i;
        }
        if (rep != min){
            int temp = arr[rep]; // temp = 5
            arr[rep] = arr[min];
            arr[min] = temp;
        }
    }

}


package ex03;

public class SlectedEx01 {
    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 4, 3};
        final int N = arr.length;

        // 변경 해야될 위치 5 -> replace -> rep


        // 변경 해야될 위치 8 -> min -> min

        final int rep = 0;
        int min = rep;

        for (int i = rep + 1; i < N; i++) {
            if(arr[min] > arr[i]){ // 5, 8, 2, 4, 3
                min = i;
        }


        if (rep != min){
            int temp = arr[rep]; // temp = 5
            arr[rep] = arr[min];
            arr[min] = temp;
        }
    }

}


package ex03; //완성된 코드

public class SlectedEx01 {
    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 4, 3};
        final int N = arr.length;
        int rep;
        int min;

        for (int j = 0; j < N - 1; j++) {
            rep = j;
            min = rep;

            for (int i = rep + 1; i < N; i++) {
                if (arr[min] > arr[i]) { // 5, 8, 2, 4, 3
                    min = i;
                }


                if (rep != min) {
                    int temp = arr[rep]; // temp = 5
                    arr[rep] = arr[min];
                    arr[min] = temp;
                }
            }
            for (int v : arr) {
                System.out.print(v + " ");

            }
        }
    }
}

See more posts

알고리즘

버블 정렬

정렬의 목적

선택 정렬

More articles

가비지 컬렉션

이진트리 서치(binary 서치)

2차원 배열

7.배열