[JAVA] - 정렬 (버블, 삽입, 선택)

[JAVA] - 정렬 (버블, 삽입, 선택)

정렬 종류

버블 정렬

두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 알고리즘

오름차순 기준으로 한 회전 당 제일 큰 값을 뒤로 보낸다.

선택 정렬

주어진 데이터 중, 최솟값을 찾아 맨 앞에 위치한 값과 교체 하는 알고리즘

교체 마다 시작 인덱스를 증가 시킨다.

public class Chap01 { public static void main(String[] args) { int[] a = {20, 35, 10, 6, 94, 1}; int[] b = {20, 35, 10, 6, 94, 1 }; Chap01 main = new Chap01(); System.out.println("Bubble Sort" +main.bubbleSort(a)); System.out.println("Insert Sort" + main.selectSort(b)); } private String bubbleSort(int[] a) { for (int i = 0; i < a.length; i++) { for (int j = 0; j < a.length -i -1; j++) { if (a[j] > a[j+1]) { swap(a,j,j+1); } } System.out.println(Arrays.toString(a)); } return Arrays.toString(a); } private String selectSort(int[] a) { for (int i = 0; i < a.length-1; i++) { for (int j = i+1; j a[j]) { swap(a, i, j); } } System.out.println(Arrays.toString(a)); } return Arrays.toString(a); } private void swap(int a[], int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } } [출력] 1회전 : [20, 10, 6, 35, 1, 94] 2회전 : [10, 6, 20, 1, 35, 94] 3회전 : [6, 10, 1, 20, 35, 94] 4회전 : [6, 1, 10, 20, 35, 94] 5회전 : [1, 6, 10, 20, 35, 94] 6회전 : [1, 6, 10, 20, 35, 94] Bubble Sort : [1, 6, 10, 20, 35, 94] 1회전 : [1, 35, 20, 10, 94, 6] 2회전 : [1, 6, 35, 20, 94, 10] 3회전 : [1, 6, 10, 35, 94, 20] 4회전 : [1, 6, 10, 20, 94, 35] 5회전 : [1, 6, 10, 20, 35, 94] Select Sort : [1, 6, 10, 20, 35, 94]

삽입 정렬

현재 비교하고자 하는 타겟과 그 이전의 원소들과 비교하며 자리를 교환하는 알고리즘

데이터를 비교하면서 찾기 때문에 비교정렬, 또는 추가적인 공간이 필요없어 제자리 정렬로 부르기도 한다.

private String insertSort(int[] a) { for (int i = 1; i < a.length; i++) { int target = a[i]; int j = i - 1; while (j >= 0 && target < a[j]) { a[j + 1] = a[j]; j--; } a[j+1] = target; System.out.println(i+"회전 : "+Arrays.toString(a)); } return Arrays.toString(a); } [출력] 1회전 : [20, 35, 10, 6, 94, 1] 2회전 : [10, 20, 35, 6, 94, 1] 3회전 : [6, 10, 20, 35, 94, 1] 4회전 : [6, 10, 20, 35, 94, 1] 5회전 : [1, 6, 10, 20, 35, 94] Insert Sort : [1, 6, 10, 20, 35, 94]

버블 , 선택 정렬과는 다르게 최선의 경우 O(N)의 시간복잡도를 갖는다.

역순에 가까울 수록 비효율적이며 최악은 O(N^2)의 시간복잡도를 갖는다.

즉, O(N^2)을 갖는 버블, 선택, 삽입 정렬중에선 가장 빠른 알고리즘이다.

from http://sasca37.tistory.com/102 by ccl(A) rewrite - 2021-10-15 13:02:18