3. 정렬 알고리즘

개념

• 정의: 데이터를 특정 기준에 따라 순서대로 나열하는 것
• 언제 사용?: 데이터의 입력 순서가 문제 푸는 것에 의미가 없을때 사용
• 시간복잡도: O(NlogN)

 

요약

 

선택 정렬

• 정의: 처리되지 않은 데이터 중 가장 작은 데이터를 선택하여 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 방법
• 시간 복잡도: O(N^2)

    public static void selectSort(int[] List){

        int minIndex;
        for(int i=0; i<List.length - 1; i++){
            minIndex = i;

            for(int j=i+1; j<List.length; j++){
                if(List[minIndex] > List[j]){
                    minIndex = j;
                }
            }

            int temp = List[i];
            List[i] = List[minIndex];
            List[minIndex] = temp;
        }
    }

 

삽입 정렬

• 정의: 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 방법
• 시간 복잡도: O(N^2)
  • 단, 리스트가 거의 정렬이 되어있는 상태라면 매우 빠르게 동작
  • 리스트가 다 정렬된 경우 O(N)의 복잡도를 가짐

    public static void insertSort(int[] List){
        
        for(int i=1; i<List.length; i++){
            // 이미 정렬된 부분에서 적절한 위치를 찾아 삽입( 0~i )
            for(int j=i; j > 0; j--){
                //한 칸씩 왼쪽으로 이동
                if(List[j] < List[j - 1]){
                    int temp = List[j];
                    List[j] = List[j-1];
                    List[j-1] = temp;
                }
                //자기보다 작은 데이터 만나면 그 위치에서 멈춤
                else{
                    break;
                }
            }
        }
    }
}

 

 

퀵 정렬

• 정의: 기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
  • 가장 첫번째 데이터를 기준 데이터로 설정하는 것이 일반적
  • 오름차순의 경우
    • 왼쪽 포인터는(Left) 기준값 보다 큰 값을 선택
    • 오른쪽 포인터는(Right) 기준값 보다 작은 값을 선택
    • 두 값을 변경
    • 왼쪽 포인터와 오른쪽 포인터가 엇갈릴 때까지 반복 ( Left >= Right )
    • 기준값과 작은 값(Right)의 위치를 변경
    • 기준 값을 기준으로 데이터 묶음을 나누어 작업을 진행
• 시간 복잡도: O(N * LogN)
  • 하지만, 이미 정렬된 배열에 대해서 작업을 한다면 O(N^2) 복잡도가 발생

    public static void quickSort(int[] List, int left, int right){
        
        if(left >= right){
            return;
        }

        int pivot = left;
        left = pivot + 1;

        while(left <= right){

            while(left <= right && List[right] > List[pivot]){
                right--;
            }

            while(left <= right && List[left] < List[pivot]){
                left++;
            }

            if(left <= right){
                int temp = List[left];
                List[left] = List[right];
                List[right] = temp;
            }
        }

        int temp = List[pivot];
        List[pivot] = List[right];
        List[right] = temp;

        quickSort(List, left, pivot-1);
        quickSort(List,pivot+1, right);

    }

 

 

계수 정렬

• 정의: 특정 조건이 부합할 때만 사용 가능 하지만, 매우 빠르게 동작하는 정렬 알고리즘
  • 특정 조건: 데이터의 크기 범위가 제한 and 정수 형태로 표현 가능할 때
  • 방법
    • 가장 작은 데이터 부터 가장 큰 데이터까지 범위가 모두 담길 수 있는 리스트(List[K])를 생성
    • 데이터를 하나씩 확인하며, 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가
    • 리스트 첫 번째 데이터 부터 해당 값만큼 반복하여 인덱스 출력
• 시간 복잡도: O(N + K)
  • K는 데이터의 크기 범위
• 단점:공간 복잡도 또한 O(N + K) 이기 때문에, 때에 따라서 비효율성이 발생할 수 있음
• 따라서, 동일한 값을 가지는 데이터가 여러 개 등장할 때 가장 효율이 좋음

    public static void countingSort(int List[], int min, int max){

        int[] count  = new int[max - min + 1];

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

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

    }