[Algorithm] 정렬(1) - 선택정렬, 버블정렬 with Java

정렬

정렬은 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.

실제 프로그램 코드 작성시 서버에서 데이터를 정렬해서 주긴 하지만 클라에서도 오름차순, 내림차순 관련하여 코드를 정리할 필요가 굉장히 많았다. 그러다보니 정렬 알고리즘에 관해 어느 정도 지식이 있다면 정말 큰 도움이 될 것이다!! 각 언어마다 제공해주는 정렬 메소드가 있겠지만 직접 구현하다 보면 실력도 늘지 않을까?!

선택 정렬

매번 가장 작은 것을 선택한다.

 

이테코로 공부하고 있는데 이 말이 정말 기억하기 쉬운 것 같다.

데이터가 여러개 있는 경우 매번 작은 것을 선택해서 넣어야 할 위치에 있는 데이터와 바꿔주는 것만 하면 된다.

선택 정렬

직접 그려본 선택정렬!

2,3,5,1,0,4 이렇게 데이터가 무작위로 놓여져 있다.

 

(1) - 먼저, 데이터 중 가장 작은 데이터를 찾는다. 바로 '0'

그 뒤 넣어야 할 위치에 있는 데이터 '2'와 자리를 바꿔 준다.

 

(2) - 정렬 된 '0'을 제외한 나머지 데이터 중 가장 작은 데이터를 찾는다. 바로 '1'

마찬가지로 넣어야 할 위치에 있는 데이터 '3'과 자리를 바꿔 준다.

 

(3)...마지막 까지 동일하게 반복해주면

0, 1, 2, 3, 4, 5 로 오름차순 정렬이 이루어진다.

내림차순은 반대로 가장 큰수를 뒤에서 부터 바꿔주면 될 것이다!

시간복잡도

선택 정렬의 경우 N-1번 동안 가장 작은 수를 찾아 맨 앞으로 보내는 과정이 이루어진다.

즉, 연산 횟수는 N + (N-1) + (N-2)....+2 까지

이를 표현하자면 N*(N+1)/2 번의 연산을 수행한다.

 

시간복잡도 : O(N^2)

	최선	평균	최악
선택 정렬	n^2	n^2	n^2

특징 - 제자리 정렬 &  불안정성

제자리 정렬

선택 정렬의 경우 기존 배열 그대로 사용하기 때문에 추가적인 메모리가 필요하지 않는다.

불안정성

단순 숫자 비교가 아니라 object에 있는 한 원소로 비교할 때

예) Person('철수',6) Person('영희',6)

기존에 있던 순서가 보장되지 않고 바뀔 수 있기 때문에 불안전성을 가지고 있다. -> 정렬되지 않은 것들 중 가장 작은 값을 반복문을 통해 다시 재배치 하기 때문! 

Person('철수',6), Person('영희',6) 이 -> Person('영희',6), Person('철수',6)으로 변하는 것.

내가 이해한 것은 이거다!

코드

class Selection Sort{
    public static void main(String[] args) {
       int[] array = {2,3,5,1,0,4};

       for(int i=0; i<array.length-1; i++){
        
            int min = Integer.MAX_VALUE;
            int index = 0;
            int tmp = array[i];
            for(int j=i; j<array.length; j++){
                if(array[j] < min){
                    index = j;
                    min = array[j];
                }
            }
            array[i] = array[index];
            array[index] = tmp;   
       }
       System.out.println(Arrays.toString(array));
    }
}

버블 정렬

옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내보자!

 

위 한줄이 버블 정렬을 잘 설명하는 말이다.

현재 위치에서 오른쪽에 있는 것과 비교해가며 작은 것을 앞으로 오게끔 반복해주면 된다.

계속 반복하면 결국 제일 큰 부분이 맨 오른쪽에 위치하기 때문에 그 부분을 제외하고 다시 처음부터 비교하며 변경하면 된다.

선택 정렬과 마찬가지로 스왑을 사용하여 정렬해준다.

버블정렬

1) 먼저 3과 1을 비교해 3이 더 크기때문에 1과 3의 위치를 바꿔준다.

2) 다음 3과 4를 비교해 4가 더 크기 때문에 그대로 둔다.

3) 4와 0을 비교해 4가 더 크기 때문에 0과 4의 위치를 바꿔준다.

쭈욱 반복해주고

끝까지 도달하면 결국 가장 큰 수인 4가 맨 끝에 위치하게 된다.

그 뒤 4를 제외하고 나머지도 비교해준다! 간단쓰

코드

public class BubbleSort {
    
    public static void main(String[] args){
        int[] array = {3,1,4,0,2};
        
        for(int i = 0; i < array.length; i++){
            for(int j=0; j < (array.length-i); j++){
                if(j != (array.length-1)){
                    if(array[j] > array[j+1]){
                        int tmp = array[j+1];
                        array[j+1] = array[j];
                        array[j] = tmp;
                    }
                }
            }    
        }
        System.out.println(Arrays.toString(array));
    }
}

시간복잡도

버블정렬의 경우에도 선택 정렬과 동일한 연산 횟수를 가진다.

즉, 연산 횟수는 N + (N-1) + (N-2)....+2 까지

이를 표현하자면 N*(N+1)/2 번의 연산을 수행한다.

 

시간복잡도 : O(N^2)

	최선	평균	최악
버블 정렬	n^2	n^2	n^2

특징 - 제자리 정렬 &  불안정성

제자리 정렬

버블 정렬의 경우 기존 배열 그대로 사용하기 때문에 추가적인 메모리가 필요하지 않는다.

안정성

같은 숫자의 데이터를 가진 객체더라도 클 경우에 그대로 유지시키기 때문에 순서가 변하지 않는다.