정렬 알고리즘이란?

"이것이 취업을 위한 코딩 테스트다 with 파이썬" 내용을 기반으로 제작하였습니다.

(https://www.youtube.com/watch?v=KGyK-pNvWos&t=2349s)

 

 

정렬이란?

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

- 문제에 따라 적절한 정렬 알고리즘이 사용된다.

 

위와 같이 정렬되지 않은 수열을 정렬하려면 어떻게 해야될까 ?

 

정렬 알고리즘에는 크게 4가지가 있다.

 

1. 선택 정렬 

     - 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.

7

5

9

0

3

1

6

2

4

8

첫번째 단계에서는 0이 제일 작으므로 0과 7을 교환한다.

 

0

5

9

7

3

1

6

2

4

8

두번째 단계에서는 1이 제일  작으므로 5와 교환한다.

 

0

1

9

7

3

5

6

2

4

8

이렇게 단계를 진행해나가다 보면 결국 0부터 9까지 정렬이 된다.

 

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

 

소스코드

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
            for(int i=0;i<arr.length;i++){
                int min_idx = i;
                for(int j=i+1;j<arr.length;j++){
                    if(arr[min_idx] > arr[j]){
                        min_idx = j;
                    }
                }
                int temp = arr[i];
                arr[i] = arr[min_idx];
                arr[min_idx] = temp;
            }
        for (int num : arr) {
            System.out.print(num+" ");
        }
        }

}

 

2. 삽입 정렬

     - 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.

     - 선택 정렬보다 더 효율적으로 동작한다.

 

7

5

9

0

3

1

6

2

4

8

첫번째 단계에서는 5의 위치를 결정한다. 7의 오른쪽 or 왼쪽으로 가게 되는데 7보다 작기 때문에 7의 왼쪽으로 이동한다.

 

5

7

9

0

3

1

6

2

4

8

두번째 단계에서는 9의 위치를 정한다. 하지만 앞에 있는 두 개의 숫자보다 9가 더 크므로 위치를 변경하지 않는다.
(정확히는 바로 앞에 7보다 커서 바로 정렬을 멈춘다,)

 

이런식으로 정렬을 진행하면 0부터 9까지 정렬이 된다.

 

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

 

소스코드

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
            for(int i=1;i<arr.length;i++){
                for(int j=i;j>0;j--){
                    if(arr[j-1] > arr[j]){
                        int temp = arr[j];
                        arr[j] = arr[j-1];
                        arr[j-1] = temp;
                    }
                    else break;
                }

            }
        for (int num : arr) {
            System.out.print(num+" ");
        }
        }

}

 

3. 퀵 정렬

     - 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 변경

     - 프로그래밍 언어의 정렬 라이브러리의 근간

     - 보통 첫 번째 데이터를 기준(pivot)으로 한다.

 

5

7

9

0

3

1

6

2

4

8

첫번째 단계에서는 5를 기준으로 한다. 

그렇다면 왼쪽에서부터 7은 5보다 크기에 선택되고 , 오른쪽에서부터의 4는 5보다 작기에 선택된다.

이제 둘의 위치를 바꾼다.

5

4

9

0

3

1

6

2

7

8

이제 쪽에서부터 9는 5보다 크기에 선택되고 , 오른쪽에서부터의 2는 5보다 작기에 선택된다.

다시 둘의 위치를 바꾼다.

 

이렇게 진행하다보면 데이터의 위치가 엇갈리는 순간이 올것이다.

그때 작은 데이터와 피벗값의 위치를 변경한다

 

1

4

2

0

3

5

6

9

7

8

이렇게 되면 왼쪽 데이터는 5보다 작고 , 오른쪽 데이터는 5보다 크다.

이처럼 피벗을 기준으로 데이터를 나누는 것을 분할이라고 한다.

 

앞에서 진행했던 것처럼 분할된 데이터에서 다시 퀵정렬을 적용하면 된다.

 

시간복잡도 : 일반적으로 O(NlogN) , 최악의 경우 O(N^2)

 

소스코드

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
        quickSort(arr,0,arr.length-1);
        for (int num : arr) {
            System.out.print(num+" ");
        }
        }

        public static void quickSort(int[] arr,int start,int end){
            if(start >= end) return;

            int pivot = start;
            int left = start+1;
            int right = end;

            while (left <= right){
                while (left <= end && arr[left] <= arr[pivot]) left++;
                while(right > start && arr[right] >= arr[pivot]) right--;

                if(left > right){
                    int temp = arr[pivot];
                    arr[pivot] = arr[right];
                    arr[right] = temp;
                }
                else{
                    int temp = arr[left];
                    arr[left] = arr[right];
                    arr[right] = temp;
                }
            }
            quickSort(arr,start,right-1);
            quickSort(arr,right+1,end);
        }

}

 

4. 계수 정렬

    - 특정한 조건이 부합할 때만 매우 빠르게 동작한다.

    - 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을때만 가능하다.

 

0

0

0

0

0

0

0

0

0

0

먼저 크기가 0 인 배열을 만들어준다.

 

7

7

1

1

2

2

3

3

4

5

만약 이런 배열이 있다면 각각의 데이터가 나오는 숫자를 카운팅하고 배열에 집어 넣는 다면 효과적일 것이다.

 

먼저 만든 0 배열에 적용시켜보자

0

2

2

2

1

1

0

2

0

0

숫자들이 등장한 횟수만큼 배열에 플러스를 해주어 넣어주었다.

 

이제 이것을 그대로 출력해주면 된다.

 

이 알고리즘은 최악의 경우에도 O(N+K)를 보장하지만 경우에 따라선 최악의 효율을 낼 수도 있다.

ex) 0과 9밖에 데이터가 없는 경우에는 데이터가 두 개밖에 없는 데 크기가 10인 배열을 만들어서 정렬해야한다.

 

따라서, 동일한 값이 여러개일 경우 효과적으로 작동할 수 있다.

 

소스코드

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

        int[] sort = new int[arr.length+1];

        for(int i=0;i<arr.length;i++){
            sort[arr[i]] ++;
        }

        for(int i=0;i<sort.length;i++){
            for(int j=0;j<sort[i];j++){
                System.out.print(i+" ");
            }
        }
        }

}