정렬의 종류와 정의

정렬의 정의

---

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는것으로 검색을 효율적으로 만들거나 일련의 항목에 대한 병합을 효율적으로 할수 있게 해준다.

정렬의 종류

---

선택 정렬 (Selection Sort)

컴퓨터가 정렬을 할떄를 생각해보자. 무작위로 여러개가 있을때 이중 가장 작은 데이터를 선택해 맨 앞의 데이터와 바꾸고 그 다음 작은 데이터를 선택해 그 앞의 데이터와 바꾸고 한다면 어떨까? 이 방법이 바로 가장 원시적으로 매번 가장 작은것을 선택한다는 의미에서 선택 정렬(Selection Sort) 알고리즘이라 한다.

void selectSort(){
 int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

//전체를 검색해서 작은값과 시작점의 위치를 스왑 (전체검색 O(N'2) 의 복잡도) 
 for(int i = 0 ; i < arr.length; i++){
     int min = i;
     for(int j = i+1 ; j < arr.length; j++){
         if(arr[min] > arr[j]) min = j;
     }
     int temp  = arr[i];
     arr[i] = arr[min];
     arr[min] = temp;
  }
}

이처럼 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N-1 하면 정렬이 완료된다. 선택정렬은 빅오 표기법으로 O(N’2) 의 시간 복잡도를 가지고 앞에 나올 삽입정렬과 퀵정렬에 비해 데이터의 개수가 쌓이면 효율적이지 못하다.

삽입 정렬 (Insert Sort)

데이터를 하나씩 확인하며 각 데이터의 적절한 위치에 삽입하면 어떨까? 라는 접근에서 시작된 정렬이 삽입정렬이다. 삽입정렬은 직관적이고 이해하기 쉬운 편이지만 선택정렬에 비하면 구현난이도가 높은 편이다. 삽입정렬은 두번째 부터 시작한다 왜냐하면 이미 앞의 데이터는 정렬이 되있다고 가정하기 때문이다.

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

j 부터 0 으로 이동하면서 자기보다 작은값이 있으면 둘을 변경하고. 만약 작은 값이 없으면 탈출하는 구조다. 만약 운이 좋으면 O(N) 으로 끝날수도 있지만(대부분 정렬되있는 경우) 운이 나쁘면 O(N’2) 의 복잡도 까지 요구할 수 있다.

퀵정렬 (Quick Sort)

퀵 정렬은 정렬 알고리즘중에 가장 많이 사용되는 알고리즘이다. 퀵정렬과 비교할 만큼 빠른 정렬은 병합 정렬 알고리즘 정도가 있다. 기준 데이터를 정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까? 라는 접근에서 시작한 알고리즘으로 문제를 작은 2개의 문제로 분리하고 해결한 다음 다시 모아서 원래의 문제를 해결하는 전략을 사용한다.

void quicksort(int start,  int end){

   if(start > end) return;

   int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
   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(start, right-1);
    quicksort(right+1, end);
   }
}

1. 배열의 시작과 끝점 잡기
2. 시작점에 첫번째 값을 기준점(피벗) 으로 설정
3. 왼쪽은 시작점보다 하나 앞으로 끝점은 제자리에서 시작
4. 왼쪽에선 기준점 보다 큰값이 나올때 까지 이동
5. 오른쪽은 기준점 보다 작은값이 나올때 까지 이동
6. 왼쪽값이 오른쪽값을 지나쳤을 경우 기준값(피벗)과 오른쪽 값을 스왑
7. 아닐경우 왼쪽값과 오른쪽값을 스왑
8. 그 후에 반으로 갈라서 왼쪽영역은 시작값은 그대로 끝값(오른쪽값)만 하나씩 줄여서 재귀함수
9. 오른쪽 영역은 시작값(오른쪽값)을 하나씩 늘리며 끝값은 고정으로 하며 재귀함수

결론은 왼쪽에 기준값보다 작은값 정렬 , 오른쪽에 기준값보다 큰 값을 정렬해서 분할정복으로 해결하는 방법이다. 시간복잡도는 O(NlogN) 복잡도를 가지는데 최선의 경우는 피벗값의 위치가 변경되어 분할이 일어 날때마다 왼쪽 오른쪽을 정확히 절반씩 분할한다는 경우다. 하지만 최악의 경우는 O(N’2) 을 가진다. 앞에서 나온 삽입정렬의 경우 정렬이 되있는경우 시간이 줄어서 최선의 경우를 얻을수 있었지만 퀵정렬은 정렬이 되있는경우 오히려 매우 느리게 동작한다.