자바 프로그래밍 면접 이렇게 준비한다 - (Sort)

• Bubble sort
  1. 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다. 선택 정렬과 기본 개념이 유사하다.

     

     • 버블 정렬(bubble sort) 알고리즘의 특징
       • 장점
         1. 구현이 매우 간단하다.
       • 단점
         1. 순서에 맞지 않은 요소를 인접한 요소와 교환한다.
         2. 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
         3. 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난
       • 일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다. 버블 정렬(bubble sort)의 시간복잡도
  • • 장점
      1. 안정한 정렬 방법
      2. 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다.
      3. 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.
    • 단점
      1. 비교적 많은 레코드들의 이동을 포함한다.
      2. 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다.
  • 삽입정렬
    • 삽입 정렬(insertion sort) 알고리즘 개념 요약
      1. 손안의 카드를 정렬하는 방법과 유사하다.
         1. 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입한다.
         2. 새로 삽입될 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다.
      2. 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
      3. 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다. 
    • 삽입 정렬(insertion sort) 알고리즘의 구체적인 개념
      
      • 삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
      • 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.
      • 처음 Key 값은 두 번째 자료부터 시작한다.

        

  • 삽입 정렬(insertion sort) 알고리즘 특징
    • 장점
      1. 안정한 정렬 방법
      2. 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다.
      3. 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.
    • 단점
      1. 비교적 많은 레코드들의 이동을 포함한다.
      2. 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다.
  • 퀵정렬
    • 퀵 정렬(quick sort) 알고리즘의 개념 요약 
      • ‘찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)’가 개발한 정렬 알고리즘
      • 퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬 에 속한다.
      • 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법
        1. 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다.
      분할 정복(divide and conquer) 방법
      • 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
      • 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.
      과정 설명
      1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
      2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)
      3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
         1. 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
         2. 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
      4. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다. 리스트의 크기가 0이나 1이 될 때까지 반복한다.

      

  •  
  퀵 정렬(quick sort) 알고리즘의 구체적인 개념
  • 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
  • 퀵 정렬은 다음의 단계들로 이루어진다.
    1. 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
    2. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
    3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다. 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

    

    
    
    • 장점
      1. 속도가 빠르다.
         1. 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
      2. 추가 메모리 공간을 필요로 하지 않는다.
         1. 퀵 정렬은 O(log n)만큼의 메모리를 필요로 한다.
    • 단점
      1. 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
    • 퀵 정렬의 불균형 분할을 방지하기 위하여 피벗을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택한다.
      • EX) 리스트 내의 몇 개의 데이터 중에서 크기순으로 중간 값(medium)을 피벗으로 선택한다.
    • 병합정렬
      • ‘존 폰 노이만(John von Neumann)’이라는 사람이 제안한 방법
      • 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복 알고리즘의 하나 이다.
        • 분할 정복(divide and conquer) 방법
          1. 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
          2. 분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.
      • 과정 설명
        1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
        2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
        3. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
        4. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
      합병 정렬(merge sort) 알고리즘의 구체적인 개념
      • 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
      • 합병 정렬은 다음의 단계들로 이루어진다.
        1. 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
        2. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
        3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
      • 합병 정렬의 과정
        1. 추가적인 리스트가 필요하다.
        2. 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.
        3. 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계 이다.

        

      합병 정렬(merge sort) 알고리즘의 예제
      • 배열에 27, 10, 12, 20, 25, 13, 15, 22이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.
      • 2개의 정렬된 리스트를 합병(merge)하는 과정
        1. 2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트(sorted)로 옮긴다.
        2. 둘 중에서 하나가 끝날 때까지 이 과정을 되풀이한다.
        3. 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 값들을 전부 새로운 리스트(sorted)로 복사한다.
        4. 새로운 리스트(sorted)를 원래의 리스트(list)로 옮긴다.

      

      
      
      • 단점
        • 만약 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다.
          • 제자리 정렬(in-place sorting)이 아니다.
        • 레크드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.
      • 장점
        • 안정적인 정렬 방법
          • 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. (O(nlog₂n)로 동일)
        • 만약 레코드를 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
          • 제자리 정렬(in-place sorting)로 구현할 수 있다.
        • 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 졍렬 방법보다 효율적이다.