43일차 (2) - java (버블정렬, 삽입정렬, 선택정렬)

Yohan·2024년 4월 22일

Java TIL

코딩기록

목록 보기

61/156

정렬

버블정렬의 개념이 가장 중요하다.
일반적으로 자바 내에 Arrays.sort() 를 사용

버블정렬

데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식

시간 복잡도는 O(N^2)으로 다른 정렬보다 느린 편

package day10.sort;

import java.util.Arrays;

public class BubbleSort {

    // swap연산 메서드
    private static void swap(int[] arr, int first, int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }

    public static void sort(int[] arr) {
        // 외부 loop에서는 비교 대상의 범위를 지정
        for (int i = arr.length - 1; i > 0; i--) {
            // [ 15, 42, 24, 33, 60 ]
            // 내부 loop에서는 양옆 데이터들의 크기를 지속 비교
            for (int j = 0; j < i; j++) {
                // 왼쪽 수가 더 크면 서로 자리를 바꿈
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }

    public static void main(String[] args) {

        int[] numbers = {33, 11, 9, 100, 5789, 1, -55};

        sort(numbers);
        System.out.println(Arrays.toString(numbers));
    }
}

선택정렬

대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬, 구현이 복잡하고 시간 복잡도도 버블정렬과 같아서 잘 사용하지 않는다.

package day10.sort;

import java.util.Arrays;

public class SelectionSort {

    // swap연산 메서드
    private static void swap(int[] arr, int first, int second) {
        int temp = arr[first];
        arr[first] = arr[second];
        arr[second] = temp;
    }

    // selection sort
    public static void sort(int[] arr) {

        // 최소값을 먼저 찾는다.
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i; // 최소값 인덱스 초기화

            for (int j = i + 1; j < arr.length; j++) { // 최소값 찾는 루프
                if (arr[j] < arr[min]) {
                    min = j; // 최소값 변경
                }
            }
            swap(arr, i, min); // 선택한값과 최소값 교환
        }

    }

    public static void main(String[] args) {


        int[] arr = {33, 11, 99, 1, 22, 88, 55, 44, 66, 77};

        sort(arr); // 정렬 수행

        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

}