선택정렬(Selection sort)

선택정렬(Selection sort)

• 제자리 정렬(in-place-sorting)알고리즘의 하나
  • 입력 배열이외의 다른 추가 메모리 요구 x
• 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택
  • 첫 번째 위치에는 가장 최솟값
  • 두 번째 위치에는 그다음 최솟값
• 과정
  
  1. 주어진 배열 중 최솟값을 찾는다.
  2. 그 값을 맨 앞에 위치한 값과 교체
  3. 맨 처음 위치를 뺀 나머지 숫자를 1~2방법으로 다시 교체

 

선택정렬의 장점 

• 자료 이동 횟수가 미리 결정된다

선택정렬의 단점

• 안정성 만족 x 
• 만약 2 2 3 5 4 1 이 있다면  1회전에 맨앞의 2가 맨뒤로 가기 때문에 안정성을 만족하지 못한다.

선택정렬 시간복잡도

 

 

 

삽입정렬(Insertion sort)

• 손안의 카드를 정렬하는 방법과 유사하다
  • 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리에 찾아 삽입한다.
  • 새로 삽입될 카드의 수만큼 반복 하면 전체카드 정렬된다.
• 앞에서부터 순서대로 이미 정렬된 배열 부분과 비교하여 자신위 위치를 찾아 삽입
• 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 넣는다.
• 과정
  1. 두번째 부터 시작해서 자신의 왼쪽과 비교하여 삽입
  2. 오름차순 기준 현재  Key값보다 왼쪽 값이 크다면 왼쪽값을 오른쪽으로 한 칸 민다.

 

 

 

삽입정렬 장점

• 안정정렬
• 대부분의 원소가 정렬되어 있다면 매우 효율적

삽입정렬 단점

• 원소의 이동이 잦다.
• 양이 많다면 적합하지 않다.

삽입정렬 시간복잡도

• Best Case
  • 정렬이 되어 있는상태 O(n)
• Worst Case
  • 역순으로 되어있을 때 O(n^2)

 

 

 

 

참고 

gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html