[알고리즘] 정렬1(버블,선택,삽입)

O(n^2)의 시간복잡도를 갖는 알고리즘(버블정렬, 선택정렬, 삽입정렬) 들과

그보다 좀 더 빠르고 효율적인 O(n logn)의복잡도를 갖는 알고리즘(병합정렬, 퀵정렬, 트리정렬)이 있다.

 

1. Bubble Sort(버블 정렬)

바로 그 다음 노드와 비교해가면서 가장 큰 값을 하나씩 뒤로 보내면서 뒤쪽부터 정렬한다.

버블 정렬은 정렬 방식이 마치 물 속에서 올라오는 물방울과 같다고 하여 버블 정렬이라는 이름이 붙여졌다.

버블 정렬

- 장점

구현이 간단하다.

데이터를 하나씩 비교하기 때문에 정밀한 비교가 가능하다.

 

- 단점

데이터를 하나씩 비교하기 때문에 비교 횟수가 많아지므로 시간이 오래 걸린다.

 

- 소스코드

public class BubbleSort {
    public int[] sol(int[] arr){
        int k= arr.length;//배열의 길이

        for(int i=0;i<k-1;i++){
            for(int j=0;j<k-1-i;j++){
                int temp;
                if(arr[j]>arr[j+1]){
                    temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
        return arr;
    }
}

 

2. 선택 정렬

선택정렬은 앞쪽부터 정렬하는 방식이다.

주어진 배열에서 가장 작은 최소값을 찾고 배열의 맨 앞의 값과 위치를 바꾸면서 정렬한다.

배열에서 최소값을 찾아야 하기 때문에 비교 횟수는 많지만 실제로 값을 바꾸는 교환횟수가 적다는 것이 특징이다.

선택 정렬

- 장점

구현이 간단하다

비교하는 횟수에 비해 교환하는 횟수가 적다.

 

-단점

데이터를 하나씩 비교하기때문에 시간이 오래 걸린다.

정렬된 상태에서 새로운 데이터가 추가되면 정렬 효율이 좋지 않다.

 

- 소스코드

public class SelectionSort {
    public int[] sol(int[] arr){

        int k= arr.length;//배열의 길이

        for(int i=0;i<k-1;i++){
            int temp, minIdx = i;
            for(int j=i+1;j<k;j++){
                if(arr[minIdx]>arr[j]){
                    minIdx = j;
                }
            }
            temp=arr[i];
            arr[i]=arr[minIdx];
            arr[minIdx]=temp;
        }
        return arr;
    }
}

 

3. 삽입 정렬

삽입 정렬은 버블 정렬의 비효율성을 개선하기 위해 등장한 방법이다.

두번째 인덱스부터 시작해서 자신의 앞에 있는 값들과 비교하여 적절한 위치를 찾아 넣어주는 형식으로 진행된다.

정렬을 위해 비교하는 범위 자체가 훨씩 적고, 이미정렬되어 있는 경우 앞에 노드보다 큰지 한번씩 밖에 비교를 하지 않아

시간 복잡도는 O(n)까지 줄어든다.

삽입 정렬

- 장점

입력으로 들어오는 배열의 원소가 정렬되어 있을수록 속도가 빠르다.

정렬된 값은 교환이 일어나지 않는다.

 

- 단점

삽입을 구현해야하므로 속도가 자료구조의 영향을 많이 받는다.

입력으로 들어오는 배열이 역순으로 정렬된 경우 성능이 굉장히 좋지 않다.

public class InsertSort {
    public int[] sol(int[] arr){
        int k=arr.length;
        for(int i=1;i<k;i++){
            int temp;
            for(int j=i;j>0;j--){
                if(arr[j-1]>arr[j]){
                    temp=arr[j-1];
                    arr[j-1]=arr[j];
                    arr[j]=temp;
                }
            }
        }
        return arr;
    }
}

 

*위의 세 정렬에 대한 성능표

반복문을 도는 횟수는 Bubble=Selection>=Insert

정렬 알고리즘	최적의 경우(오메가)	평균적인 경우(델타)	최악의 경우(빅오)
Bubble sort	n^2	n^2	n^2
Selection Sort	n^2	n^2	n^2
Insertion Sort	n	n^2	n^2

- 정리

버블정렬과 선택정렬은 단순하고 직관적이며, 구현이 쉽지만, 비효율적이므로 잘 사용하지 않는다.

삽입정렬은 정렬이 어느정도 되어있는 경우에 최소한의 비교와 연산이 이루어지므로, 성능이 좋아 사용된다.

 

- 프로그래머스 정렬 문제 [ H-Index ]

https://school.programmers.co.kr/learn/courses/30/lessons/42747

프로그래머스