정렬

삽입 정렬 

• 삽입 정렬 ? 
  
  오름차순 정렬을 진행하는데, 작은 값을 앞으로 삽입하고 큰 값을 뒤로 이동시킨다하여 삽입 정렬이라고 한다. 
• 시간 복잡도 
  평균과 최악 모두 O(n 제곱)
• 1회전 : 두 번째 값을 첫 번째 값과 비교하여 작은 값을 앞으로 삽입.
• 2회전 : 세 번째 값을 첫 & 두 번째 값과 비교하여 오름순으로 정렬
• 3회전 : 네 번째 값을 첫 & 두 & 세 번째 값과 비교하여 오름차순 정렬 

선택 정렬 

• 선택 정렬?
  
  레코드 중에서 가장 작은 값을 찾아 첫 번째 자리로, 두 번째로 작은 값을 찾아 두 번째 자리로 놓는 방식을 반복 하여 정렬하는 방식이다. 
• 시간 복잡도
  평균과 최악 모두 O(n 제곱)
• 1회전 : 첫 번째 값과 두 번째 값 비교 후 작은 값을 첫 번째 값으로 이동, 이 과정을 모든 요소들에 반복. 첫 레코드 자리와 2~마지막 레코드 자리가 계속 비교됨
• 2회전 : 두 번째 레코드 3~마지막 레코드 자리를 계속 비교하여 작은 값 앞으로 이동 

버블 정렬 

• 버블 정렬 ? 
  
  인접한 두 개의 레코드 씩 비교하여 큰 값을 뒤로 보내는 정렬 방식으로 가장 큰 자리 값을 1회차에 하나씩 확정 시켜나간다. 
• 시간 복잡도 
  평균과 최악 모두 O(n 제곱)
• 1회전 : 첫 번째 값과 두 번째 값 비교하여 큰 값을 2번째 레코드 자리로. 두 번째 와 세 번째, ... 마지막 자리 까지 반복하여 제일 큰 값을 확정시킴
• 2회전 : 첫 번째 값과 두 번째 값 비교하여 큰 값을 2번째 레코드 자리로. 두 번째와  세 번째, ... 마지막 자리 -1 까지 반복

쉘 정렬 

• 쉘 정렬 ? 
  
  쉘 정렬은 매개변수 값으로 서브 파일을 구성하고, 각  서브파일을 삽입 정렬 방식으로 순서 배열하는 과정을 반복한다. 
• 시간 복잡도 
  : 평균 수행 시간 복잡도는 O(n 1.5제곱) 이고 최악 수행 시간 복잡도는 O(n 제곱)이다. 

퀵 정렬 

• 퀵 정렬 ?
  
  퀵 정렬은 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복한다. 
• 시간 복잡도 
  : 평균 O(n로그2n)

힙 정렬 

• 힙 정렬 ?
  
  힙 정렬은 전이진 트리를 이용한 정렬 방식이다. 
• 시간 복잡도
  평균과 최악 모두 O(n로그2n)