알고리즘 - 정렬

정렬

---

Selection Sort

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

• 수행시간: O(n^2)
• 구현 with JAVA

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]의 자리를 바꿔준다.
    }
}

Bubble Sort

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

• 수행시간: O(n^2)
• 구현 with JAVA

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]의 자리를 바꿔준다.
        }
    }
}

 

Insertion Sort

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

• 수행시간
  • 이미 정렬되어 있을 때: 자리 변경 없이 비교만 이뤄 지므로 O(n)
  • 역순으로 정렬되어 있을 때: 2중 루프를 사용해 모든 비교를 해주어야 하므로 O(n^2)
  • 평균 O(n^2)
• 구현 with JAVA

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;
    }
}

• 수행시간
  • 이미 정렬되어 있을 때: 배열이 계속 불균등하게 나누어 지므로 n번 호출된다. O(n^2)
  • 평균 O(nlogn)
• 구현 with JAVA

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;
}

 

reference

roytravel.tistory.com/37