정렬(버블, 선택, 삽입)

정렬(Sorting)

• 데이터를 정해진 순서대로 작은것부터 크게 혹은 큰것부터 작게 차례대로 나열하는 방법이다.

버블정렬

• 두 인접한 데이터를 비교해서 뒤에 데이터가 더 크다면 자리를 바꾸면서 교체하는 방식

import java.util.ArrayList;
import java.util.Collections;

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

        ArrayList<Integer> array = new ArrayList<>();

        array.add(5);
        array.add(4);
        array.add(3);
        array.add(2);
        array.add(1);


        for (int i = 0; i < array.size() - 1; i++) {
            boolean check = true;

            for (int j = 0; j < array.size() - 1 - i; j++) {

                if (array.get(j) > array.get(j + 1)) {
                    Collections.swap(array, j, j + 1);
                    check = false;
                }

            }
            if(check) break;
        }

        for (Integer integer : array) {
            System.out.println(integer);
        }
    }
}

선택정렬

• 주어진 데이터 중 최소값을 먼저 찾는다.
• 작은값을 맨앞에 데이터랑 계속 바꾸면서 최소값을 세팅해 나가는 정렬방법

public class MySelectSort {

    public static void main(String[] args) {

        ArrayList<Integer> array = new ArrayList<>();

        for (int i = 0; i < 100; i++) {
            array.add((int) (Math.random() * 100));
        }

        for (int i = 0; i < array.size()-1; i++) {

            for (int j = i + 1; j < array.size(); j++) {
                if (array.get(i) > array.get(j)) {
                    Collections.swap(array, i, j);
                }
            }

        }
        for (Integer integer : array) {
            System.out.println("integer = " + integer);
        }

    }

}

삽입정렬

• 인덱스가 두번째 부터 시작
• 인덱스 앞에 있는 데이터부터 검사해서 key값이더 작으면 뒤로 복사

import java.util.ArrayList;
import java.util.Collections;

public class MyInsertSort {

    public static void main(String[] args) {

        ArrayList<Integer> array = new ArrayList<>();

        for (int i = 0; i < 100; i++) {
            array.add((int) (Math.random() * 100));
        }

        for (int i = 0; i < array.size()-1; i++) {

            for (int j = i+1; j > 0; j-- ) {

                if (array.get(j) < array.get(j-1)) {
                    Collections.swap(array, j, j-1);
                } else {
                    break;
                }

            }

        }
        for (Integer integer : array) {
            System.out.println("integer = " + integer);
        }

    }

}