Java

정렬

Dec 15, 2023
정렬
Contents
목적 : 데이터의 검색을 잘하기 위함버블 정렬(bubble sort)선택 정렬(Selection sort)삽입정렬(Insertion sort)퀵 솔트(Quick sort)이진 트리(Binary Tree)

목적 : 데이터의 검색을 잘하기 위함

기본 : 풀 스캔(O(N)) > 이진트리(O(logN))탐색 > b+트리
💡
알고리즘 : 컴퓨터가 따라 할 수 있도록 문제를 해결하는
절차나 방법을 자세히 설명하는 과정
알고리즘을 만드는 것 : 절차를 만드는 것
나중에 함수에 들어감
 

버블 정렬(bubble sort)

목표: 오름차순으로 정렬하는 것
서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
인접한 : 바로 옆에 있는 번지
두 원소 : 인덱스
💡
1회전에 가장 큰 수가 맨 뒤로 가는 것
반복되면서 오름차순으로 정렬됨
회전수 : (n-1)
1회전의 비교 횟수 : n-1 / 2회전의 비교 횟수 : n-2
3회전의 비교 횟수 : n-3 / 4회전의 비교 횟수 : n-4

연습문제

 
notion image
 
1) 첫번째 도전 4바퀴 돌기
2) 4바퀴 도는데 1회전때 4바퀴 도는 내부 for문 만들기
package ex03.test;

public class BubbleTest01 {
    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 4, 3};
        final int N = arr.length; //상수일 경우 이름을 대문자로 사용

        //1. 첫번째 도전 4바퀴 돌기
        for (int i = 0; i < N-1; i++) {
            //System.out.println("몇번돌지?");
        }
        //2. 4바퀴 도는데 1회전때 4바퀴 도는 내부 for문 만들기
        for (int i = 0; i < N-1; i++) {
            for (int j = 0; j < N-1; j++) {
                System.out.println("몇번돌지?");
            }

            System.out.println("");
        }
    }
}
notion image
3) 세번째 도전 4바퀴 돌고, 내부적으로 (4, 3, 2, 1) 바퀴 돌기
package ex03.test;

public class BubbleTest02 {
    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 4, 3};
        final int N = arr.length; //상수일 경우 이름을 대문자로 사용

        //3. 세번째 도전 4바퀴 돌고, 내부적으로 (4, 3, 2, 1)바퀴 돌기
        for (int i = 0; i < N-1; i++) {
            for (int j = 0; j < N - i - 1; j++) {

                System.out.println("몇번돌지?");
            }
            System.out.println("");
        }
    }
}
notion image
4-1) 1회전 연습하기
package ex03.test;

public class BubbleTest03 {
    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 4, 3};
        final int N = arr.length; //상수일 경우 이름을 대문자로 사용

        //4. 1회전 연습하기
            int temp;
            if(arr[0] > arr[1]) {
                temp = arr[0];
                arr[0] = arr[1];
                arr[1] = temp;
            }
        System.out.println(arr[0] + " " + arr[1]);

        if(arr[1] > arr[2]) {
            temp = arr[1];
            arr[1] = arr[2];
            arr[2] = temp;
        }
        System.out.println(arr[1] + " " + arr[2]);

        if(arr[2] > arr[3]) {
            temp = arr[2];
            arr[2] = arr[3];
            arr[3] = temp;
        }
        System.out.println(arr[2] + " " + arr[3]);

        if(arr[3] > arr[4]) {
            temp = arr[3];
            arr[3] = arr[4];
            arr[4] = temp;
        } 
        System.out.println(arr[3] + " " + arr[4]);

        for (int i = 0; i < 5; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}
notion image
4-2) 
package ex03.test;

public class BubbleTest04 {
    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 4, 3};
        final int N = arr.length; //상수일 경우 이름을 대문자로 사용

        //4. 1회전 연습하기
        int temp;
        for (int i = 0; i < N-1; i++) {
            if (arr[i] > arr[i+1]) {
                temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
        }
        for (int j = 0; j < 5; j++) {
            System.out.print(arr[j] + " ");
        }
    }
}
notion image
5)
package ex03.test;

public class BubbleTest05 {
    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 4, 3};
        final int N = arr.length; //상수일 경우 이름을 대문자로 사용

        //5. 모든 회전 후
        int temp;

        for (int k = 1; k < N; k++) {

            for (int i = 0; i < N-k; i++) {
                if (arr[i] > arr[i + 1]) {
                    temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
        }
        for (int j = 0; j < N; j++) {
            System.out.print(arr[j] + " ");
        }
    }
}
notion image
메서드를 이용한 완성본
package ex03;

public class BubbleEx01 {
    static void bubble(int[] arr){ //메서드
        final int N = arr.length; //상수일 경우 이름을 대문자로 사용
        
        int temp;

        for (int k = 1; k < N; k++) {

            for (int i = 0; i < N-k; i++) {
                if (arr[i] > arr[i + 1]) {
                    temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
        }
        for (int j = 0; j < N; j++) {
            System.out.print(arr[j] + " ");
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 4, 3};
        BubbleEx01.bubble(arr); //같은 클래스 안에 있을 경우 생략 가능

    }
}

디버깅하는 방법

위치 마우스로 잡아서 디버깅 시작
notion image
단계별로 확인하기
notion image
두세번 누르면 디버깅 완료
notion image
1회전 후 2회전 시작까지의 디버깅
notion image
notion image
notion image
notion image
notion image
notion image
notion image
notion image
notion image
 

선택 정렬(Selection sort)

목표: 오름차순으로 정렬하는 것
자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
💡
규칙
p는 항상 i에서 1씩 증가
회전수는 n에서 1씩 감소
회전수 : (n-1)

연습문제

notion image
 
1) 첫번째 도전 1회전때 4바퀴 도는코드 만들기
package ex03;

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

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

        final int rep = 0; // 0
        int i = rep; // 0
        int min = rep; // 0 알수 없으나 초기화는 자기 자리로 해놓는 것이 좋음 // 그대로 감
       
				// 1회전
        i = i + 1; // 1
        if(arr[min] > arr[i]){ // 5 > 8
                min = i;
        }

        i = i + 1; // 2
        if (arr[min] > arr[i]){ // 5 > 2
            min = i; // 2
        }
        i = i + 1; // 3
        if (arr[min] > arr[i]){ // 2 > 4
            min = i;
        }
        i = i + 1; // 4
        if (arr[min] > arr[i]){ // 2 > 3
            min = i;
        }
        if (rep != min){
            int temp = arr[rep]; // 5
            arr[rep] = arr[min]; // 2
            arr[min] = temp;
        }
    }
}
 
2) 1회전 내부for문으로 만들기
package ex03;

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

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

        final int rep = 0; // 0

        int min = rep; // 0 알수 없으나 초기화는 자기 자리로 해놓는 것이 좋음 // 그대로 감
			
				// 1회전
        for (int i = rep+1; i < 5; i++) {
            if (arr[min] > arr[i]) {
                min = i;
            }

            if (rep != min) {
                int temp = arr[rep];
                arr[rep] = arr[min];
                arr[min] = temp;
            }
        }
    }
}
 
3) 4회전 만들기
package ex03;

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

        int rep = 0; // 0
        int min = rep;

        // 1회전
        rep = 0;
        min = rep;
        for (int i = rep+1; i < 5; i++) {
            if (arr[min] > arr[i]) {
                min = i;
            }

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

        rep = 1; // 0
        min = rep;

        // 2회전
        for (int i = rep+1; i < 5; i++) {
            if (arr[min] > arr[i]) {
                min = i;
            }

            if (rep != min) {
                int temp = arr[rep];
                arr[rep] = arr[min];
                arr[min] = temp;
            }
        }
        
        rep = 1; // 0
        min = rep;
        // 3회전
        for (int i = rep+1; i < 5; i++) {
            if (arr[min] > arr[i]) {
                min = i;
            }

            if (rep != min) {
                int temp = arr[rep];
                arr[rep] = arr[min];
                arr[min] = temp;
            }
        }
    }
}
 
4) for문으로 간단히 만들기
package ex03;

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

        int rep = 0; // 0
        int min = rep;

        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]) {
                    min = i;
                }

                if (rep != min) {
                    int temp = arr[rep];
                    arr[rep] = arr[min];
                    arr[min] = temp;
                }
            }
        }
        for (int v : arr) { // 전체만 출력 가능
            System.out.print(v + " ");
        }
    }
}
notion image
 
 

삽입정렬(Insertion sort)

목표: 오름차순으로 정렬하는 것
자료 배열의 모든 요소를 앞에서부터 차례대로
이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써
정렬을 완성하는 알고리즘
💡
회전수 : (n-1)
1회전의 비교 횟수 : 1 / 2회전의 비교 횟수 : 2
3회전의 비교 횟수 : 3 / 4회전의 비교 횟수 : 4

연습문제

notion image
 
1) 막노동으로 규칙찾기
package ex03;

public class InsertedEx01 {
    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 4, 3};

        int target;
        int temp;

        // 1회전
        target = arr[1]; // 8
        if(arr[0] > arr[1]){
            temp = arr[0];
            arr[0] = arr[1];
            arr[1] = temp;
        }
        // 2회전
        target = arr[2];// 2
        if(arr[1] > arr[2]){
            temp = arr[1];
            arr[1] = arr[2];
            arr[2] = temp;
        }
        target = arr[1];
        if(arr[0] > arr[1]){
            temp = arr[0];
            arr[0] = arr[1];
            arr[1] = temp;
        }
        // 3회전
        target = arr[3];
        if(arr[2] > arr[3]) {
            temp = arr[2];
            arr[2] = arr[3];
            arr[3] = temp;
        }
        target = arr[2];// 2
        if(arr[1] > arr[2]){
            temp = arr[1];
            arr[1] = arr[2];
            arr[2] = temp;
        }
        target = arr[1];
        if(arr[0] > arr[1]){
            temp = arr[0];
            arr[0] = arr[1];
            arr[1] = temp;
        }
        // 4회전
        target = arr[4];
        if(arr[3] > arr[4]) {
            temp = arr[3];
            arr[3] = arr[4];
            arr[4] = temp;
        }
        target = arr[3];
        if(arr[2] > arr[3]) {
            temp = arr[2];
            arr[2] = arr[3];
            arr[3] = temp;
        }
        target = arr[2];
        if(arr[1] > arr[2]){
            temp = arr[1];
            arr[1] = arr[2];
            arr[2] = temp;
        }
        target = arr[1];
        if(arr[0] > arr[1]){
            temp = arr[0];
            arr[0] = arr[1];
            arr[1] = temp;
        }
    }
}
notion image
 
2) 코드 정리하기
package ex03;

public class InsertedEx02 {
    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 4, 3};

        int target;
        int temp;
        int N = arr.length;

        for (int i = 0; i < N-1; i++) {

            for (int j = 1; j < N; j++) {
                target = arr[j]; // 8

                if (arr[j - 1] > arr[j]) {
                    temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        for (int v : arr) { // 전체만 출력 가능
            System.out.print(v + " ");
        }
    }
}
notion image
 

퀵 솔트(Quick sort)

분할 정복 알고리즘의 하나
평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법
 
피벗을 선택하고, 피벗을 기준으로 좌우로 데이터를 나눈 후(분할), 각각에 대해 동일한 작업을 반복하여 정렬하는 방식
💡
quickSort(arr, 0, arr.length - 1); : 퀵 정렬 알고리즘을 구현한 메서드를 호출
arr : 정렬할 배열
0과 arr.length-1 : 각각 정렬할 배열의 시작과 끝 인덱스
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 4, 3, 10, 9, 13, 1};
        quickSort(arr, 0, arr.length - 1);

        for (int v : arr) {
            System.out.print(v + " ");
        }
    }

    public static void quickSort(int[] arr, int start, int end) {
        if (start >= end) return; // 원소가 1개인 경우 그대로
        int pivot = start; // 피벗 : 첫 번째 원소
        int left = start + 1;
        int right = end;

        while (left <= right) {
            // 피벗보다 큰 데이터를 찾을 때까지 반복
            while (left <= end && arr[left] <= arr[pivot]) left++;
            // 피벗보다 작은 데이터를 찾을 때까지 반복
            while (right > start && arr[right] >= arr[pivot]) right--;

            // 피벗을 기준으로 두 부분으로 나누는 과정이 완료 //작은 데이터와 피벗을 교체
            if (left > right) {
                int temp = arr[pivot];
                arr[pivot] = arr[right];
                arr[right] = temp;
            } else { // 아니면 작은 데이터와 큰 데이터를 교체
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        // 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
        quickSort(arr, start, right - 1);
        quickSort(arr, right + 1, end);
    }
}
예시)
package ex03;

import java.util.Arrays;
import java.util.List;

public class SortEx01 {
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList (5, 8, 2, 4, 3);

        list.stream().sorted();
    }
}

연습문

 
 

이진 트리(Binary Tree)

💡
가운데 값을 찾아가서 정리하고 다음 값부터 탐색
notion image
저장할 때부터 정렬을 잘해서 넣어야 함
시간 복잡도 * 검색 갯수
💡
랜덤 액세스 15%까지는 바이너리가 빠름
시간복잡도가 풀스캔과 바이너리가 같으면 동일
그 이상은 풀스캔이 더 좋음
 

연습문제

package ex03.test;

public class BinaryTest01 {
    public static void main(String[] args) {

        // N = 13
        // 시간복잡도 log2(N) -> log2(13) -> 3.700 (3과 4사이)
        // 이진 검색 => 반드시 정렬이 되어 있어야 한다.
        int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
        int N = arr.length;
        final int target = 9;
        int start = 0;
        int end = N - 1;
        int mid;

        // 1 회전
        mid = start + ((end - start) / 2); // 기대값 6

        if (arr[mid] == target) {
            System.out.println("1회전 : " + target + "값은 " + mid + "번지에 있습니다");
        }

        if (arr[mid] < target) { // 기대값 start 5, end 8
            start = mid + 1;
        }

        if (arr[mid] > target) {
            end = mid - 1;
        }

        System.out.println("1회전 start : " + start);
        System.out.println("1회전 end : " + end);

        // 2 회전
        mid = start + ((end - start) / 2); // 기대값 6

        if (arr[mid] == target) {
            System.out.println("2회전 : " + target + "값은 " + mid + "번지에 있습니다");
        }

        if (arr[mid] < target) { // 기대값 start 7, end 8
            start = mid + 1;
        }

        if (arr[mid] > target) {
            end = mid - 1;
        }

        System.out.println("2회전 start : " + start);
        System.out.println("2회전 end : " + end);

        // 3 회전
        mid = start + ((end - start) / 2); // 기대값 7

        if (arr[mid] == target) {
            System.out.println("3회전 : " + target + "값은 " + mid + "번지에 있습니다");
        }

        if (arr[mid] < target) { // 기대값 start 8, end 8
            start = mid + 1;
        }

        if (arr[mid] > target) {
            end = mid - 1;
        }

        System.out.println("3회전 start : " + start);
        System.out.println("3회전 end : " + end);

        // 4 회전
        mid = start + ((end - start) / 2); // 기대값 8

        if (arr[mid] == target) { // 찾음
            System.out.println("4회전 : " + target + "값은 " + mid + "번지에 있습니다");
        }

        if (arr[mid] < target) {
            start = mid + 1;
        }

        if (arr[mid] > target) {
            end = mid - 1;
        }

        System.out.println("4회전 start : " + start);
        System.out.println("4회전 end : " + end);

        System.out.println("시간복잡도 : " + Math.log(N) / Math.log(2));
    }
}
notion image
 
package ex03;

public class BinarySearch {
    public static void main(String[] args) {
        // N = 17
        // 시간복잡도 log2(N) -> log2(17) -> 4.x // 최악 5번
        // 이진 검색 => 반드시 정렬이 되어 있어야 한다.
        // 16 / 2*2*2*2*2 -> logn -> log16
        int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
        int N = arr.length;
        final int target = 8;
        int start = 0;
        int end = N - 1;
        int mid;

        int round = 1;
        while (true) {
            mid = start + ((end - start) / 2); // 기대값 6
            System.out.println("mid : " + mid);

            if (arr[mid] == target) {
                System.out.println(round + "회전 : " + target + "값은 " + mid + "번지에 있습니다");
                break;
            }

            if (arr[mid] < target) { // 기대값 start 5, end 8
                start = mid + 1;
            }

            if (arr[mid] > target) {
                end = mid - 1;
            }

            System.out.println(round + "회전 start : " + start);
            System.out.println(round + "회전 end : " + end);

            round++;
        }
        System.out.println("시간복잡도 : " + (Math.log(N) / Math.log(2)));
    }
}
notion image
 
시간 복잡도 : 일반 10진수를 지수로 표현해주는 것
최악의 경우 안에 나옴
💡
Math.log(N)/Math.log(2) :시간복잡도 표현
notion image
notion image
 
Share article

More articles

See more posts

객체 지향

December 18, 2023
객체 지향

가지치기

December 18, 2023
가지치기

배열

December 14, 2023
배열

반복문

December 14, 2023
반복문

vosw1

RSS·Powered by Inblog