[자료구조] 정렬 -1

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.

https://github.com/ejImDev/data_structure_study.git

선택정렬

• 배열에서 아직 정렬되지 않은 부분의 원소들중 최솟값을 ‘선택’하여 정렬된 부분의 바로 오른쪽 원소와 교환하는 정렬 알고리즘
  
  

• 배열 a의 왼쪽 부분은 이미 정렬되어 있고 나머지 부분은 정렬 안된 부분
  
• 정렬된 부분의 키들은 오른쪽의 정렬되지 않은 부분들의 키보다 작다
  
• 선택정렬은 항상 정렬 안된 부분에서 최솟값을 찾아 왼쪽의 정렬된 부분의 바로 오른쪽 원소로 옮기기 때문
  
• 이 과정은 a에서 최솟값을 a[i]와 교환 후에 (b)와 같이 i를 1증가시키며. 이를 반복적으로 수행
  

수행시간

• 선택정렬은 루프가 1번 수행될 때마다 정렬되지 않은 부분에서 가장 작은 원소를 선택
  
• 처음 루프가 수행될 때 N개의 원소들 중에서 min을 찾기 위해 N-1번 원소 비교
  
• 루프가 2번째 수행될 때 N-1개의 원소들 중에서 min을 찾는데 N-2번 비교
  
• 같은 방식으로 루프가 마지막으로 수행될 때: 2개의 원소 1번 비교하여 min을 찾음
  
• 따라서 원소들의 총 비교 횟수 = O(N²)
  
  

선택정렬의 특징

• 입력에 민감하지 않음
  
  • 항상 O(N²) 수행시간이 소요
    
• 최솟값을 찾은 후 원소를 교환하는 횟수가 N-1
  
  • 이는 정렬알고리즘들 중에서 가장 작은 최악경우 교환 횟수
    
• 하지만 선택정렬은 효율성 측면에서 뒤떨어지므로 거의 활용되지 않음
  
  
  

삽입정렬

• 배열이 정렬된 부분과 정렬되지 않은 부분으로 나뉘며, 정렬 안된 부분의 가장 왼쪽 원소를 정렬된 부분에 삽입하는 방식의 정렬 알고리즘
  
  

• (a) 정렬 안된 부분의 가장 왼쪽원소 i(현재 원소)를 정렬된 부분의 원소들을 비교하며 (b)와 같이 현재 원소 삽입
  
• 현재 원소 삽입 후 정렬된 부분의 원소수 1 증가, 정렬 안된 원소수 1 감소
  
  

수행시간

• 삽입정렬은 입력에 민감
  
• 입력이 이미 정렬된 경우(최선경우)
  
  • N-1번 비교하면 정렬을 마침 = O(N)
    
• 입력이 역으로 정렬된 경우(최악경우)
  
  • O(N²)
    
• 최악의 경우 데이터 교환 수 : O(N²)
  
• 입력 데이터의 순서가 랜덤인 경우(평균경우)
  
  • 현재 원소가 정렬된 앞 부분에 최종적으로 삽입되는 곳이 평균적으로 정렬된 부분의 중간이므로 0.5 x (N(N-1)/2) ≈ 1/4N² = O(N²)
    
    

응용

• 이미 정렬된 파일의 뒷부분에 소량의 신규 데이터를 추가하여 정렬하는 경우(입력이 거의 정렬된 경우) 우수한 성능을 보임
  
• 입력크기가 작은 경우에도 매우 좋은 성능을 보임
  
• 삽입정렬은 재귀호출을 하지 않으며, 프로그램도 매우 간단하기 때문
  
• 삽입정렬은 합병정렬이나 퀵정렬과 함께 사용되어 실질적으로 보다 빠른 성능에 도움을 줌
  
• 단, 이론적인 수행시간은 향상되지 않음
  
  
  

쉘 정렬

• 삽입정렬에 전처리과정을 추가한 것
  
  • 전처리과정 : 작은 값을 가진 원소들을 배열의 앞부분으로 옮기며 큰 값을 가진 원소들이 배열의 뒷부분에 자리잡도록 만드는 과정
    
• 삽입정렬이 현재 원소를 앞부분에 삽입하기 위해 이웃하는 원소의 숫자들끼리 비교하며 한 자리씩 이동하는 단점 보완
  
• 전처리과정은 여러 단계로 진행되며, 각 단계에서는 일정 간격으로 떨어진 원소들에 대해 삽입정렬 수행
  
  

전처리과정 전과 후

• h-정렬 : 간격이 h인 원소들끼리 정렬하는 것
  
• 4-정렬 후 결과 : 작은 숫자들(10,25,35)이 배열의 앞부분으로, 큰 숫자들(35,90,80)이 뒷부분으로 이동
  
• 쉘정렬은 h정렬의 h값(간격)을 줄여가며 정렬을 수행하고, 마지막엔 간격을 1로하여 정렬
  
• h=1인 경우는 삽입정렬과 동일
  
  

수행시간

• 수행시간은 간격을 어떻게 설정하느냐에 따라 달라짐
  
• Hibbard의 간격 : 2^k^-1 (즉, 2^k^-1, … , 7,3,1) O(N^1.5^)시간
  
• Marcin Ciura의 간격 : 1, 4, 10, 23, 57, 132, 301, 701, 1750
  
• 정확한 수행시간은 아직 풀리지 않은 문제
  
• 일반적으로 쉘정렬은 입력이 그리 크지 않은 경우에 매우 좋은 성능을 보임
  
  

응용

• 쉘정렬은 임베디드 시스템에서 주로 사용되는데, 이는 간격에 따른 그룹별 정렬알고리즘을 하드웨어 설계를 통해 구현하는 것이 매우 쉽기(효율적이기) 때문
  
  

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/nHHJCHGbV3c