본문 바로가기

알고리즘 자료구조

[자료구조와 함께 배우는 알고리즘 입문] 6.정렬 알고리즘(2)

728x90

3. 단순 선택 정렬

 

3-1. 단순 선택 정렬 알아보기

가장 작은 요소는 맨 앞으로, 두 번째로 작은 요소는 맨 앞에서 두 번째로 이동하고 그 다음으로 작은요소, 또 그 다음으로 작은요소를 옮겨주면서 정렬해주는 알고리즘이다.

쉽게 표현하면 아래와 같은 과정을 통해 정렬을 시키는 것이다.

 

 

3-2. 단순 선택 정렬 적용

static void swap(int[] a, int idx1, int idx2){
        int temporay = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = temporay;

        //idx1의 데이터 값을 임시 변수에 저장하고
        //idx1과 idx2데이터 교환
    }
    static void selectionSort(int[]a, int n){
        for (int i = 0; i < n-1; i++) {
            int min = i;
            for (int j = i+1; j < n; j++) {
                if(a[j]<a[min]){
                    min = j;
                }
            }
            swap(a,i,min);
        }   
    }

 

 

4. 단순 삽입 정렬

 

4-1. 단순 삽입 정렬 알아보기

선택한 요소를 알 맞은 위치에 집어넣는 과정을 반복하면서 정렬하는 알고리즘이다.

배열의 정렬 과정을 표기하면 아래와 같다.

 

그러니까 선택한 데이터 값을 배열의 데이터 값과 비교해가면서 해당 데이터보다 작은 데이터와 큰 데이터 사이에 집어넣어주어야 하는 것이다.

 

 

4-2. 단순 삽입 정렬 적용

static void insertSort(int[] arr, int length){
        for (int i = 0; i < length; i++) {
            int j;
            int tmp = arr[i];
            for (j=i;j>0&& arr[j-1]>tmp;j--){
                arr[j] = arr[j-1];
            }
            arr[j] = tmp;
        }
    }

 

4-3. 단순 정렬의 시간 복잡도

단순 삽입, 단순 선택 정렬, 그리고 버블 정렬의 시간 복잡도는 모두 O(n²)로 효율성이 떨어지는 알고리즘이다.

 

 

 

5.  셸 정렬

 

5-1. 단순 삽입 정렬 특징 살펴보기

단순 삽입 정렬은 정렬이 이미 되어있거나 정렬하기 위해 거쳐야 하는 과정이 비교적 적은 경우 정렬 속도가 빠르지만, 그렇지 않은 경우에는 이동 횟수가 많아 효율적이지 못하다.

 

5-2. 셸 정렬 알아보기

셸 정렬은 위의 단순 삽입 정렬의 장점은 흡수하고 단점은 보완한 정렬 알고리즘이다.

일정 간격으로 떨어져있는 요소를 그룹으로 묶어 정렬을 하고, 간격을 좁혀 그룹을 줄이면서 정렬을 반복한다.

여러 그룹으로 나누어 정렬하면서 정렬 횟수는 늘지만, 전체적으로 데이터의 이동횟수가 줄어 효율적으로 정렬이 가능하다.

 

5-3. 셸 정렬 적용

 static void shellSort(int[] arr, int length){
        for (int i = length/2; i >0 ; i/=2) {
            for (int j = i; j < length ; j++) {
                int h;
                int temp = arr[j];
                for (h = j-i; h>=0 && arr[h]>temp ; h-=j){
                    arr[j+h] = arr[h];
                }
                arr[j+h] = temp;
            }
        }
    }
728x90