선택정렬

개념

선택 정렬은 말 그대로 현재 위치에들어갈 데이터를 찾아 선택하는 알고리즘. 데이터들을 비교하면서 정렬한다.

cf) 기본적으로 내가 정렬할 때 자주 사용했던 알고리즘인지 모르고 썻던 알고리즘이다.

알고리즘 구현

1.주어진 리스트에서 최소값을 찾는다.
2. 최솟값을 맨 앞 자리의 값과 교환한다.
3. 맨 앞자리를 제외한 나머지 값들 중 최소값을 찾아 위와 같은 방법으로 반복한다.

알고리즘 코드 구현

public class Selection_Sort {
 
	public static void selection_sort(int[] a) {
		selection_sort(a, a.length);
	}
	
	private static void selection_sort(int[] a, int size) {
		
		for(int i = 0; i < size - 1; i++) {
			int min_index = i;	
			
			// 최솟값을 갖고있는 인덱스 찾기 
			for(int j = i + 1; j < size; j++) {
				if(a[j] < a[min_index]) {
					min_index = j;
				}
			}
			
			// i번째 값과 찾은 최솟값을 서로 교환 
			swap(a, min_index, i);
		}
	}
	
	private static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	
}

선택정렬 알고리즘 한계

1. 시간복잡도가 O(N^2)이다
2. 안전 정렬이 아니다.

*안전 정렬이 아니라는 것은, 같은 수를 정렬할 때 기존의 정렬했던 순서와 다르다는 것을 의미한다.

삽입 정렬

개념

삽입 정렬은 현재 비교하고자 하는 traget과 그 이전의 원소들과 비교하며 자리를 swap 하는 정렬 방법이다.

선택정렬과 다르게 안정 정렬(stable sort) 이다.

알고리즘 구현

1. 현재 타겟이 되는 숫자와 이전 위치에 있는 원소들을 비교한다. (첫 번째 타겟은 두 번째 원소부터 시작한다.)
2. 타겟이 되는 숫자가 이전 위치에 있던 원소보다 작다면 위치를 서로 교환한다.
3. 그 다음 타겟을 찾아 위와 같은 방법으로 반복한다.

알고리즘 코드 구현

    public static void main(String[] args) throws IOException {

        int[] ary = {2,4,1,2,5,7,1};

        for(int i=1; i<ary.length;i++){

            int target = ary[i];
            int j = i-1;

            // target 보다 한칸 앞에 있는 대상과 비교
            // 비교시, target이 더 작다면, 비교대상 앞으로 한칸 이동
            
            while(j>=0 && target<ary[j]){

                ary[j+1]=ary[j];
                j--;
            }
            //비교대상이 나보다 작다면, 이전에 바꿧던 비교대상의 자리를 target이 차지해야함
            ary[j+1]=target;
        }
        for(int i=0;i<ary.length;i++){
            System.out.println(ary[i]);
        }
    }

알고리즘 장단점

>장점 
1. 추가적인 메모리 소비가 작다.
2. 안정정렬이 가능하다.

>단점
1. 역순에 가까울수록 비효율적이다.
2. 데이터 상태에 따라서 성능 편차가 매우 크다.

// 단점 1,2번은 거의 같은 말이라고 보다도 무방

• 시간복잡도는 O(N^2) 이다.
  Bubble Sort나 Selection Sort 와 이론상 같은 시간복잡도를 갖음에도 평균 비교 횟수에 대한 기대값이 상대적으로 적기 때문에 평균 시간복잡도가 O(N2) 인 정렬 알고리즘 중에서는 빠른편에 속하는 알고리즘이다.

거품정렬

개념

두 개의 인접한 원소를 비교하여 정렬하는 방식이다.

*cf) Bubble 이라는 이름이 붙었는지 찾아보니 정렬 과정에서 원소의 이동이 마치 거품이 수면위로 올라오는 것 같다고 해서 거품(Bubble) 이라는 이름이 붙었다고 한다.. 억지인듯하다.

알고리즘 구현

1. 앞에서부터 현재 원소와 바로 다음의 원소를 비교한다.
2. 현재 원소가 다음 원소보다 크면 원소를 교환한다.
3. 다음 원소로 이동하여 해당 원소와 그 다음원소를 비교한다.

알고리즘 코드 구현

가장 바깥 for문 (전체 배열 길이 -1) round 만큼 돔
안쪽 for 문 (전체 배열 길이 -i) 만큼 돔 //round 진행할 때마다 1번씩 덜 돌아야함.

        int[] ary = {2,4,1,2,5,7,1};

        for(int i=1; i<ary.length;i++){
            for(int j=0;j<ary.length-i;j++){
                if(ary[j]>ary[j+1]){
                    int temp = ary[j];
                    ary[j]=ary[j+1];
                    ary[j+1]=temp;
                }
            }
        }
        for(int i=0;i<ary.length;i++){
            System.out.println(ary[i]);
        }

알고리즘 장단점

>장점
1. 추가적인 메모리 소비가 작다.
2. 구현이 매우 쉽다.
3. 안장정렬이 가능하다.

>단점
1. 다른 정렬 알고리즘에 비해 교환 과정이 많아 많은 시간을 소비한다.

Reference

https://st-lab.tistory.com/168