CS/알고리즘

알고리즘 - 정렬

빈둥벤둥 2021. 2. 13. 21:48

정렬


Selection Sort

    • 최소 원소를 찾아 맨 왼쪽 원소와 교환하고 맨 왼쪽 원소를 제외한다. 하나의 원소가 남을 때까지 반복한다. 
    • 장점: 정렬을 위한 비교 횟수는 많으나 교환 횟수가 적어 교환이 많이 이루어져야 하는 상태에서 효율적으로 사용할 수 있다.(역순 정렬일때 가장 효율적이다.)
    • 단점: 이미 정렬된 상태에서 자료가 추가되면 재정렬할때 최악의 처리 속도를 보인다. 

    • 수행시간: O(n^2)
    • 구현 with JAVA
1
2
3
4
5
6
7
8
9
public void selectionSort(int[] arr) {
    for(int i = 0; i < arr.length - 1; i++) {
        min = i;
        for(int j = i + 1; j < arr.length; j++) {
           if(a[min] > arr[j]) min = j;
        }
       arr[i]와 arr[min]의 자리를 바꿔준다.
    }
}
cs

 

Bubble Sort

    • 인접한 바로 옆 원소와 비교하며 자리를 바꾼다. 
    • 장점: n개 원소에 대해 n개의 메모리를 사용하기에 데이터를 하나씩 정밀하게 비교할 수 있다.
    • 단점: 언제나 O(n^2)이라는 시간 복잡도를 가진다. 즉 언제나 모든 수를 다 비교해야 한다.

    • 수행시간: O(n^2)
    • 구현 with JAVA
1
2
3
4
5
6
7
8
public void bubbleSort(int[] arr) {
    for(int i = 0; i < arr.length; i++) {
        for(int j = 0; j < arr.length - 1 - i; j++) {
            if(arr[j] > arr[j + 1]) 
                arr[j]와 arr[j + 1]의 자리를 바꿔준다.
        }
    }
}
cs

 

Insertion Sort

    • 자신보다 앞의 원소들을 비교해 적절한 위치를 찾은후 해당 위치에 원소를 넣고 나머지 원소들을 뒤로 밀어준다.
    • 장점: 이미 정렬되어 있을 경우 O(n)이라는 효율성을 가지고 있다. 버블 정렬과 달리 정렬된 값은 다시 비교하지 않는다. 
    • 단점: 데이터의 상태와 크기에 따라 성능의 편차가 크다. 역순 정렬일 때 O(n^2)이다.

    • 수행시간
      • 이미 정렬되어 있을 때: 자리 변경 없이 비교만 이뤄 지므로 O(n)
      • 역순으로 정렬되어 있을 때: 2중 루프를 사용해 모든 비교를 해주어야 하므로 O(n^2)
      • 평균 O(n^2)
    • 구현 with JAVA
1
2
3
4
5
6
7
8
9
public void insertionSort(int[] arr) {
    for(i = 1; i < arr.length; i++) { //이전 원소와 비교해야 하므로 1부터 시작
        int temp = arr[i];
        for(j = i - 1; j >= 0 && temp < arr[j]; j--) {
            arr[j + 1] = arr[j]; //값을 하나씩 뒤로 밀어준다.
        }
        arr[j + 1] = temp;
    }
}
cs

 

Merge Sort

  • 분할 정복법. 데이터가 저장된 배열을 절반으로 나누고 각각을 순환적으로 정렬한다. 정렬된 두 개의 배열을 합쳐 전체를 정렬한다. 
  • 장점: 기준값 설정하는 과정 없이 무조건 절반으로 분할하기에 기준값에 따라 성능이 달라지는 경우가 없다.
  • 단점: 배열을 합치는 과정에서 추가적인 메모리가 필요하다.
    • 수행시간: O(nlogn)
    • 구현 with JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public void mergrSort(int[] arr, int l, int r) {
    if(l < r) {
        int m = (l + r) / 2;
       mergeSort(arr, l, m);
       mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}
public void merge(int[] arr, int l, int m, int r) {
    int[] mergeArr = new int[arr.length];
    int s1 = l; //첫 번째 merge할 배열의 시작 인덱스
    int s2 = m + 1//두 번째 merge할 배열의 시작 인덱스
    int idx = l; // mergeArr에 값을 저장할때 사용할 인덱스
 
    while(s1 <= m && s2 <= r) {
        if(arr[s1] <= arr[s2]) mergeArr[idx++= arr[s1++];
        else mergeArr[idx++= arr[s2++];
    }
    while(s1 <= m) { //첫 번째 배열이 남은 경우 남은 배열을 적재해 준다.
        mergeArr[idx++= arr[s1++];
    }
    while(s2 <= r) { //두 번째 배열이 남은 경우 남은 배열을 적재해 준다.
        mergeArr[idx++= arr[s2++]; 
    }
        
    for(int i = l; i <= r; i++) { //merge한 값을 arr에 전달해준다.
        arr[i] = mergeArr[i];
    }
}
cs

 

Quick Sort

  • 분할 정복법. 기준(pivot) 원소를 정한 후 기준 앞 부분에는 기준보다 작은 원소가, 기준 뒤 부분에는 기준보다 큰 원소가 위치하도록 두 부분으로 나누고 각 부분을 순환적으로 정렬한다.
  • 장점: 분할 후 합병을 위해 추가 저장 공간이 필요하지 않다.
  • 단점: 기준값에 따라 시간복잡도가 크게 달라진다. 이상적인 기준값을 선택했다면 항상 절반씩 분할이 되어 O(nlogn)이 되지만 이미 정렬되어 있을 경우 항상 불균등하게 나누어 지므로 시간복잡도도 O(n^2)이 된다.
    • 수행시간
      • 이미 정렬되어 있을 때: 배열이 계속 불균등하게 나누어 지므로 n번 호출된다. O(n^2)
      • 평균 O(nlogn)
    • 구현 with JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void quickSort(int[] arr, int l, int r) {
    if(l < r) {
        int m = partition(arr, l, r);
        quickSort(arr, l, m - 1); //pivot 기준으로 왼쪽 부분 정렬
        quickSort(arr, m + 1, r); //pivot 기준으로 오른쪽 부분 정렬
    }
}
public int partition(int[] arr, int l, int r) {
    int pivot = arr[(l + r) / 2]; //기준값을 중앙값으로 설정
    while(l < r) {
        while(arr[l] < pivot) l++;
        while(arr[r] > pivot) r--;
        if(l < r) arr[l]과 arr[r]의 자리를 바꾼다.
    }
    return l;
}
cs

 

Radix Sort

  • n개의 d자리의 정수들을 가장 낮은 자리수부터 정렬한다.
  • 장점: O(n)이라는 빠른 시간복잡도를 갖는다.
  • 단점: 숫자 만큼 추가 메모리가 필요하다. 
  • 수행시간: O(dn) (d는 자리수 의미).

 

reference

roytravel.tistory.com/37