정렬 알고리즘

• 선택 정렬 : 선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.
  비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n²) 만큼의 시간이 걸린다.
  • 주어진 리스트 중에 최솟값을 찾는다.
  • 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
  • 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
  • 소스
    void selectionSort(int[] list) {
        int indexMin, temp;
    
        for (int i = 0; i < list.length - 1; i++) {
            indexMin = i;
            for (int j = i + 1; j < list.length; j++) {
                if (list[j] < list[indexMin]) {
                    indexMin = j;
                }
            }
            temp = list[indexMin];
            list[indexMin] = list[i];
            list[i] = temp;
        }
    }
  • 이미지
    https://upload.wikimedia.org/wikipedia/commons/9/94/Selection-Sort-Animation.gif
    
    
    
• 버블 정렬 : 거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도(Θ(n²))가 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.
  • 예제
    
    55 07 78 12 42
    07 55 78 12 42  첫 번째 패스
    07 55 78 12 42
    07 55 12 78 42
    07 55 12 42 78  두 번째 패스
    07 55 12 42 78
    07 12 55 42 78
    07 12 42 55 78  세 번째 패스
    07 12 42 55 78  네 번째 패스
    07 12 42 55 78  다섯번째 패스
    07 12 42 55 78  정렬 끝
    
  • 소스
    public void bubbleSort(int a[]) {
            int size = a.length;
            for(int i=size-1; i>0; i--) {
                System.out.printf("\n버블 정렬 %d 단계 : ", size-i);
                for(int j=0; j<i; j++) {
                    if(a[j] > a[j+1]) {
                        swap(a,j,j+1);
                    }
                    System.out.printf("\n\t");
                    for(int v : a) {
                        System.out.printf("%3d ", v);
                    }
                }           
            }
            System.out.println();
        }
       public  void swap(int a[], int idx1, int idx2) {
            int temp = a[idx1];
            a[idx1] = a[idx2];
            a[idx2] = temp;
        }
• 삽입 정렬 : 삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
  선택 정렬이나 거품 정렬과 같은 같은 O(n²) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다.
  • 예제
    

    
  • 소스
    void insertionSort(int[] arr)
    {
    
       for(int index = 1 ; index < arr.length ; index++){
         
          int temp = arr[index];
          int aux = index - 1;
    
          while( (aux >= 0) && ( arr[aux] > temp) ) {
    
             arr[aux+1] = arr[aux];
             aux--;
          }
          arr[aux + 1] = temp;
       }
    }
• 합병 정렬 : https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC
• 기수 정렬 : https://ko.wikipedia.org/wiki/%EA%B8%B0%EC%88%98_%EC%A0%95%EB%A0%AC
• 버킷 정렬
• 셀 정렬 : 셸 정렬(영어: shell sort)은 가장 오래된 정렬 알고리즘의 하나이다. 이름은 1959년 이 방법을 발표한 창안자 도널드 셸의 이름을 따서 붙여졌다. 셸 정렬은 개념을 이해하고 구현하기는 쉬우나 시간복잡도 분석은 조금 복잡하다.
  https://ko.wikipedia.org/wiki/%EC%85%B8_%EC%A0%95%EB%A0%AC
  • 데이터를 십수 개 정도 듬성듬성 나누어서 삽입 정렬한다.
  • 데이터를 다시 잘게 나누어서 삽입 정렬한다.
  • 이렇게 계속 하여 마침내 정렬이 된다.
  • 셸 정렬에서 데이터를 나누는 값(이하 N)은 보통 전체에서 2로 나누는 값으로 진행한다. 그러나 3을 나누고 1을 더하는 경우가 더 빠르다고 알려져 있다. 즉 N/2 보다는 N/3+1이 더 빠르다.
    
    
• 힙 정렬 : https://ko.wikipedia.org/wiki/%ED%9E%99_%EC%A0%95%EB%A0%AC
• 퀵 정렬 : https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC